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 2^{n}-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…

### Like this:

Like Loading...

*Related*

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).

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…

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

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