# 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
```