Rudi's solution to The Bit counting Problem


  buf[0] = 0;

  int p = 1;

  int s = 1;

  do

  {

    for (int i = p; i < p * 2; ++i)

      buf[i] = buf[i - p] + 1;

    p *= 2;

    s += p;

  } while (s <= N);

My solution uses the fact that the number of bits set in i, n(i) can be described recursively.

Looking at the first 16 values of n:

0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4

It can be seen that the number of bits can be described recursively:

n(2^j + 1) = n(i) + 1 for i = 0 -> j, for j = 0 -> 2^N

This means that finding the next 2^j values, add 1 to the first 2^j values:

  0
  0{0+1}
  01{0+1}{1+1}
  0112{0+1}{1+1}{1+1}{2+1}
  01121223{0+1}{1+1}{1+1}{2+1}{1+1}{2+1}{2+1}{3+1}

  ß

  0
  01
  0112
  01121223
  0112122312232334

back