# Two’s complement

*Journey into the machine: how signed integers are stored in memory*

In a computer, all is stored in bits, as the machine only understand 0 and 1.

Numbers follow that rule and are stored in a binary format. A sequence of 0 and 1, where each position maps to a power of 2. Usually numbers are stored in one or more bytes, a byte representing 8 bits.

In the examples I will give below, I will use 4bits numbers just for clarity but it can be generalized to any larger number. Number 5 in binary yields 0101.

5 is seen as 0 * 2³ + 1 * 2² + 0 * 2 + 1.

### Unsigned Numbers

An unsigned numbers is always 0 or positive. If it is stored in 4 bits, then I have 2*2*2*2 = 2⁴ = 16 possible combinations. Then I can write any integer from 0 (stored as 0000) to 15 (stored as 1111).

### Signed Numbers

What if I want to store -1 on my computer ? On 4 bits ? People came up with different ideas, all share 1 common ground, it splits the domain of possible values in 2. So instead of going from 0 to 15, it will go from -some value to +another value. Here are some ideas:

#### 0. Save the leftmost bit for the sign

This way, I can write all numbers between -7 (1111) to +7(0111).

This method has 2 flaws, I have 2 possible values for 0: 0000 for +0 and 1000 for -0. Then additions are not straight forward. If I add 5 + (–5). Doing as usual leads to 0010 = 2, Oops. Next idea.

#### 1. Reverse the number — One’s complement

A different take, I take the opposite, flipping every bit. I end up with the same minimum and maximum values, and now 5 + (-5) = 0. However I still have 2 values for 0 and subtractions are not obvious.

#### 2. Two’s complement

This technique can be summed up in 2 steps:

- flip the number
- add one

In more details: as before I do not change anything to store positive numbers. I only work to store negative values. To go from 5 to -5:

Here we see all the possible values we can make with 4 bits.

I only have one value for 0, so now I can go from -8 to +7. We can note as well that for -8, the leftmost bit works both as a negative sign indicator and the actual binary representation for 8.

Here are the explanation for why there is only one combination of bits for 0 and some examples of addition and subtraction.

As the numbers are stored in 4 bits, any carry over after is discarded by the machine.

Adding 3 to 2

Subtracting 4 to 2 is the same thing as adding -4 to 2

A little extra work is needed, since the result is negative we need to take the two’s complement, this value is 2, so the result of -4 +2 = -2 …good…

### Conclusion

Two’s complement is a great way to stored signed values in memory. However, one still need to pay attention with overflow. Adding 2 large numbers would lead to a carry-over falling in the sign bit, and therefore yield a negative value.

This method is not magic, here is a good explanation of why it works.