The formula
Converting a plain binary number n to its Gray codeword is one instruction:
g = n XOR (n >> 1)
Take the number, shift it right one bit, exclusive-OR the two. Each Gray bit says whether the corresponding pair of adjacent binary bits disagree — which is why exactly one Gray bit flips when n steps to n+1.
Going back is where the asymmetry lives. Each binary bit is the running XOR of all Gray bits above it:
b(k) = g(N−1) XOR g(N−2) XOR … XOR g(k) — from the MSB down
In code, the fast version is a shift-XOR cascade — for a 16-bit word:
b = g; b ^= b >> 1; b ^= b >> 2; b ^= b >> 4; b ^= b >> 8;
The 3-bit sequence, worth memorizing because it shows up on every encoder datasheet:
n: 0 1 2 3 4 5 6 7
bin: 000 001 010 011 100 101 110 111
Gray: 000 001 011 010 110 111 101 100
Read down the Gray row — every neighbor differs in one bit, and the last entry (100) is one bit away from the first (000). The code is cyclic. That wrap-around is free, and it is why the code works on a rotating disk.
Where you meet it
- Absolute rotary encoders on the test stand. A 10-bit optical encoder disk etched in plain binary has a spot — count 511 to 512 — where all ten tracks change at once (
0111111111to1000000000). Real tracks are never aligned to better than a few arc-minutes, so mid-transition the read head can report any of 1,024 positions. The same disk etched in Gray code changes one track per step, and the worst possible misread is the adjacent count. Every absolute encoder you will ever mount on a gimbal or antenna positioner uses it for exactly this reason. - Clock-domain crossings in FPGA review. An asynchronous FIFO passes its read and write pointers between two clock domains. Pass a binary pointer and a metastable capture during a multi-bit change can produce a wildly wrong value; pass a Gray-coded pointer and the captured value is either the old count or the new one — never garbage. When the review board asks how the CDC is protected, "Gray-coded pointers plus two-flop synchronizers" is the expected answer, and its absence is a finding.
- RF link design. QAM and PSK constellations are Gray-mapped so that the most likely symbol error — falling into an adjacent decision region — corrupts only one bit of the symbol. That mapping is baked into essentially every modem standard you will test against, and it is why measured BER runs close to symbol error rate divided by bits per symbol at high SNR.
- Karnaugh maps. The row and column ordering
00, 01, 11, 10on every K-map you drew in school is the 2-bit Gray sequence. It is what makes adjacent cells differ in one variable so groupings correspond to legal simplifications.
How it works
The construction that gives the code its older name is reflection. Take the 1-bit list 0, 1. Write it forward, then write it again in reverse — the mirror image — and prefix the first half with 0, the second half with 1:
0, 1 → 00, 01, 11, 10 → 000, 001, 011, 010, 110, 111, 101, 100
The reflection is doing the work: at the seam, only the new prefix bit changes, and inside each half the property is inherited from the previous stage. Repeat to any width. This is the "reflected binary" — and it is also what n XOR (n >> 1) computes in closed form.
What you buy: bounded transition error. In plain binary, the number of bits that flip between n and n+1 is unbounded short of the word width — 7 to 8 flips four bits, 511 to 512 flips ten. Any physical system that samples those bits with slightly different timing — encoder read heads, flash-ADC comparator banks, flip-flops on an async boundary — can catch some bits old and some new, producing a code that was never valid. Gray code makes every transition atomic by construction: one bit is in flight, so the only two readable values are the two legitimate neighbors.
What you give up: arithmetic. Gray codewords do not add, compare, or subtract meaningfully — g(2) = 011 is numerically larger than g(3) = 010. The universal pattern is Gray on the wire or the disk, binary in the ALU, with the shift-XOR decode at the boundary. An async FIFO computes "full" and "empty" by comparing Gray pointers directly, but that works only because of a specific known relationship between the two, not because Gray codes order naturally.
The limits worth respecting:
- The guarantee covers unit steps only. A shaft that moves two counts between samples changes two bits, and you are back to needing a sample rate that keeps the step size at one. Gray code is not a substitute for sampling fast enough.
- Truncate from the middle, not from the end. The reflected code is cyclic over
2^Nstates, and the lazy way to get 360 counts — take codewords 0 through 359 of the 9-bit sequence — breaks at the splice: the wrap from count 359 back to count 0 flips five bits, the exact glitch the disk was built to avoid. The standard remedy is on every absolute-encoder datasheet: cut symmetrically about the code's reflection axis instead, using codewordsg(76)throughg(435)— drop 76 from each end of the 512. The mirror symmetry of the reflected construction guarantees the two cut ends differ in exactly one bit, so the wrap is as clean as every other step. This "excess Gray" trick yields a cyclic single-bit-change code for any even length; no such code exists for an odd length, because a closed cycle of single-bit flips must contain an even number of steps to return every bit to its starting value. - The classic field mistake is treating a Gray-coded register as a number. A telemetry word from an encoder gets logged raw, someone plots it, and the plot shows sawtooth discontinuities that look like a slipping coupling. The hardware is fine; the decode step is missing. Ten minutes with
b ^= b >> kbeats a day of chasing a mechanical fault that does not exist. - One-bit-per-step is not error detection. A single flipped bit in a Gray codeword is another perfectly valid codeword one count away. If corruption matters, you still need parity or CRC on top.
History
The name on the code belongs to Frank Gray, a physicist at Bell Telephone Laboratories. In November 1947 he filed a patent titled "Pulse Code Communication," describing a vacuum-tube apparatus that digitized analog signals directly into a code with the one-bit-per-step property, so that a converter caught between levels could only err by one count. Gray noted the code "has as yet no recognized name" and christened it the reflected binary code, after the mirror construction; the patent, US 2,632,058, was granted on March 17, 1953, and the community promptly ignored his name for it and used his instead [1][2].
The idea is much older than the patent. Émile Baudot, the French telegraph engineer whose name survives in "baud," used a reflected-binary-style ordering in his printing telegraph work in 1878, decades before anyone had an electronic use for it [2][3]. Older still: in 1872 Louis Gros, a notary's clerk in Lyon, published a pamphlet analyzing the baguenaudier — the Chinese rings puzzle — and showed that the sequence of ring moves that solves it is exactly this counting sequence. The mathematics was worked out for a parlor toy seventy-five years before Bell Labs needed it for pulse-code modulation [2][4].