Gray Code
A binary ordering where consecutive values differ in exactly one bit, avoiding the multi-bit glitches of normal counting. The nth Gray code is simply n XOR (n >> 1).
- Category
- Bit Manipulation
- Time complexity
- O(1) per
- Space complexity
- O(1)
Pseudocode
gray(i) = i XOR (i >> 1) consecutive codes differ by 1 bit
Reference implementation
def gray(i):
return i ^ (i >> 1)
# 0,1,3,2,6,7,5,4 for 3-bit