ii. Gray Code

An ordering of all $2^n$ bit strings where consecutive strings differ in exactly one bit. It’s a Hamiltonian cycle of the hypercube, and it lets you enumerate subsets with one insertion or deletion per step.

Reflected binary code

$G(i)=i\oplus (i\gg 1),G_n=0G_{n-1}\Vert 1\overline{G_{n-1}}\text{ (reflected)}.$

unsigned gray(unsigned i) { return i ^ (i >> 1); }
unsigned grayInverse(unsigned g) { for (unsigned s = g >> 1; s; s >>= 1) g ^= s; return g; }
// or in O(log w): g ^= g >> 1; g ^= g >> 2; g ^= g >> 4; g ^= g >> 8; g ^= g >> 16;

• $G(i)$ and $G(i+1)$ differ in bit $\mathrm{ctz}(i+1)$.
• The sequence is cyclic: $G(2^n-1)=2^{n-1}$ differs from $G(0)=0$ in one bit.
• $\mathrm{popcount}(G(i))\equiv$ parity of the step count $i$, since each step flips exactly one bit.
• Tower of Hanoi: move $i$ moves disk $\mathrm{ctz}(i)$, the same bit that changes in the Gray code.

Proof: $G$ is a bijection with the one-bit-step and decoding properties

One-bit step. Let $k=\mathrm{ctz}(i+1)$. Binary increment gives: for $j<k$, bit $j$ of $i$ is $1$ and of $i+1$ is $0$; bit $k$ of $i$ is $0$ and of $i+1$ is $1$; for $j>k$, the two agree. Bit $j$ of $G(x)=x\oplus (x\gg 1)$ is $x_j\oplus x_{j+1}$. For $j>k$: both $x_j$ and $x_{j+1}$ agree between $i$ and $i+1$ (either both above $k$, or $j=k+1$ where bit $k+1$ is also unchanged by the increment), so $G(i{)}_j=G(i+1{)}_j$. For $j<k-1$: $i_j=i_{j+1}=1$ gives $G(i{)}_j=0$, and $(i+1{)}_j=(i+1{)}_{j+1}=0$ gives $G(i+1{)}_j=0$ — equal. For $j=k-1$ (when $k\ge 1$): $i_{k-1}=1,i_k=0$ gives $G(i{)}_{k-1}=1$, and $(i+1{)}_{k-1}=0,(i+1{)}_k=1$ gives $G(i+1{)}_{k-1}=1$ — equal. At $j=k$: $i_k=0,i_{k+1}$ gives $G(i{)}_k=i_{k+1}$, and $(i+1{)}_k=1,(i+1{)}_{k+1}=i_{k+1}$ gives $G(i+1{)}_k=1\oplus i_{k+1}$ — these differ. So $G(i)\oplus G(i+1)$ has exactly bit $k$ set. Bijection. $i\mapsto i\oplus (i\gg 1)$ has a two-sided inverse: the loop for s=g>>1; s; s>>=1: g^=s recovers $i$ top bit down, since $i_t=g_t\oplus i_{t+1}$ (from $g=i\oplus (i\gg 1)$) and by the time bit $t$ is XORed, s carries exactly the already-recovered bit $t+1$ of $i$ shifted into position. A function on a finite set with a two-sided inverse is a bijection, hence a permutation of $[0,2^n)$; combined with the one-bit-step property, $G(0),\dots ,G(2^n-1)$ is a Hamiltonian path on the hypercube $Q_n$. Cyclic. $G(2^n-1)\oplus G(0)=(2^n-1)\oplus (2^{n-1}-1)\oplus 0=2^{n-1}$, a single bit, so the last and first codes also differ in exactly one bit, closing the path into a Hamiltonian cycle. $■$

Tested: gray/grayInverse/the $O(\log w)$ unrolled inverse all checked against a full enumeration of $i\in [0,2^{16})$ — range, bijectivity (no collisions), round-trip inverse, single-bit adjacency with the predicted $\mathrm{ctz}$ position, and the cyclic wraparound.

Enumerating subsets with $O(1)$ updates

for (unsigned i = 0; i < 1u << n; i++) {
    if (i) { int b = __builtin_ctz(i); (gray(i) >> b & 1) ? add(b) : remove(b); }
    process(gray(i));
}

That’s $2^n-1$ single-element updates instead of $n{2}^n$. Useful when inserting or removing one element is expensive: maintaining a matrix product, a determinant via rank-one updates, a convex hull, or computing the permanent with Ryser’s formula in $O(2^{n}n)$ (Permanent).

Variants and facts

• $k$-ary reflected Gray code: consecutive strings differ by $\pm 1$ in one digit. Generate by reflecting digit order like the binary case.
• Gray code over a subset lattice of fixed size (revolving door / combinations differing by one swap): enumerate all $k$-subsets with one element swapped out and one in per step.
• Hamiltonian cycle on $Q_n$ with a prescribed start: XOR every code with the start.
• Hamiltonian path in a hypercube between two vertices: exists iff they have different parity (bipartite), and a recursive construction splits on a coordinate where they differ.
• Minimum number of single-bit flips to visit all $2^n$ states: $2^n-1$, attained by Gray code.
• Balanced Gray code: a variant where every bit position changes roughly the same number of times across the whole cycle, rather than the reflected code’s heavy skew toward the low bits. Monotone Gray code: one where the sequence of changed-bit positions follows a monotone pattern. Snake-in-the-box: the longest induced path in a hypercube (no two non-consecutive visited vertices adjacent) — an open combinatorial problem in general, unlike the Hamiltonian-cycle question Gray code answers exactly.
• Outside CP: rotary encoders and ADCs use Gray code so a reading caught mid-transition is off by at most one step, instead of the arbitrary garbage ordinary binary gives on a multi-bit flip (e.g. $0111\to 1000$); Karnaugh maps label rows/columns in Gray code so adjacent cells differ in one variable, which is what makes the visual minimisation of boolean functions work.

Proof: the $2^n-1$ lower bound, and the parity condition for a two-endpoint Hamiltonian path

Lower bound. Visiting all $2^n$ distinct states one flip at a time is a walk through $2^n$ vertices, which uses exactly (number of vertices) $-$ 1 $=2^n-1$ edges if no vertex repeats; fewer than $2^n-1$ flips can touch at most $2^n-1$ new states beyond the start, i.e. at most $2^n$ states total only if every flip reaches a genuinely new state, so $2^n-1$ is also necessary, not just sufficient. The Gray code achieves it exactly (it’s a Hamiltonian path, proved above), so $2^n-1$ is tight. Parity. The hypercube $Q_n$ is bipartite by $\mathrm{popcount}(x)\mathrm{mod}2$, since every edge flips one bit and so changes parity by exactly one step. A path alternates between the two parity classes, so a Hamiltonian path from $u$ to $v$ visits $2^n$ vertices alternating parity starting at $\mathrm{par}(u)$; this forces $\mathrm{par}(v)=\mathrm{par}(u)\oplus (2^n-1\mathrm{mod}2)$. For $n\ge 1$, $2^n-1$ is odd, so $\mathrm{par}(v)\ne \mathrm{par}(u)$ is necessary. (Sufficiency is the standard recursive construction: split $Q_n$ into two $Q_{n-1}$ copies by the coordinate where $u,v$ differ, Hamilton-path each half using the inductive hypothesis on the smaller cube, and join them across that one differing coordinate.) $■$

• De Bruijn sequences are the cyclic analogue for windows rather than whole strings (Euler Tours).