Count Bits - Brian Kernighan's Algorithm

Here's a faster way: repeatedly clear the rightmost set bit until $n$ becomes 0. Count how many times you clear a bit.

The trick is $n \& (n - 1)$. This expression clears the rightmost 1 bit in $n$. Why? When you subtract 1 from $n$, the rightmost 1 becomes 0 and all bits to its right become 1. ANDing with the original $n$ cancels them out.

Example: $n = 12 = 1100$. Compute $n - 1 = 11 = 1011$. Then $n \& (n-1) = 1100 \& 1011 = 1000 = 8$. The rightmost 1 is gone. This algorithm runs in $O(k)$ time where $k$ is the number of set bits, not $O(32)$.