Number of 1 Bits

easy

№ 191. Number of 1 Bits

71% ac·力扣中文站

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.

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