Flip and adjust by 0ne: two complement visual

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.

number 5 in binary, I use 4 bits

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

Storing negative number, saving 1 bit

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.

Storing negative numbers, flip the positive value

2. Two’s complement

This technique can be summed up in 2 steps:

  1. flip the number
  2. 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:

steps 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.

carry over gets discarded after 4 bits, only one combination for 0

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

Adding 3 to 2

simple addition

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

simple subtraction

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.