two's complement

two’s complement is the most popular way of encoding negative numbers (aka. signed number representation); it is popular because it makes signed number operation much easier than other representations;

the problem background: computers have an adder circuit for unsigned number addition, and they want to support signed number additions, too; a number here means an integer, same below;

there are several ways of representing signed numbers:

• one’s complement;
• two’s complement;
• offset binary (excess-k);
• base -2;

what makes two’s complement excel is: we can use the same adder circuit for both unsigned and signed number additions;

to illustrate the idea, assume we have an adder circuit for 3-bit unsigned numbers (ie. n == 3):

111     7
110     6
101     5
100     4
011     3
010     2
001     1
000     0

before we delve into signed numbers, we formally define the specification of the adder circuit using modular arithmetic:

• for any inputs a and b, the circuit outputs c where c == (a + b) mod 8;

this is easy to prove: the adder circuit can either overflow or not; if it does not overflow, then it gives correct result; if it does overflow, it will give a result offset by 2^3 == 8;

this tells us a property of the adder circuit: it is actually doing modular addition; no matter what inputs a and b it takes, its output will be congruent to (a + b) mod 8;

nice property; now we can handle signed numbers: if any input a is negative, we map a to a' before the addition, where a' is in range [0, 8) and a' == a mod 8; if both are negative then we map both; from the above property, its output will be congruent to (a' + b') mod 8, which is the same as (a + b) mod 8;

when signed numbers have range [-4, 4), there is only one number in this range that is congruent to (a + b) mod 8; if no overflow happens, this will be the correct result;

looking back at the mapping a to a':

-1 -> 7
-2 -> 6
-3 -> 5
-4 -> 4

this is exactly two’s complement encoding:

111     7   -1
110     6   -2
101     5   -3
100     4   -4
011     3    3
010     2    2
001     1    1
000     0    0

what the mapping does is wrapping large values down to their congruences;

the name two’s complement comes from using complements in radix 2; but i like naming it modular representation as i think this is a better name that explains how it actually works;

you can play fancier with this modular representation; any of these mappings are valid and give correct addition results (assuming no overflow):

111     7   -1   -1  -25
110     6   -2   -2    6
101     5   -3    5   21
100     4   -4    4  -12
011     3    3    3  -13
010     2    2    2   10
001     1    1    1  -15
000     0    0    0  -16
        |    |    |    |
    unsigned |    |    |
 two's complement |    |
shift two's complement |
               generic modular