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.
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).
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…
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.