# Number of 1 Bits

easy | Accept. 71% | 力扣中文站

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