While I was writing the Maths for Programmers course, I was constructing some examples to illustrate overflow and noticed a strange pattern. I was working with the number 255, which is the biggest number that can be stored in an unsigned byte, and is represented in binary by 1111 1111. The idea was to use the unsigned byte data type and show the results of calculating 255 + 255 and 255 * 255 – both of those will cause an overflow.
Now 255 + 255 gives 510. And 255 * 255 gives 65,025. Look at what these numbers look like in binary.
Weird huh! One of the numbers is exactly the 16-bit one’s complement of the other (Or if you prefer, the bitwise NOT of the other). Whenever one number has a 1, the other has a 0, and vice versa.
That looks far too neat to be a coincidence, so I started wondering whether the same thing would happen with other similar numbers. The obvious quirk about the number 255 is that it is represented by all 1’s in binary. 7 is similar in this respect, so let’s see if the same thing happens when you start with 7. 7 + 7 is 14, and 7*7 is 49. Converting to binary, we see:
The picture shows that again the sum is the one’s complement of the product.
Clearly something odd is happening here. And the scientist in me immediately wants to know what is going on.
Let’s be a bit more specific. I did these things:
- Chose a number that could be represented by all 1’s in binary. Let’s call this number N and the number of 1’s in it n.
- Worked out the two values sum=N+N and product = N*N.
And found that for a couple of different values of n, sum was the bitwise NOT of product.
So the question is: Is that always the case? Will you always find that sum = bitwise-NOT(product) whatever the value of n you start with?
This is a situation where some simple algebra can very quickly come to the rescue – which is what I did to figure out the answer to this question.
We need to start with an observation. Firstly, if a number is represented by all 1’s in binary, that means the number is just 2 to some integer power minus 1.
- 7 is just 8 -1 or 2 cubed minus 1.
- 255 is just 256 minus 1 or 2 8 minus 1.
And in general, a sequence of n 1’s represents the number 2n – 1. So in fact for the first of our steps, what we were doing is choosing a number N=2n-1. If we also notice that sum=N+N is just the same as sum=2*N, that means we can rephrase the thing we’re trying to prove as: If N=2n-1, then does taking the bitwise NOT of N*N always give 2*N?
The big clue to this is noticing what happens if you add sum and product. Let’s try it for n=3, so sum=7, product=49.
You get an answer that’s all 1’s or another number that’s of the form 2n – 1. Hopefully this picture makes it obvious why that must happen: In each column, you’re adding a 1 and a 0, so every column of the answer must contain 1.
So what that means is that if two numbers x and y are represented as the one’s complement of each other, then that means that x + y = 2p-1 for some integer p.
Does it work the other way round? If two numbers add up to 2p-1, must they be 1’s complements of each other? In fact it does. You can see this from this picture, which shows a number that’s represented as all 1’s in binary and which you’ve got by adding two unknown numbers.
Look at the rightmost bit. That’s 1. The only way to get 1 in the answer is by adding 1 and 0. So one of the original numbers must have had a 1 in that bit, and the other must have had a zero. Notice also that means it’s impossible for anything to have carried into the next bit.
So we now know that if two integers add to give an integer of the form 2p-1, then those integers were bitwise NOTs of each other.
Now’s where the bit of algebra comes in. Let’s add the two numbers sum and product. That comes to
sum + product = 2*N + N2
But that’s just the same as
sum + product = (N+1)2 – 1
And since N = 2n-1, that all comes to
sum + product = 22n – 1
And that’s enough to prove the original hypothesis – because the binary representation of 22n -1 is just 2n 1’s. And we’ve just proven that two numbers that add to give something that’s all 1’s in binary must be bitwise NOTs of each other.
That’s really nice. It shows that the pattern I noticed that sparked off my curiosity is actually a general rule.
As far as I’m aware, knowing this is very likely useless for helping with any commercial programming problem, so if you were hoping that reading this week’s TechieSimon article would tell you what collection to use or how to map your database data to your user interface faster, then – tough luck! But I think it’s a fun example of how a little algebra can cast light on some of the strange patterns you get in binary arithmetic.
By the way, honesty compels me to point out I’ve missed a few minor bits out of my ‘proof’ – in particular if you wanted to write this as a formal mathematical proof, you’d need to think more carefully about how many bits you’re using when you take the bitwise NOT. But I’m fairly sure that does work.
(I posted this on 9 Sept 2013 but rewrote it a day later to make the proof clearer – after some feedback from Nick North that the article wasn’t too clear)