Gray code (reflected binary code) orders the 2ⁿ binary values so that any two consecutive codes differ in exactly one bit. It was patented by Frank Gray in 1953.

XOR formula

The Gray code of integer b is g = b XOR (b >> 1). To invert, fold the shifts back: b = g XOR (g>>1) XOR …

Reflect-and-prefix construction

Start with the 1-bit list [0, 1]. To go from n to n+1 bits: take the list, write its reflection (reversed copy) below it, prefix every code in the top half with 0 and every code in the bottom half with 1. The single-bit-change property is preserved at the mirror seam.

Hamiltonian path on the n-cube

Treat each code as a vertex of the n-dimensional hypercube; edges join codes that differ in one bit. A Gray-code sequence is exactly a Hamiltonian path — it visits every vertex once, stepping along one edge at a time.

Applications

• Rotary / position encoders — one bit changes per step, so a misaligned reading can be off by at most one position instead of a wild multi-bit glitch.
• Karnaugh maps — rows and columns are Gray-ordered so adjacent cells differ in one variable.
• Genetic algorithms & error reduction — small value changes map to small bit changes.