Number of 1 Bits
EasyHamming weight · n & (n − 1)
Count the 1s in a number's binary form by repeatedly removing the lowest 1.
The idea
Repeatedly clear the lowest set bit with n & (n−1), counting each clear. The loop runs exactly once per 1-bit, so it's faster than checking all 32 positions.
1
0
1
1
0
1
0
0
0
1
2
3
4
5
6
7
n180
count0
Step 1 of 6. Trick: n & (n − 1) erases the lowest set 1-bit. Count how many times we can do that. Values: 1, 0, 1, 1, 0, 1, 0, 0. n 180, count 0.
1/6
Optimal
timeO(bits set)spaceO(1)
One iteration per set bit.
1// clear the lowest set bit each step2let count = 0;3while (n !== 0) {4 n &= n - 1;5 count++;6}7return count;Input
- array
- [1, 0, 1, 1, 0, 1, 0, 0]
Memory
- n
- 180
- count
- 0
Output
- count
- 0
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 11
- Output:
- 3
- Explanation:
- 11 is 1011 → three 1s.
Example 2
- Input:
- n = 128
- Output:
- 1
- Explanation:
- 128 is 10000000 → one 1.
Example 3
- Input:
- n = 255
- Output:
- 8
- Explanation:
- 255 is 11111111 → eight 1s.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.