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…

Advertisements

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.) […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s