Brian Kernighan's Algorithm
n and (n - 1) wipes the lowest set bit, so the loop runs once per 1 bit.
Bit Manipulation: Count the 1s, Kernighan style
178 has 4 set bits. 4 rounds, one per 1 bit, not one per bit position.
Cost
- Best
- O(1)
- Average
- O(set bits)
- Worst
- O(log n)
- Space
- O(1)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Bit Manipulation covers these too, in the same run.