The Count That Never Trips

The trouble with counting

Watch an ordinary binary counter tick over from three to four. The bits read 011, and then, all at once, 100. Three ones vanish and a new one appears: four bits change in a single step. On paper that is fine, the number simply went up by one. But a binary counter is not made of paper. It is made of wires, or magnetic domains, or the light and dark bands on a spinning disc, and those wires do not all switch at precisely the same instant. For a sliver of time, while some bits have flipped and others have not, the counter is showing neither 011 nor 100 but some third pattern that corresponds to no moment in its life. If something reads the counter right then, it reads a number that never happened.

That is not a rare accident at the edges. It is the normal way ordinary counting moves. Look at the odometer above and step it by hand: 0111 to 1000 flips all four bits; 1111 back to 0000 flips all of them again. Roughly every other step flips more than one wire, and the worst steps flip every wire on the board. The value is always correct once things settle. It is the transitions that lie.

Gray code is the fix, and it is almost impossibly clean. It keeps every value a counter needs, the same whole numbers 0 through 2ⁿ−1, but it puts them in a different order, chosen so that any two consecutive entries differ in exactly one bit. Not usually one bit. Always one bit. From the first step to the last, and then around the wrap from the final code back to the start, precisely one wire ever moves. There is no in-between pattern to misread, because there is no in-between: the counter is always either fully in its old state or fully in its new one.

One line of arithmetic

You do not need a lookup table to build it. The Gray code of a number t is

gray(t) = t XOR (t >> 1)

Take the number, shift a copy one place to the right, and XOR the two together. That is the whole recipe, and the console runs it live for every value you step to. It is genuinely a reordering and nothing is lost: the value carried is identical, and you can always recover the plain integer by a prefix-XOR the other way (each bit is the running XOR of all the Gray bits above it). Gray code is the same numbers wearing a different route between them.

The first console makes the contrast literal. The binary row and the gray row carry the same count t, and the cells that changed since the last step are lit. The binary row flares, sometimes the whole row at once. The gray row lights exactly one cell, every single time. The readout keeps the score: over one full turn of a w-bit wheel, Gray code flips its bits 2ʷ times, once per step, the least any cyclic counter possibly could; binary flips them 2ʷ⁺¹ − 2 times, climbing toward twice as much churn as the count gets wider. Half the motion, none of the phantoms.

There is a small, exact bonus hiding in that gray row, and it is an old friend. The single bit that flips at step t is bit number trailingZeros(t): the smallest wheel turns every step, the next every second step, the next every fourth, a ruler laid along the number line. That is the very same ruler sequence that names which disk moves at step t of the Tower of Hanoi. The puzzle and the odometer are not merely similar. They are running the identical script, one in disks and one in bits.

The mirror that makes it

Why does exactly one bit ever move? The formula proves it, but the reason is a construction you can see, and it is where the name comes from. To build the list for w bits, take the finished list for w−1 bits, write it out, and then write it again upside down underneath. Put a 0 in front of every entry in the top copy and a 1 in front of every entry in the reflection. That is it, and the second console draws it: the top half in muted ink, its mirror image below in ember.

Every join inside the top half was already a single-bit change, because that was the smaller list working correctly, and prefixing a shared 0 cannot break it. The same is true inside the bottom half. The only new join is the seam in the middle, and the mirror makes those two entries identical except for the leading bit, one 0, one 1, so the seam costs exactly one flip too. Reflect a correct list and you get a correct list one size larger. Reflected binary code, hence the ordinary full name.

That reflection has a shape. Every w-bit number is a corner of the w-dimensional cube, and two corners are joined by an edge exactly when their numbers differ in one bit. So a code that changes one bit per step is a walk that crosses one edge at a time and, because every value appears once, visits every corner exactly once before returning home. The panel beside the mirror draws that cube, Q₂ a square, Q₃ the familiar cube, Q₄ a tesseract, with the Gray code lit as a single unbroken loop through all of it. Press walk and follow the dot: it never lifts off an edge, never repeats a corner, and closes the ring at the end. Mathematicians call such a loop a Hamiltonian cycle, and the fact that one exists on every cube, for free, from a one-line formula, is the geometric heart of the whole idea.

The encoder, where it earns its keep

None of this would have a patent if it were only elegant. The third console is the reason Gray code is cut into real hardware. Picture a shaft whose angle you want to measure: you print rings of light and dark bands around it, one ring per bit, and park a row of sensors to read them. The trouble is the one from the very first paragraph, now made of brass and glass. The sensors are never perfectly aligned, and at a boundary where several bands change together, they cross the line at slightly different moments.

Drag the pointer across a binary boundary with the skew turned up. The warn-coloured sensor on each track sits a hair ahead of or behind the true edge, and for an instant the assembled reading is a phantom, flagged in ember, a number that is neither the sector you left nor the one you are entering. Now look at the Gray track doing the same sweep: it never flags. It cannot. Adjacent Gray sectors differ in a single band, so the only thing a misaligned sensor can disagree about is whether that one band has turned yet, and both answers, old value and new value, are honest. The sweep tally makes the gap brutal: across a full rotation, the binary disc spends a large fraction of its travel emitting phantom codes, while the Gray disc emits zero, at any width, at any skew. Slide the skew to zero and the binary phantoms vanish too, which is exactly the point, that is the fantasy of perfect alignment no physical disc enjoys.

This is the problem Frank Gray was solving at Bell Labs in the 1940s, patented in 1953 for pulse-code modulation, the same reflected code that the telegraph pioneer Émile Baudot had already been feeling his way toward in the 1870s. It is why rotary and linear position encoders, from the angle sensors in a 1950s radar dish to the detent knob on a synthesiser, are cut in Gray code to this day. The engineering trick and the beautiful object are one and the same: a way of counting that, because it only ever moves one bit, can never be caught in the middle of a lie.

Notes on how this was made

Everything on the page is recomputed in your browser from gray(t) = t XOR (t >> 1); there are no stored tables. Before the article was written, the three claims were checked offline (47 assertions, 0 failures):

• It is a bijection. For every width up to 10 bits, gray maps 0…2ʷ−1 onto itself with no collisions, and the prefix-XOR grayToBin inverts it exactly.
• One bit, always. Consecutive Gray codes differ in exactly one bit across the full cycle, wrap included, giving 2ʷ flips per turn against binary's 2ʷ⁺¹−2 (the ratio marches to 2). The single flipped bit at step t is trailingZeros(t), the ruler sequence, byte-identical to the Hanoi disk order from #057.
• The mirror is the formula. The reflect-and-prefix construction reproduces the XOR code exactly to 8 bits, and the sequence is a Hamiltonian cycle on the w-cube (every step an edge, every corner once).
• The encoder is honest. Under staggered per-track sensor skew, binary produces spurious phantom codes across a full sweep at every width and skew tested, while Gray produces exactly zero.

The only external facts are settled history: Frank Gray's reflected binary code (Bell Labs, patent filed 1947, granted 1953) and its use in pulse-code modulation and position encoders, with Baudot's 1870s telegraph code as a cyclic-progressive ancestor. This is the coding-theory sequel to the Tower of Hanoi: the same ruler sequence, read as bits instead of disks.