Gray Codes

Imagine a rotary shaft connected to a sensor. As the shaft turns, the sensor reads the angle and outputs it as a binary number. At the moment the angle crosses from 3 (binary 011) to 4 (binary 100), all three bits must flip simultaneously. In practice they never flip at the exact same instant — for a tiny moment the sensor can read 000, 001, 010, 100, or something else entirely. Any device downstream sees a glitch: a spurious, wrong value that can trigger the wrong action.

Frank Gray, a physicist at Bell Labs, patented the solution in 1947 and it bears his name: order the binary strings so that consecutive values differ in exactly one bit. Then the transition from 3 to 4 touches only a single bit. Only one bit changes, so there is no window in which two different bits are mid-flight and the output is undefined.

This deceptively simple idea connects to a beautiful structure in combinatorics: a Hamiltonian path on the hypercube graph whose vertices are all n-bit strings and whose edges connect strings that differ in one bit. The standard 4-bit Gray code visits all 16 vertices of a 4-dimensional hypercube, stepping along exactly one edge at a time.

The construction is recursive. The 1-bit Gray code is just [0, 1]. To get the n-bit code, write the (n–1)-bit code forward, then backward, and prepend 0 to the forward half and 1 to the backward half. This reflected binary code is the most common Gray code and can be computed in closed form: to convert an ordinary binary number $b$ to its Gray code, simply compute b XOR (b >> 1).

Step through the 4-bit Gray code below. Each row shows the decimal value, its standard binary representation, and its Gray code representation. Watch the highlighted bit column — only one bit changes on each step.

<p class="hint">
  {{hint}}
</p>
<div id="table-wrap">
  <table id="gray-table">
    <thead>
      <tr>
        <th>{{th_decimal}}</th>
        <th class="b3">{{th_bit3}}</th>
        <th class="b2">{{th_bit2}}</th>
        <th class="b1">{{th_bit1}}</th>
        <th class="b0">{{th_bit0}}</th>
        <th>{{th_binary}}</th>
        <th>{{th_gray}}</th>
        <th>{{th_formula}}</th>
      </tr>
    </thead>
    <tbody id="tbody"></tbody>
  </table>
</div>
<div class="controls">
  <button id="prev" type="button">{{btn_prev}}</button>
  <button id="next" type="button">{{btn_next}}</button>
  <button id="play" type="button">{{btn_autoplay}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="info" id="info"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
#table-wrap { overflow-x: auto; }
table { border-collapse: collapse; width: 100%; min-width: 420px; }
th, td { padding: .3rem .55rem; text-align: center; border: 1px solid #dde3ea; }
th { background: #e8eef3; font-weight: 700; font-size: .82rem; }
td { font-family: ui-monospace, monospace; font-size: .93rem; }
td.dec { font-family: system-ui, sans-serif; font-weight: 600; color: #1d3557; }
td.bin, td.gray, td.formula { letter-spacing: .06em; }
tr.active { background: #e4f0ff; }
td.changed { background: #ffd166; color: #1d1d1d; border-radius: 4px; font-weight: 700; }
td.prev-changed { background: #ffe8a0; }
.b3, .b2, .b1, .b0 { width: 52px; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .8rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.info { margin-top: .55rem; font-size: .88rem; font-weight: 600;
        color: #0a7d33; min-height: 1.3em; }

// Code not found

Notice that ordinary binary counting frequently flips multiple bits at once (3→4 flips three bits). The Gray code never does. At every step, exactly one bit flips — that is the whole point. The demo also shows the closed-form conversion formula: Gray = n XOR (n >> 1).

The standard reflected binary Gray code is solved — constructing it takes $O(2^{n})$ time and $O(n)$ space per step with the XOR formula. But Gray codes live inside a richer landscape.

• Standard construction: trivial. The formula Gray(n) = n XOR (n >> 1) converts any integer in constant time. The recursive reflection construction generates the full sequence in linear time. There is no open question about computing the standard code.
• Hamiltonian path on the hypercube. The n-bit Gray code is exactly a Hamiltonian path on the n-dimensional hypercube graph $Q_{n}$ (vertices = n-bit strings; edges = pairs differing in one bit). For the plain hypercube, Hamiltonian paths and cycles are easy to find by reflection. But the moment you add constraints — "avoid this subset of vertices", "maintain this ordering on certain coordinates" — you are asking whether a constrained Hamiltonian path exists, which is NP-complete in general.
• Monotone and balanced Gray codes. Researchers have studied Gray codes that have extra regularity: each bit position changes the same number of times, or changes only within a fixed range of indices. Constructing these specialized variants is non-trivial and some variants remain active research topics.
• Connection to sorting networks. Listing all permutations of n elements so consecutive permutations differ by one adjacent swap is a "permutation Gray code" — closely related to sorting and combinatorial generation.

The key insight for complexity: the single-bit-change property defines a path in a graph. Imposing additional structure on that path quickly crosses into NP-hard territory, which is why the field of combinatorial generation — of which Gray codes are a flagship example — continues to produce hard open problems.

The single-bit-change property is remarkably useful across engineering and mathematics:

• Rotary encoders. Absolute rotary position sensors output the shaft angle as a binary number. Using Gray code instead of binary ensures that at every angle boundary, only one track changes state — eliminating the glitch states that standard binary produces.
• Analog-to-digital converters. Some ADC designs convert signals through a sequence of comparisons. Gray coding the output stages minimizes the number of bits that must switch simultaneously, reducing switching noise.
• Karnaugh maps. The rows and columns of a Karnaugh map (K-map) are labeled in Gray code order so that adjacent cells differ by one variable. This is what makes K-maps work: adjacent minterms — which correspond to logic simplifications — sit next to each other on the map.
• Error-correcting codes. The binary-reflected Gray code is the basis of several distance-1 codes and appears in the construction of certain cyclic codes.
• The Tower of Hanoi. Moving n disks from peg A to peg C in the Tower of Hanoi puzzle traces exactly the n-bit Gray code: each legal move corresponds to flipping the bit in the current position that produces the next Gray code word. The optimal solution visits $2^{n}$ − 1 moves, corresponding to the $2^{n}$ − 1 edges of the Hamiltonian path.
• Combinatorial generation. Gray codes are the canonical example of generating combinatorial objects (subsets, permutations, combinations) in a "minimal change" order — one swap, one addition, or one deletion per step. Libraries of combinatorial algorithms rely on these orderings for efficiency.

See also the related ideas of sorting networks and the deeper question of P vs NP that lurks when you add constraints.

Frank Gray's insight was almost embarrassingly simple: count in an order where only one bit changes at a time. Yet that idea threads through rotary encoders, Karnaugh maps, the Tower of Hanoi, and the theory of Hamiltonian paths on hypercubes.

The standard reflected binary Gray code is completely solved — a one-liner XOR formula generates it in constant time per step. But the moment you impose extra structure on the sequence, you are asking about constrained Hamiltonian paths, and that question lives in the same hard territory as P vs NP.

Gray codes are a reminder that elegant, solved problems at the center of computer science sit right next to open, hard ones. One extra constraint can take you from a solved problem to an unsolved research frontier.