Gray Code
g = n xor (n shr 1); each row of codes flips exactly one bit of the row above.
Decision · step 2 of 7Bit Manipulation: Gray codes from 0
n = 1 is 00000001; n shr 1 is 00000000; xor gives 00000001. Against the row above only bit 0 changed, while plain binary flipped 1 bit going from 0 to 1.
What you will see
Successive rows differ in a single flipped 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
Taught by the same lesson
Bit Manipulation covers these too, in the same run.