AlgoScope

Brian Kernighan's Algorithm

n and (n - 1) wipes the lowest set bit, so the loop runs once per 1 bit.

Bit manipulation, algorithm, intermediate
178 has 4 set bits.0001020304050607
178 has 4 set bits.0001020304050607

Bit Manipulation: Count the 1s, Kernighan style

Result, step 6 of 6

178 has 4 set bits. 4 rounds, one per 1 bit, not one per bit position.

How bit manipulation works

Cost

Best
O(1)
Average
O(set bits)
Worst
O(log n)
Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

Bit Manipulation covers these too, in the same run.