Description
Count set bits in a nonnegative 32-bit integer.
Solution
def hamming_weight(n):
count = 0
while n:
n &= n-1
count += 1
return countExamples
Example 1
- Input
[11]- Output
3
11 in binary is 1011, with three ones.
Example 2
- Input
[0]- Output
0
Zero contains no set bits.
Example 3
- Input
[128]- Output
1
128 is a power of two with one set bit.
Approach
Repeatedly clear the lowest set bit until the value becomes zero.
Time & space
O(b) time for b set bits, at most 32; O(1) space.