Count Set Bits
Clear the lowest 1 with n and (n - 1) until nothing is left, counting rounds.
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 one is counted as it is found.
Cost
| Best | O(1) |
|---|---|
| Average | O(log n) |
| 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.