Gray Code

A Gray code is a way to list all $2^n$ binary numbers of $n$ bits so that consecutive numbers (and, cyclically, the last and the first) differ in exactly one bit. It was invented for mechanical encoders: when a sensor moves from one position to the next, only one bit changes, so a misread can only be off by one position rather than producing garbage.

For $n = 3$:

Formula

The $i$-th Gray code is

i.e. each bit is the XOR of the corresponding bit of $i$ with the next higher bit. Consecutive numbers differ only in the lowest few bits of the binary form, and XOR-ing with the shifted copy collapses those changes to a single bit.

def gray(i):
    return i ^ (i >> 1)

codes = [gray(i) for i in range(8)]
assert codes == [0, 1, 3, 2, 6, 7, 5, 4]
n = 10
for i in range((1 << n) - 1):
    assert bin(gray(i) ^ gray(i + 1)).count("1") == 1          # neighbours differ in one bit
assert bin(gray((1 << n) - 1) ^ gray(0)).count("1") == 1        # and it is cyclic
assert sorted(gray(i) for i in range(1 << n)) == list(range(1 << n))     # a permutation

Inverse: from Gray code to the index

Given $g = G(i)$, recover $i$. The highest bit of $i$ equals that of $g$; each next bit of $i$ is the XOR of the next bit of $g$ with the bit of $i$ just found, i.e. the bit of $i$ at position $k$ equals the XOR of all bits of $g$ from position $k$ upwards:

def inverse_gray(g):
    i = 0
    while g:
        i ^= g
        g >>= 1
    return i

assert all(inverse_gray(gray(i)) == i for i in range(1 << 12))
assert inverse_gray(0b110) == 4

Applications

Enumerating all subsets with one change per step

Iterating the subsets of $\{0, \dots, n-1\}$ in Gray order changes one element per step, so a quantity depending on the subset (sum, XOR, count of violated constraints) can be updated in $O(1)$ instead of recomputed in $O(n)$. The bit that flips between step $i$ and $i+1$ is the lowest set bit of $i + 1$.

def subset_sums_gray(values):
    """Sums of all subsets, generated by flipping one element per step."""
    n = len(values)
    total = 0
    sums = [0]
    current = 0                                        # Gray code of the step
    for i in range(1, 1 << n):
        bit = (i & -i).bit_length() - 1                # the element that changes
        current ^= 1 << bit
        total += values[bit] if current >> bit & 1 else -values[bit]
        sums.append(total)
    return sums

vals = [3, 5, 9, 14]
sums = subset_sums_gray(vals)
assert sorted(sums) == sorted(sum(vals[j] for j in range(4) if m >> j & 1) for m in range(16))

Solving puzzles: the Towers of Hanoi and the Chinese rings

The state graph of these puzzles is a Gray code path: the optimal solution visits states in Gray order.

Error resistance in encoders and Karnaugh maps

Adjacent cells of a Karnaugh map differ in one variable because rows and columns are labelled in Gray order.

Generating a Hamiltonian cycle on the hypercube

Consecutive Gray codes are adjacent vertices of the $n$-dimensional hypercube, so the sequence is a Hamiltonian cycle of that graph.

n = 4
edges_in_cycle = {frozenset((gray(i), gray((i + 1) % (1 << n)))) for i in range(1 << n)}
assert len(edges_in_cycle) == 1 << n
assert all(bin(a ^ b).count("1") == 1 for a, b in map(tuple, edges_in_cycle))