Number of 1 Bits

March 23, 2021

Write a function that takes an unsigned integer and returns the number of $1$ bits it has (also known as the Hamming weight).

Code

public int hammingWeight(int n) {
int result;
for (; n != 0; n = n & n - 1) result += 1;  return result;
}

Explanation

The trick is to do a bitwise $\And$ of $n$ and $n - 1$. This operation has the effect of flipping the least significant $1$ to $0$. Then, answer is the number of times we need to carry out this operation to turn the number to zero.

$\begin{array}{rll} n & 1011 & 0\textcolor{#EC407A}{1}00 \\ n-1 & 1011 & 0011 \\ \hline n\And(n-1) & 1011 & 0000 \end{array}$

To see the effect of $\And$-ing $n$ and $n - 1$, look at the binary representation of the three numbers closely. Notice that after the operation:

• the least significant $\textcolor{#EC407A}{1}$ of $n$, highlighted in pink turns to $0$ after the operation;
• the bits to the right of $\textcolor{#EC407A}{1}$ are all $0$’s;
• the bits to the left of $\textcolor{#EC407A}{1}$ remain the same.

This is the case when $n$ is even. Whn $n$ is odd, the effect is the same.

Reference

LeetCode Official Solution - Number of 1 Bits