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?

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.

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

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.

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.

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.

© 2004 Daniel S. Wilkerson