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
andb
, the circuit outputsc
wherec == (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