# A binary number puzzle

As I haven’t finished the posts I’ve planned to write, here is a quick puzzle involving binary numbers:

Compute the total number of one-bits in the binary representations of the numbers 0 to 2n-1 for n from 1 to 50.

For example, for n = 2 we have four different binary representations: 00, 01, 10 and 11. Adding the number of one-bits: 0 + 1 + 1 + 2 = 4.

Hint: it’s quite easy once you get the pattern…

## 4 thoughts on “A binary number puzzle”

1. Demian says:

Cool puzzle. Brute force didn’t make it (http://ideone.com/8EjNj). But it wasn’t that hard to find the relation between the number of ones and n (http://ideone.com/G4ZMf). With memoization, this thing flies (though it’s not necessary for 1..50 really http://ideone.com/PYaBu).

2. Axel says:

Here’s an analytic solution though not the simplest of all.

Let’s start by the example given:

With n = 2 we have 00, 01, 10, 11 => 4 one-bits. If we add an extra bit by going to n = 3 we’ll have 000, 010, 100, 110, 001, 011, 101, 111 => 12.
As we can see we’ll have twice the amount of one-bits as with the previous value of n plus one more one-bit per new binary representation(we double the representations every time we add a bit, so in each step we are adding 2^(n-1) representations to the last one).

This leads to the following expression.
So X_n = 2(X_(n-1)) + 2^(n-1).

But digging a little bit further…

X_n = 2(2(X_(n-2)) + 2^(n-2)) + 2^(n-1)
= 4(X_(n-2)) + 2*2^(n-2) + 2^(n-1)
= 4(X_(n-2)) + 2^(n-1) + 2^(n-1)
= 4(X_(n-2)) + 2*2^(n-1)
….
= 8(X_(n-3)) + 3*2^(n-1)

Keep going and the pattern shows up pretty fast…

Finally we know that X_1 = 0 + 2^(1-1) = 1

In conclusion: X_n = n * 2^(n-1)

Again this is not the best of the explanations…

3. mchouza says:

The two proposed solutions match (http://ideone.com/YGZto). I will post my solution tomorrow, thanks for your contributions!

4. […] (This is the answer to the puzzle proposed in the previous post.) […]