🐟 Blog

Number of 1 Bits

March 23, 2021


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


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


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.


LeetCode Official Solution - Number of 1 Bits

© Attribution Required | 转载请注明原作者与本站链接
© 2022 yujinyan.me