1. One-Liner
Gray code orders binary numbers so successive values differ in exactly one bit—reflection construction g = i ^ (i>>1).
2. The Problem It Solves
Used in rotary encoders, Karnaugh maps, error reduction in switching, and minimizing glitches.
3. The Core Idea
Binary to Gray XORs with half-shifted copy—each step flips the bit where binary carry propagates.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | For i in 0..2^n-1 |
| 2 | g = i ^ (i >> 1) |
| 3 | Collect sequence |
5. Dry Run Example
n=2: 00,01,11,10—each hop toggles one bit.
6. Key Properties
| Property | Detail |
|---|---|
| Hamming distance | 1 between neighbors |
| Cyclic | Wrap may differ requirement |
| Inverse | Binary Gray decoding exists |
7. Where It Is Used
| Domain / System | Use |
|---|---|
| Hardware | Encoders |
| Digital | K-maps |
| Algorithms | Hamiltonian on hypercube |
8. Interview Tips
Know n-bit reflected construction recursively; streaming parity relations optional depth.
9. Comparison with Other Algorithms
| Technique | Notes |
|---|---|
| Binary counting | Many bit changes |
| Johnson counter | Hardware alternative |
| De Bruijn | Different sequence |
10. Complexity
| -- | -- |
|---|---|
| Time | O(2^n) to list all |
| Space | O(2^n) output |
Implementation Example (PYTHON)
def gray_code(n):
return [i ^ (i >> 1) for i in range(1 << n)]