Gray Code
g = n xor (n shr 1). Each row of codes flips exactly one bit of the row above.
Bit 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.
Cost
- Best
- O(1)
- Average
- O(1)
- Worst
- O(1)
- Space
- O(1)
Before this
Taught by the same lesson
Bit Manipulation covers these too, in the same run.