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

Much simpler answer:

Let x be an array of length k+1 and x[i] has the number of set bits in i.

x[0] = 0
for i=1:k
    x[i] = x[i>>1] + i&1

Answer 2

We start by manually evaluating the bit count for some small numbers. We note a recurrence relation between the bit count of n and previous results:

 n: | count(n): | recurrence:
==============================
  0 |        0 |
  1 |        1 |
------------------------------
 10 |        1 | =  count(0) + 1
 11 |        2 | =  count(1) + 1
------------------------------
100 |        1 | =  count(0) + 1
101 |        2 | =  count(1) + 1
110 |        2 | = count(10) + 1
111 |        3 | = count(11) + 1
...

Given all bit counts up to 2 = 2¹, we can compute the bit counts up to 4 = 2² by adding 1. Given the bit counts up to 4 = 2², we can compute the bit counts up to 8 = 2³ by adding 1. We generalize this to the k-th power of two and can come up with following exemplary implementation:

// Counts and returns number of enabled bits for integers 0 - n:
function count_bits(n) {
  let count = new Array(n);
  count[0] = 0;
  for (let i = 1, j = 0, k = 1; i <= n; ++i, ++j) {
    if (i == 2**k) { // k-th bit of i has been enabled
      k++;
      j = 0;
    }
    count[i] = count[j] + 1;
  }
  return count;
}

// Example:
console.log(count_bits(17).join());

We note that all operations involved are incrementing by one, random array access, copying array elements and checking the k-th bit of loop increment i via i == 2**k which could be rewritten as i & 1 << k or - for arbitrary precision of i - as a random array access.

Assuming that all primitive operations listed above are in O(1) on our machine, the total runtime complexity is in O(n).

This would equally hold for arbitrary precision integers - where incrementing has an average runtime complexity of O(1) - unless copying count[i] = count[j] + 1 takes more than constant time. As this is unfortunately the case for arbitrarily large integers, our runtime complexity is in O(n log(log(n))) as we need O(log(log(n))) space to store the bit count of n.

Answer 3

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.