Approach Summary
Brian Kernighan: n &= (n-1) clears the lowest set bit. Count iterations until n = 0.
How to Recognize This Pattern
- "Hamming weight / popcount"
- n & (n-1) strips the rightmost 1 bit each iteration
Complexity Analysis
Time Complexity
O(1)
Space Complexity
O(1)
Tags
Divide and Conquer Bit Manipulation