One bit at a time
A Gray code is an ordering of all binary numbers of a given width in which consecutive values differ by exactly one bit. Standard binary counting can flip many bits at once, for example three to four flips three bits; Gray code never does, changing only a single bit per step.
Building it
Two clean methods exist:
- Reflect and prefix: take the Gray code for one fewer bit, write it forward with a leading zero, then write it backward with a leading one. The reflection guarantees the join in the middle differs by only the new high bit.
- Formula: the Gray code of a number is that number combined with itself shifted right by one position using exclusive or. This converts a binary index directly into its Gray value.
Converting back from Gray to binary is also simple, accumulating exclusive ors from the high bit down.
Why it matters
- Mechanical and optical encoders use Gray code so a misread during a transition changes the reading by at most one step.
- It reduces glitches in state transitions where only one bit should change at a time.
- It generates subsets where each differs from the last by adding or removing one element.
Key idea
Gray code orders binary values so each consecutive pair differs in one bit; build it by reflecting and prefixing or by combining a number with its right shift using exclusive or, which makes encoders and transitions robust to single bit errors.