How to count the number of 1 bits set in 0, 1, 2, ..., n in O(n) time?

Question

This was an interview question. The original questions asks:

Given a positive integer N, count the number of 1's in each integer from 0 to N, and return the count in an array of size N+1. Do it in O(n) time.

An Example would be:

Given 7, then return [0, 1, 1, 2, 1, 2, 2, 3]

Of course, the easiest way is to create a loop counting 1's for every integer, but that would be O(kn) time, with k as the size of the integers in bits. So either there's a way to count the number of 1's of an integer in O(1) time, or there's a way to directly generate the count going from 0 to N. I'm sure both methods exist, but can't figure out either.

Answer 1

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 2^k - 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.