Kernighan's Method
The fastest way to count Set Bits (Hamming Weight). A silicon-level trick that destroys
one bit at a time using n & (n - 1).
Technical Essence
n &= (n - 1) clears the rightmost set bit. Total iterations = number of set bits.
Complexity
O(k)
Example 1: n =
7 (0111)
Iteration 1: Destroy rightmost bit
0 1 1 1 (n=7)
& 0 1 1 0 (n-1=6)
= 0 1 1 0 (Result: 6)
0 1 1 1 (n=7)
& 0 1 1 0 (n-1=6)
= 0 1 1 0 (Result: 6)
Iteration 2: Destroy next bit
0 1 1 0 (n=6)
& 0 1 0 1 (n-1=5)
= 0 1 0 0 (Result: 4)
0 1 1 0 (n=6)
& 0 1 0 1 (n-1=5)
= 0 1 0 0 (Result: 4)
Iteration 3: Destroy final bit
0 1 0 0 (n=4)
& 0 0 1 1 (n-1=3)
= 0 0 0 0 (Done!)
0 1 0 0 (n=4)
& 0 0 1 1 (n-1=3)
= 0 0 0 0 (Done!)
Count: 3 Iterations
Example 2: n =
12 (1100)
Iteration 1: Skip trailing zeros
1 1 0 0 (n=12)
& 1 0 1 1 (n-1=11)
= 1 0 0 0 (Result: 8)
1 1 0 0 (n=12)
& 1 0 1 1 (n-1=11)
= 1 0 0 0 (Result: 8)
Iteration 2: Final bit flip
1 0 0 0 (n=8)
& 0 1 1 1 (n-1=7)
= 0 0 0 0 (Done!)
1 0 0 0 (n=8)
& 0 1 1 1 (n-1=7)
= 0 0 0 0 (Done!)
Count: 2 Iterations