Number of 1 Bits
Write a function that takes a positive integer and returns the number of set bits (1-bits) in its binary representation. This is also called the Hamming weight. **Core Insight:** The classic bit trick `n & (n - 1)` clears the lowest set bit of `n`. By repeatedly applying this until `n` becomes 0, we count exactly how many set bits there were — one iteration per set bit. **Algorithm:** Initialize `count = 0`. While `n != 0`: increment count, then set `n = n & (n - 1)`. Return count. **Why `n & (n-1)` works:** Subtracting 1 from n flips the lowest set bit to 0 and sets all lower bits to 1. ANDing with the original n clears those lower bits, leaving a number with exactly one fewer set bit. **Alternative:** In many languages you can use a built-in popcount function (e.g. `bin(n).count('1')` in Python, `Integer.bitCount(n)` in Java). **Complexity:** Time O(k) where k is the number of set bits — at most O(log n). Space O(1).
Constraints
- •
1 ≤ n ≤ 2³¹ - 1
def hammingWeight(n: int) -> int:
count = 0
while n:
n &= n - 1
count += 1
return count