Counting Set Bits
Kernighan's trick: n & (n−1) always clears the lowest set bit, so the loop runs once per 1-bit rather than once per bit position.
- Category
- Bit Manipulation
- Time complexity
- O(set bits)
- Space complexity
- O(1)
Pseudocode
while n ≠ 0 n ← n & (n−1) — clear lowest 1 iterations = number of 1s
Reference implementation
count = 0
while n:
n &= n - 1 # drop lowest 1
count += 1
# Kernighan's trick