i@yujinyan.me

Blog

Number of 1 Bits

LeetCode

Write a function that takes an unsigned integer and returns the number of 11 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 nn and n1n - 1. This operation has the effect of flipping the least significant 11 to 00. Then, answer is the number of times we need to carry out this operation to turn the number to zero.

n10110100n110110011n&(n1)10110000\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 nn and n1n - 1, look at the binary representation of the three numbers closely. Notice that after the operation:

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

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

Reference

LeetCode Official Solution - Number of 1 Bits