Brian Kernighan's Algorithm
n and (n - 1) wipes the lowest set bit, so the loop runs once per 1 bit.
Decision · step 2 of 6Bit Manipulation: Count the 1s, Kernighan style
178 and 177 = 176. Subtracting 1 borrows through the trailing zeros, so the AND wipes exactly the lowest 1, at bit 1. That is round 1.
What you will see
Each step the lowest one disappears; the count increments.
Cost
| Best | O(1) |
|---|---|
| Average | O(set bits) |
| Worst | O(log n) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, run it on your own input, try operations in any order.
Screen readers: Each bit announces its position and value; each step announces the operation and the resulting number in binary and decimal.
Reduced motion: Bits flip with a crossfade; masks appear in place.
Before this
Related
Taught by the same lesson
Bit Manipulation covers these too, in the same run.