Gray Code: Generating Sequences Where Neighbours Differ by One Bit

A Gray code orders all n-bit numbers so that consecutive values differ in exactly one bit. "Generate the Gray code sequence for n bits" is a short interview question with a satisfying one-line answer, and good follow-ups.

The formula

The i-th reflected binary Gray code is i ^ (i >> 1).

def gray_code(n):
    return [i ^ (i >> 1) for i in range(1 << n)]

# n = 3 -> [0, 1, 3, 2, 6, 7, 5, 4]
#          000 001 011 010 110 111 101 100

Why it works

Going from i to i + 1 in binary flips a block of trailing ones to zeros and one zero to a one. XOR with the right shift cancels that whole block except for a single bit, so only one bit of the Gray code changes.

The reflection construction

Gray codes for n bits = the (n−1)-bit list, followed by the same list reversed with the top bit set. Explaining this shows you understand the structure, not just the trick.

def gray_reflect(n):
    res = [0]
    for b in range(n):
        res += [x | (1 << b) for x in reversed(res)]
    return res

Converting Gray back to binary

Each binary bit is the XOR of all Gray bits above and including it:

def gray_to_binary(g):
    b = 0
    while g:
        b ^= g
        g >>= 1
    return b

Follow-ups interviewers ask

• Start from a given value: XOR every code with the start value: the one-bit-difference property is preserved ("circular permutation in binary representation").
• Cyclic property: the last and first codes also differ by one bit, so the sequence is a Hamiltonian cycle on the n-dimensional hypercube.
• Backtracking version: DFS over numbers, flipping one bit at a time and skipping visited values, which is useful when the interviewer bans the formula.

Where Gray codes are used

Rotary encoders and other sensors (a misread during a transition is off by at most one step), safe counters crossing clock domains in hardware design, Karnaugh map ordering, and some genetic algorithm encodings.

Disclosure: I work on Linkjob AI, an AI interview assistant. These are general practice notes.