Lowest Set Bit
n and -n keeps only the lowest 1. It is the step a Fenwick tree takes.
Result · step 2 of 2Bit Manipulation: Isolate the lowest 1
88 and -88 = 8, which is bit 3 alone. This is the step a Fenwick tree takes to find its parent.
What you will see
Two's complement of n lines up under n; AND leaves a single bit.
Cost
| Best | O(1) |
|---|---|
| Average | O(1) |
| Worst | O(1) |
| 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.