40fy | Two's Complement as a clock

By putting forward the hands of the clock you shall not advance the hour.

- Victor Hugo

A clock analogy

In a 3-bit register, arithmetic is modulo 2³=8. Concretely, 111+001≡000 because the next bit doesn’t fit. As the successor of 111 is now 000, you can join them forming a clock-like loop:

    Binary      Unsigned    Two's complement
    \000          \ 0             0
 111 \   001     7 \   1      -1     1 
110       010   6       2    -2       2
 101     011     5     3      -3   \ 3
     100            4            -4 \

If you ever read a clock as “quarter to ten”, two’s complement should feel familiar. Those \ represent the overflow lines, across which modular and normal arithmetic differ, but not irreparably¹. At both the most significant bit changes. It denotes negativity, and thus -4 rather than 4.

The number one trick

How can we easily compute the two’s complement representation of a number -a? Computers certainly don’t do it by imagining clocks. Their approach begins with a neat trick: if ~a is the bitwise negation of an N-bit register a, then:

a + ~a + 1 = 2N ≡ 0.

Intuitively, adding ~a fills all and only the zeros in a. The sum of two bits is just XOR with an AND carry bit. a AND ~a = 0 so no carries, a XOR ~a = 1 so the result is all ones. Hence ~a is called the ones’ complement of a. Then, as in the opening example, we add 1 to get 0 (modulo N).

By definition, a + -a = 0, so a + -a ≡ a + ~a + 1. Cancel the a and voilà: -a ≡ ~a + 1.

Geometric insight

Bitwise negation corresponds to a mirror along the overflow axis. Adding 1 turns it into a mirror along the vertical axis, which, as predicted, matches arithmetic negation! Nice for -0 = 0 but not so much for the most negative number -4.

The choice of octagon orientation² favored two’s complement, where the center is the number 0, while the natural unsigned representation centers the overflow line:

  Binary      Unsigned   Sign-magnitude  Ones' compl.  Two's compl.
  111|000        7|0          -3|0          -0 0          -1 0
110  |  001    6  |  1      -2  |  1      -1     1      -2     1
101     010    5     2      -1  |  2      -2  |  2      -3  |  2
  100 011        4 3          -0|3          -3|3          -4|3

We can now summarize the conceptual progression of signed representations: sign-magnitude is just treating the most significant bit as a minus sign, but then negative numbers run backwards and -0 is not 0; ones’ complement fixes the former and two’s the latter.