Sign in to watch this lesson
Algorithms - Bits and Number Theory · 3:13
Gray Code
A Gray code lists every n-bit word so that neighbours differ in exactly one bit, which is a walk along the edges of a cube that visits every corner once. We build it by reflect-and-prefix, encode with g = i ^ (i >> 1) (G(4) = 110 = 6), and decode with a running XOR from the top bit, not the tempting g ^ (g << 1). Then the surprise: in the shortest Towers of Hanoi solution, the bit that flips at step k is the disk that moves, ctz(k) + 1, and the smallest disk always cycles the same way round.
You will learn
- Explain the defining property of a Gray code and see it as a Hamiltonian walk on the n-dimensional cube.
- Build the n-bit Gray sequence by reflect-and-prefix and with the closed form g = i ^ (i >> 1).
- Decode a Gray word back to its index with a running XOR from the top bit, in O(log n) steps, and avoid the wrong one-shift inverse.
- Use the Gray-code / binary-counter link to solve Towers of Hanoi without recursion: disk ctz(k) + 1 moves at step k.