2. Numerical Data Representation

Signed Numbers

The representation of bits may vary or how it is encoded. For example the table below.

code	number
13	-3
14	-2
15	-1
0	0
1	1
2	2
3	3

With unsigned integers, the are all positive!

To have signed integers, you must have a "sign bit" where $0$ means +, and $1$ means -. This is the sign-magnitude representation on a number line.

$-0$

With the binary pattern $100$, we can negative zero. This causes arithmetic to be awkward.

Signed Number Arithmetic (Sign-Magnitude)

This is all related to sign-magnitude arithmetic (not how computers actually store them).

Negation

$-(3) \rightarrow 0011_{2} \rightarrow 1011_{2}$

$-(-3) \rightarrow 1011_{2} \rightarrow 0011_{2}$

Simple enough right? Well...

(Wrong) Addition

$\space \space \space \space 3$
$\underline{+\space 3}$
$\space \space \space \space 6$

$\space \space \space \space 0\overset{0}{1}\overset{1}{1}1$
$\underline{+\space 0011}$
$\space \space \space \space 0110$

Ok so thats all good!

$\space \space \space \space \space \space \space \space \space 3$
$\underline{+\space -3}$
$\space \space \space \space \space \space \space \space \space 0$

$\space \space \space \space 0\overset{0}{1}\overset{1}{1}1$
$\underline{+\space 1011}$
$\space \space \space \space 1110 \Rightarrow -6$

Oh... that is not good.

A Better System? (Ones' Complement)

What if we flip all of the bits to negate a number, well this is Ones' Complement.

$-3 \rightarrow -0011 \xrightarrow[]{\text{flip}} 1100$
$-(-3) \rightarrow -1100 \xrightarrow[]{\text{flip}} 0011$

Ok, good negation works well. What about addition.

$\space \space \space \space 3$
$\underline{+\space 2}$
$\space \space \space \space 5$

$\space \space \space \space 0\overset{1}{0}11$
$\underline{+\space 0010}$
$\space \space \space \space 0101$

$\space \space \space \space \space \space \space \space \space 3$
$\underline{+\space -2}$
$\space \space \space \space \space \space \space \space \space 1$

$\space \space \space \space \overset{1}{0}\overset{1}{0}\overset{1}{1}1$
$\underline{+\space 1011}$
$\space \space \space \space 0000??$

Wait! Add the carry back in

$\space \space \space \space 0000$
$\underline{+\space 0001}$
$\space \space \space \space 0001 \Rightarrow 1$

Since this is positive, we don't flip.

Two's Complements (Signed Numbers)

Two additions can be costly. So we use two's complements instead.

Like ones' complements, we flip all the bits, but then we add one.

It is lopsided and there is no $+4$, but arithmetic is easy and we generally use this with signed-integers.

$-(3) \rightarrow -0011 \xrightarrow[]{\text{flip}} 1100 \xrightarrow[]{\text{add } 1} 1101$
$-(-3) \rightarrow -1101 \xrightarrow[]{\text{flip}} 0010 \xrightarrow[]{\text{add } 1} 0011$

We do not need to substract since $flip(k+1) == flip(k-1)$ if we ignore the carry.

$\space \space \space \space 3$
$\underline{+\space 7}$
$\space \space 10$

$\space \space \space \space 0\overset{1}{0}11$
$\underline{+\space 0010}$
$\space \space \space \space 0101$

$\space \space \space \space \space \space \space \space \space 3$
$\underline{+\space -7}$
$\space \space \space \space \space\space -4$

$\space \space \space \space 0\overset{1}{0}\overset{1}{1}1$
$\underline{+\space 1001}$
$\space \space \space \space 1100$

Flip: $0011$
Add $1$: $0100$
Answer in Decimal: $-4$

But how does the computer "know" whether it's doing signed or unsigned addition?

It doesn't

Neat Properties

If we take a posivite number and add zeros:

$120_{10}=0111\space 1000_2$
$0000\space 0000\space 0111\space 1000_{2}=120_{10}$

If we take a negative number and add ones:

$1000 \space 0111_2 = -0110 \space 1000_2 + 1_2$
$\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space = -0111 \space 1001_2 = -121_{10}$

$1111 \space 1111 \space 1000 \space 0111_2 = -0000 \space 0000 \space 0111 \space 1000_2 + 1_2$
$\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space\space \space\space \space =-0000 \space 0000 \space 0111 \space 1001_2 = -121_{10}$

Pitstop

$10001010$

Is it signed? Is it unsigned?

Well... We don't know, arbitrariness continues.

Minimum Number of Bits to Represent $-16$

1s' complement uses $1$ bit for sign, including negative zero.
Range of $n$-bit numbers is $-2^{n-1}-1\rightarrow 2^{n-1}-1$

Answer: $6$ bits are needed.
$0001 \space 0000 \rightarrow \text{flip} \rightarrow 1110 \space 1111 \rightarrow \text{truncate} \rightarrow 10 \space 1111$

---

2's complement uses $1$ bit for sign, excluding negative zero.
Range of $n$-bit numbers is $-2^{n-1}\rightarrow 2^{n-1}-1$

Answer: $5$ bits are needed.
$0001 \space 0000 \rightarrow \text{flip} \rightarrow 1110 \space 1111 \rightarrow \text{add} \space 1 \rightarrow 1111 \space 0000 \rightarrow \text{truncate} \rightarrow 1 \space 0000$

Fliping

Only flip when reading negation, and flip negative numbers to read them more easily.

Overflow & Edgecases

int main() {
    tiny number = -6;
    print << (number - 1) << enter;

    return 0;
}

Output: $-7$

int main() {
    tiny number = -7;
    print << (number - 1) << enter;

    return 0;
}

Output: $-8$

int main() {
    tiny number = -8;
    print << (number - 1) << enter;

    return 0;
}

Output: $7$

Wait! What?

Well, think of it like a carrousel.

Decimal	Binary
$0$	$0000$
$1$	$0001$
$2$	$0010$
$3$	$0011$
$4$	$0100$
$5$	$0101$
$6$	$0110$
$7$	$0111$
$-8$	$1000$
$-7$	$1001$
$-6$	$1010$
$-5$	$1011$
$-4$	$1100$
$-3$	$1101$
$-2$	$1110$
$-1$	$1111$

This is Fine!

Just use really big values, and good programming practices.

Negation of the Smallest Integer

$-(-8) \rightarrow 1000 \xrightarrow[]{\text{flip}} 0111 \xrightarrow[]{\text{add } 1} 1000 \rightarrow -8$

In other words, since we do not have an $8$ in our carrousel, we can't do $-(-8)=8$

Next Page →