Skip to main content

Algorithm to Count the Number of On-Bits

After the CS188 final, I engaged in an interesting conversation about job hunting with my friends, and that reminded me of the following interview question I was asked a year ago: Find an efficient algorithm that finds the number of on-bits in an integer, given that bitwise and arithmetic operations can be done in a constant time. A naive implementation is as follows:

while (number) {
  if (number & 0x1)
    counter++;
  number = number >> 1;
}

The key idea of this algorithm is to increment the counter if the least significant bit is on, and shift the number down by 1 bit. It can be shown that repeating this process until the number becomes 0 correctly counts the number of on-bits in the number. However, this algorithm is very inefficient when the most significant bit is 1 and the rest is filled with 0s. Namely, the time complexity of this algorithm is O(logn(hob)) where hob is the highest on-bit in the number.

And here’s a better algorithm that my interviewer showed me. This algorithm completes in O(m) where m is the number of on-bits:

while (number) {
  number &= number^(-number);
  counter++;
}

Correctness Proof #

Base case #

Clearly, when number is 0, while loop terminates without incrementing the counter. Thus, assuming that counter is 0 initially, this algorithm returns counter = 0 when there is no on-bit in the number.

Inductive step #

To generate -number, we flip the all bits in the number and add 1 since we're using two's complement; the resultant bits is such that all bits to the left of the right-most 1 is flipped (excluding the right-most 1). e.g. -11010100 = 00101100. Hence, number XOR -number gives the bits of 1s with one 0 placed at where the right-most 1 was. e.g. 11010100^(-11010100) = 11111011. Thus, number AND (number XOR -number ) yields the new number with the right most on-bit removed. Because we increment the counter by 1, the sum of the number of bits remaining in the number and the value of counter is consistent in this step.