The problem
Return how many bits of the positive integer n are 1 in its binary form (its “Hamming weight”). 11 is 1011 in binary: three 1s.
Examples
01
- Input
n = 11
- Output
3
02
- Input
n = 128
- Output
1
03
- Input
n = 2147483645
- Output
30
Constraints
- 1 ≤ n ≤ 2³¹ − 1
The idea
Subtracting 1 flips the lowest 1 bit to 0 and every 0 below it to 1: 1100 − 1 = 1011. AND (&, 1 only where both bits are 1) of n and n − 1 therefore keeps everything above that bit and clears the rest: 1100 & 1011 = 1000.
So n &= n − 1 removes exactly one 1 bit. Count how many times it runs before n is 0. It loops once per 1 bit, not once per bit.
- Time
- O(number of 1 bits) — at most 31
- Space
- O(1)
Solution · every language run against every case
class Solution: def hammingWeight(self, n: int) -> int: count = 0 while n: n &= n - 1 # n - 1 flips the lowest 1 bit and the 0s below it: & clears exactly that bit count += 1 return count