#191
Number of 1 Bits
Easy n & (n-1)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count how many bits are set to 1 in the binary form of a number.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: how many switches are ON in this number?
Why this works: n & (n - 1) turns off the lowest ON bit. Count how many times you can do that before n is 0.
Example: n = 11 (1011)
1011 & 1010 = 1010 count 11010 & 1001 = 1000 count 21000 & 0111 = 0000 count 3
✦Hints open one at a time
You can check the last bit with n & 1 and then shift right.
n & (n - 1) clears the lowest set bit. How many times can you do that before n becomes 0?
↗Approach
Brian Kernighan's trick: each n & (n - 1) removes exactly one 1-bit, so the loop runs once per set bit.
</>Solution (Java)
class Solution {
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1); // drop the lowest set bit
count++;
}
return count;
}
}!Common mistake
Using n >> 1 on a negative int in Java — the sign bit is copied in and the loop never ends. Use >>> or the n & (n - 1) loop.
Complexity
- Time: O(number of set bits) ≤ O(32).
- Space: O(1).
