1. One-Liner
Repeatedly do n &= n-1 to drop the lowest set bit; iteration count equals population count.
2. The Problem It Solves
Count bits in sparse integers, parity checks, and when hardware popcnt unavailable or disallowed.
3. The Core Idea
Subtracting 1 flips trailing zeros and lowest 1; AND clears that 1—each loop removes exactly one set bit.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | c=0 |
| 2 | While n≠0: n &= n-1; c++ |
| 3 | Return c |
5. Dry Run Example
n=12 (1100): iterations 1100→1000→0000 → two bits.
6. Key Properties
| Property | Detail |
|---|---|
| Complexity | O(number of 1s), not bit width |
| vs lookup | Trade memory |
| Unsigned | Mind sign in Java |
7. Where It Is Used
| Domain / System | Use |
|---|---|
| Networking | Hamming weight |
| Crypto | Parity side-channels careful |
| Embedded | Bit counting |
8. Interview Tips
Compare to __builtin_popcount, SWAR broadword; know n&(n-1) also isolates lowest bit via n XOR (n&(n-1)).
9. Comparison with Other Algorithms
| Technique | Notes |
|---|---|
| Shift loop | O(log n) always |
| Lookup table | O(1) time, space |
| Parallel popcount | SIMD |
10. Complexity
| -- | -- |
|---|---|
| Time | O(k) k = popcount |
| Space | O(1) |
Implementation Example (PYTHON)
def count_set_bits(n):
c = 0
while n:
n &= n - 1
c += 1
return c