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
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
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.