Thorkil's solution to The Bit counting Problem
buf[0] = 0;
for (int i = 0; i < N; ++i)
buf[i] = buf[i>>1] + (i&1);
Thorkil's solution also uses that the number of bits set in i, n(i) can be described recursively.
n(2i) = n(i)
n(2i + 1) = n(i) + 1
back