Gray Code

May 2026 · 20 min read

A Gray code orders bit strings so consecutive values differ in exactly one bit. This property is useful for hardware encoders, subset traversal, hypercube walks, and interview problems that ask you to generate a special ordering of all masks.

Definition

An n-bit Gray code sequence contains all 2^n bit strings exactly once, and adjacent strings differ by one bit. A cyclic Gray code also makes the last and first strings differ by one bit.

n = 2:
00, 01, 11, 10

00 -> 01 changes bit 0
01 -> 11 changes bit 1
11 -> 10 changes bit 0
10 -> 00 changes bit 1

Binary to Gray

The standard reflected Gray code maps integer x to:

gray = x ^ (x >> 1)

Why it works: each Gray bit says whether adjacent binary prefix bits differ. As x increments, carry propagation changes a suffix, but the Gray representation changes only at the boundary.

vector<int> gray_code(int n) {
    vector<int> ans;
    for (int x = 0; x < (1 << n); ++x) {
        ans.push_back(x ^ (x >> 1));
    }
    return ans;
}

Gray to Binary

Recovering binary requires prefix XOR from the most significant side. Repeatedly XOR the Gray value with itself shifted right.

int gray_to_binary(int g) {
    int x = 0;
    while (g) {
        x ^= g;
        g >>= 1;
    }
    return x;
}

gray:   1101
binary: 1001

bit 3 = 1
bit 2 = 1 ^ 1 = 0
bit 1 = 0 ^ 0 = 0
bit 0 = 0 ^ 1 = 1

Reflective Construction

You can also build Gray code recursively: take the (n-1)-bit sequence, prefix 0 to it, then traverse it backward and prefix 1.

n = 1: 0, 1
n = 2: 00, 01, 11, 10
n = 3: 000, 001, 011, 010, 110, 111, 101, 100

Hypercube Intuition

All n-bit strings are vertices of an n-dimensional hypercube. Two vertices share an edge if they differ in one bit. A Gray code is a Hamiltonian cycle or path through that hypercube.

This view helps in constructive problems: if the required move changes one bit, think about walking a hypercube.

Applications

• Subset enumeration with small updates: consecutive masks differ by one element, so you can update a maintained value incrementally.
• Hardware encoders: one-bit transitions reduce ambiguity during physical state changes.
• Interview generation: LeetCode 89 is the direct reflected-code construction.
• Hypercube paths: many constructive bit problems hide a Gray-code ordering.

Pitfalls

• Gray code order is not numeric order.
• For n >= 31, 1 << n overflows an int; use 64-bit values or avoid materializing the full sequence.
• Generating all Gray codes is O(2^n), so constraints must be small.

Practice Problems

• LeetCode 89 - Gray Code generation use i ^ (i >> 1) or reflection.
• LeetCode 1238 - Circular Permutation in Binary Representation rotation start the Gray cycle from a given value.
• CSES - Gray Code printing output all n-bit strings in Gray order.