Glossary
What is a Gray code?
A Gray code lists all 2^n binary strings of length n so that consecutive strings differ in exactly one bit. The standard one, the binary reflected Gray code, has a one-line formula: the k-th code word is k XOR (k >> 1).
Why one bit at a time matters
In hardware, a rotary encoder that reports position in Gray code can never read a wildly wrong value mid-transition, because only one bit is changing. In software, generating subsets in Gray code order means each step adds or removes one element, so you can update a running total in constant time instead of recomputing it.
Where it is taught
Knuth opens Volume 4A's generation chapter with it in §7.2.1.1, Generating All n-Tuples: the reflected code and its properties, loopless generation (constant time per step, not just on average), other Gray codes for mixed radices, and de Bruijn cycles. The idea of changing one thing per step returns for permutations and combinations in the sections after.
Questions
Who is it named after?
Frank Gray of Bell Labs, who patented its use in 1953, though the reflected code was known earlier (it solves the Chinese ring puzzle).
How do I convert Gray code back to binary?
XOR the code with all its right shifts: b = g ^ (g >> 1) ^ (g >> 2) ^ ..., which takes log n steps with doubling shifts.