Here's a nice little observation that you can use to do this in time O(n). Imagine you want to know how many 1 bits are set in the number k, and that you already know how many 1 bits are set in the numbers 0, 1, 2, ..., k - 1. If you can find a way to clear any of the 1 bits that are set in the number k, you'd get some smaller number (let's call it m), and the number of bits set in k would then be equal to one plus the number of bits set in m. So provided that we can find a way to clear any 1 bit from the number k, we can use this pattern to solve the problem:
result[0] = 0 // No bits set in 0
for k = 1 to n:
let m = k, with some 1 bit cleared
result[k] = result[m] + 1
There's a famous bit twiddling trick where
k & (k - 1)
yields the number formed by clearing the lowest 1 bit that's set in the number k, and does so in time O(1), assuming that the machine can do bitwise operations in constant time (which is usually a reasonable assumption). That means that this pseudocode should do it:
result[0] = 0
for k = 1 to n:
result[k] = result[k & (k - 1)] + 1
This does O(1) work per number O(n) total times, so the total work done is O(n).
Here's a different way to do this. Imagine, for example, that you know the counts of the bits in the numbers 0, 1, 2, and 3. You can use this to generate the counts of the bits of the numbers 4, 5, 6, and 7 by noticing that those numbers have bitwise representations which are formed by taking the bitwise representations of 0, 1, 2, and 3 and then prepending a 1. Similarly, if you then knew the bit counts of 0, 1, 2, 3, 4, 5, 6, and 7, you could generate the bit counts of 8, 9, 10, 11, 12, 13, 14, and 15 by noting that they too are formed by prepending a 1 bit to each of the lower numbers. That gives rise to this pseudocode, which for simplicity assumes that n is of the form 2k - 1 but could easily be adapted for a general n:
result[0] = 0;
for (int powerOfTwo = 1; powerOfTwo < n; powerOfTwo *= 2) {
for (int i = 0; i < powerOfTwo; i++) {
result[powerOfTwo + i] = result[i] + 1;
}
}
This also runs in time O(n). To see this, notice that across all iterations of all the loops here, each entry in the array is written to exactly once, with O(1) work done to determine which value is supposed to be put into the array at that slot.