Why the '+1' in Two's Complement Arithmetic?

by Daniel S. Wilkerson; 22 June 2004

This is a draft. Sorry for any unclarity.

Have you ever wondered where that +1 comes from when computing negatives in two's complement arithmetic? Inverting the bits to compute the negative seems so natural, but then there is this +1 you have to do. What is the source of the asymmetry that results in this +1, this fly in the ointment?

The problem

Consider a string of N bits as a non-negative binary number. Consider operations plus_N and times_N as arithmetic on N bits except we discard the carry bit that goes off the end; that is, we are doing the usual unsigned arithmetic on binary strings.

This is clearly the ring Z_{2^N} under the standard unsigned interpretation of a bit string as a number. The additive part of the ring is a group, and so inverses are unique. We would like a method for computing the additive inverse of a number in this ring given its representation in bits.

Theorem 1:

1. toggling each bit, operation T, followed by
2. incrementing by one, operation I.

Proof 1:

Note that for any x, toggling its bits and x one gives a string of pure ones; Adding one to that gives zero:

        T(x) + x + 1 = 0.

In a ring we can do standard algebra (here, we are using uniqueness of additive inverses).

        I(T(x)) = T(x) + 1 = -x.

Proof 2:

For a string of bits X, its numerical value is

          N(X) = Sum_i ( X_i * 2^i ).

Multiply by -1 to get the negative:

        - N(X) = Sum_i ( - X_i * 2^i ).

That is, replace 0 by 0 and 1 by -1 and you have the negative. The problem is we don't allow -1 as a digit.

So, add one to every digit; together with the negation, this results in simply togging the original bits. But what is the value of the all_ones string so that we can cancel out what we did? Assume for the moment we know it is -1; we look at how to see that below.

        - N(X) = Sum_i ( - X_i * 2^i ) + -1       + 1
               = Sum_i ( - X_i * 2^i ) + all_ones + 1
               = T(X) + 1
               = I(T(X))

One way we can check that all-ones string is negative one since if you add one to it you get zero and inverses are unique.

Another way is to just recall the sum of a geometric series. Let S denote Sum_{i=0,infinity}.

        S = 1 + r + r^2 + ...
          = 1 + r * (1 + r + r^2 ...)
          = 1 + rS.

Therefore S - rS = 1, or

        S = 1/(1-r).

And for a finite sum

        Sum_{i=0,N-1} = Sum_{i=0,infinity} - Sum_{i=N,infinity}
                      = 1/(1-r) - r^N * Sum_{i=0,infinity}
                      = (1-r^N) / (1-r).

So the value of the N ones is:

        (1 - 2^N) / (1 - 2) = 2^N - 1.

Adding one more gives 2^N = 0.

Proof 3:

Let N be 8 for specificity. Draw a clock with 8 equally-spaced points and labeled sequentially in binary.

       000
   111  |  001
  110  -*-  010
   101  |  011
       100

To take the negative we want to reflect across the 0,4 axis. However toggling the bits reflects across the (-0.5, 3.5) axis.

We can do a change of basis of the reflection we have to get the reflection we want, and further the change of basis matrices are just rotations. Here F_x means reflection about the axis through the point x and R_y means rotate by y. (I'm not checking the signs carefully here.) In my notation, function composition applies from left to right, that is A;B means do A then B.

    (Negation) = F_-1/2
               = R_-1/2; F_0; R_1/2
               = F_0; R_1
               = (Toggle); (Increment)

So why does inverting the bits reflect across the F_-1/2 axis instead of F_0? As Rob Johnson points out, any bijection, in particular a flip, has to maintain the center of mass of a bunch of points, since addition commutes. Inverting the bits is a bijection, and therefore the center of mass of the numbers doesn't move. [Need to show it is a flip also.] The axis of the flip has to go through the center of mass which is the expected value of a point if you pick each digit at random.

Normalizing the clock to sum to 1, not 8, we have the value of a one in each binary place is:

        1/2, 1/4, ....

Each has a probability of 1/2 of being one, and is zero otherwise. Thus, the expected value is:

        1/4 + 1/8 + 1/16

which is also:

        1/4 + 1/8 + 1/16 + 1/32 + .... minus
                           1/32 + ....

equals:

        1/2 - 1/16.

Re-normalizing the sum back to 8 (multiplying by 8) the 1/16 becomes 1/2, the source of the asymmetry.

Conclusion

Acknowledgments