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
And here’s a better algorithm that my interviewer showed me.
This algorithm completes in
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.