# 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(lo{g}_{n}(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.