Gray Code

An ordering of all $2^n$ binary strings in which consecutive strings differ in exactly one bit.

The standard (reflected binary) Gray code

$G(i)=i\oplus (i\gg 1).$

int gray(int i)    { return i ^ (i >> 1); }
 
int inverseGray(int g) {                       // recover i from G(i)
    for (int b = g >> 1; b; b >>= 1) g ^= b;
    return g;
}
// or: while (g >>= 1) i ^= g;

Both are $O(\log n)$; the forward direction is $O(1)$.

i : 0 1 2 3 4 5 6 7
G : 0 1 3 2 6 7 5 4
bin 000 001 011 010 110 111 101 100

Why it works

$G(i)$ and $G(i+1)$ differ in exactly the bit at position $\mathrm{ctz}(i+1)$ — the lowest set bit of $i+1$. The XOR-with-shift construction “reflects” each half of the sequence, which is exactly the recursive definition:

$G_n=\left(0G_{n-1}\right)\Vert (1\mathrm{reverse}(G_{n-1})).$

Properties

Property
Consecutive codes differ in 1 bit	by construction
Cyclic: $G(2^n-1)$ and $G(0)$ also differ in 1 bit
The bit that changes from $i$ to $i+1$ is $\mathrm{ctz}(i+1)$
$G$ is a bijection on $[0,2^n)$
$\mathrm{popcount}(G(i))$ has no simple form	but parity does: it equals the parity of $i$‘s bit-count in a shifted sense

Where it is used

Hardware and encoding

Rotary encoders and analogue-to-digital converters use Gray code so that a reading caught mid-transition is off by at most one step, rather than producing an arbitrary value (as binary would when 0111 → 1000 flips four bits).

Karnaugh maps

Rows and columns are labelled in Gray code so that adjacent cells differ in one variable — which is what makes visual minimisation of boolean functions work.

Hamiltonian path on the hypercube

The Gray code sequence is a Hamiltonian cycle on the $n$-dimensional hypercube $Q_n$, where vertices are bit strings and edges join strings differing in one bit. Any problem asking to “visit all $2^n$ subsets changing one element at a time” is asking for a Gray code.

Enumerating subsets with incremental updates

When a DP or a search must visit all $2^n$ subsets and updating the state for one element is much cheaper than recomputing from scratch, iterate in Gray-code order:

for (int i = 0; i < (1 << n); i++) {
    int g = gray(i);
    if (i) {
        int bit = __builtin_ctz(i);              // the bit that changed
        if (g >> bit & 1) add(bit); else remove(bit);
    }
    process(g);
}

$O(2^n)$ total updates instead of $O(2^{n}n)$ — a real saving when add/remove are expensive (matrix updates, connectivity changes, geometric structures).

Tower of Hanoi

The $i$-th move of the optimal solution moves disk $\mathrm{ctz}(i)$ — exactly the bit that changes in the Gray code. The whole solution is a Gray code walk. See Tower of Hanoi.

Variants

• $k$-ary Gray code — for base $b$: consecutive strings differ by $\pm 1$ in one digit.
• Balanced Gray code — each bit changes roughly equally often.
• Monotone Gray code — bit changes follow a monotone pattern.
• Snake-in-the-box — the longest induced path in a hypercube; an open combinatorial problem.

Contest appearances

Direct Gray-code problems are uncommon, but the underlying facts recur:

• “arrange these $2^n$ items so consecutive ones differ minimally” → Gray code;
• “enumerate all subsets with $O(1)$ incremental updates” → Gray code order;
• “the $i$-th move of Hanoi” → __builtin_ctz(i);
• “hypercube Hamiltonian path” → Gray code;
• “minimum bit flips to enumerate all states” → exactly $2^n-1$, achieved by Gray code.

See also: Enumerating Submasks · Tower of Hanoi · Bit Manipulation