Problem Types - Learning Module

Loading content...

0/276

Gray Code

The Code That Changes One Bit at a Time

In 1947, Frank Gray, a researcher at Bell Labs, patented a binary code with a remarkable property: consecutive values differ by exactly one bit. This seemingly simple constraint has profound implications for hardware design, error prevention, and elegant algorithm design.

Consider the problem with standard binary counting:

7 = 0111
8 = 1000

When transitioning from 7 to 8, all four bits change simultaneously. In physical hardware, these bits don't flip at exactly the same instant, creating momentary invalid states. Gray code eliminates this problem entirely by ensuring only one bit ever changes.

The first 8 Gray codes compared with binary:

Binary vs Gray Code (3-bit)
Decimal	Binary	Gray Code	Bits Changed (Binary)	Bits Changed (Gray)
0	000	000	—	—
1	001	001	1	1
2	010	011	2	1
3	011	010	1	1
4	100	110	3	1
5	101	111	1	1
6	110	101	2	1
7	111	100	1	1

What You Will Master

By the end of this page, you will understand why Gray code matters in hardware and algorithms, derive the elegant conversion formulas between binary and Gray code, implement multiple Gray code generation algorithms, and discover its surprising connection to the Towers of Hanoi puzzle.

The Hardware Problem Gray Code Solves

To appreciate Gray code, we must understand the transitional glitch problem in digital hardware.

The problem with multi-bit transitions:

When a binary counter increments from 0111 (7) to 1000 (8), four physical switches or sensors must change state. Due to manufacturing tolerances, they don't change at exactly the same nanosecond. During the transition, the circuit might briefly read:

0111 → 0110 → 0100 → 0000 → 1000  (possible sequence)
   7 →    6 →    4 →    0 →    8  (glitch values!)

If any system samples the value during this transition, it reads garbage—potentially 0, 4, 6, or any intermediate value!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Simulating what happens during multi-bit binary transitions
function simulateTransitionGlitches(from: number, to: number, bits: number): number[] {
    const glitches: Set<number> = new Set();
    
    // Find all bits that change
    const diff = from ^ to;
    const changingBits: number[] = [];
    
    for (let i = 0; i < bits; i++) {
        if ((diff >>> i) & 1) {
            changingBits.push(i);
        }
    }
    
    // Generate all possible intermediate states
    // (all combinations of bits having changed or not)
    const numCombinations = 1 << changingBits.length;
    
    for (let mask = 0; mask < numCombinations; mask++) {
        let intermediate = from;
        for (let j = 0; j < changingBits.length; j++) {
            if ((mask >>> j) & 1) {
                // This bit has already transitioned
                intermediate ^= (1 << changingBits[j]);
            }
        }
        glitches.add(intermediate);
    }
    
    return Array.from(glitches).sort((a, b) => a - b);
}
 
// Transition from 7 to 8 (binary: 0111 → 1000)
console.log("Glitch values 7→8:", simulateTransitionGlitches(7, 8, 4));
// Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
// ANY of the 16 possible 4-bit values could be read!
 
// With Gray code: 0100 → 1100 (Gray 7 → Gray 8)
console.log("Glitch values Gray 7→8:", simulateTransitionGlitches(0b0100, 0b1100, 4));
// Output: [4, 12] - only start and end states possible!

Where This Matters

•Rotary Encoders: Position sensors on motors use Gray-coded disks. If multiple tracks change, momentary misread could indicate wrong position.
•Analog-to-Digital Converters: Flash ADCs use Gray code to prevent glitches in fast-changing signals.
•Clock Domain Crossing: When passing multi-bit values between clock domains, Gray code prevents metastability issues.
•Mechanical Switches: Electromechanical systems where switch contacts don't change simultaneously use Gray code for reliable position sensing.

Gray Code Guarantee

With Gray code, during any transition, exactly one bit changes. The only possible readings are the previous value, the new value, or (during the actual flip) perhaps an undefined single-bit state. Never a completely wrong value like reading 0 when transitioning from 7 to 8!

Mathematical Properties of Gray Code

Gray code has elegant mathematical properties that make it both theoretically beautiful and practically useful.

Key Properties

•Single-bit distance: Adjacent codes (including wraparound from last to first) differ by exactly one bit. This is known as the Hamming distance of 1.
•Cyclic property: The sequence forms a cycle—the last value (e.g., 1000 for 4-bit) differs from the first (0000) by one bit.
•Reflection construction: n-bit Gray code can be built from (n-1)-bit Gray code by reflection (explained below).
•Unique representation: Each value 0 to 2ⁿ-1 appears exactly once in n-bit Gray code sequence.
•XOR relationship: Gray(n) = n ⊕ (n >>> 1). Binary can be recovered with iterative XOR.

The Reflection Construction:

To build n-bit Gray code from (n-1)-bit Gray code:

Take the (n-1)-bit Gray code sequence
Prefix each code with 0
Reverse the sequence and prefix each with 1
Concatenate: original (with 0s) followed by reversed (with 1s)

Example: Building 3-bit from 2-bit Gray code:

Reflection Construction
Step	2-bit Codes	Action	3-bit Result
1	00, 01, 11, 10	Prefix with 0	000, 001, 011, 010
2	00, 01, 11, 10	Reverse list	10, 11, 01, 00
3	10, 11, 01, 00	Prefix with 1	110, 111, 101, 100
4	Concatenate	—	000, 001, 011, 010, 110, 111, 101, 100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function grayCode(n: number): number {
    return n ^ (n >>> 1);
}
 
function verifyGrayProperty(bits: number): boolean {
    const count = 1 << bits;  // 2^bits values
    
    for (let i = 0; i < count; i++) {
        const current = grayCode(i);
        const next = grayCode((i + 1) % count);  // Wrap around
        const diff = current ^ next;
        
        // Check that exactly one bit differs (diff is power of 2)
        const isPowerOfTwo = diff !== 0 && (diff & (diff - 1)) === 0;
        
        if (!isPowerOfTwo) {
            console.log(`Failed at ${i}: ${current} and ${next} differ by ${diff}`);
            return false;
        }
    }
    
    console.log(`✓ All ${count} transitions have Hamming distance 1`);
    return true;
}
 
// Verify for various bit widths
verifyGrayProperty(3);  // 8 values, all adjacent pairs differ by 1 bit
verifyGrayProperty(4);  // 16 values
verifyGrayProperty(8);  // 256 values

The Hamming Connection

Gray code is a special case of a Hamming distance-1 code arranged in a specific sequence. The Hamming distance between two bit strings is the number of positions where they differ. Gray code creates a path through all 2ⁿ n-bit strings where each step has Hamming distance exactly 1. This is also called a Hamiltonian path on the n-dimensional hypercube!

Conversion Between Binary and Gray Code

The conversion between standard binary and Gray code is beautifully simple, requiring just XOR and shift operations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Convert binary number to Gray code
 * 
 * Formula: G = B ⊕ (B >>> 1)
 * 
 * Derivation:
 * - Gray bit g[i] = binary bit b[i] ⊕ b[i+1]
 * - MSB of Gray = MSB of Binary (since b[n] = 0)
 * - Each other bit is XOR of current and next higher binary bit
 */
function binaryToGray(n: number): number {
    return n ^ (n >>> 1);
}
 
// Let's trace through for n = 13 (binary: 1101)
//
// n        = 1101
// n >>> 1  = 0110
// n ^ (n>>>1) = 1011  (Gray code for 13)
//
// Bit-by-bit:
// g[3] = b[3] ^ 0 = 1 ^ 0 = 1  (MSB stays same)
// g[2] = b[3] ^ b[2] = 1 ^ 1 = 0
// g[1] = b[2] ^ b[1] = 1 ^ 0 = 1
// g[0] = b[1] ^ b[0] = 0 ^ 1 = 1
// Result: 1011 ✓
 
console.log("Binary 13 → Gray:", binaryToGray(13).toString(2));  // 1011
 
// Generate Gray codes for 0-15
console.log("\n4-bit Gray codes:");
for (let i = 0; i < 16; i++) {
    const gray = binaryToGray(i);
    console.log(`${i.toString().padStart(2)}: ${i.toString(2).padStart(4,'0')} → ${gray.toString(2).padStart(4,'0')}`);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Convert Gray code to binary number
 * 
 * This is slightly more complex - we need to XOR cumulatively from MSB to LSB
 * 
 * b[n-1] = g[n-1]                    (MSB same)
 * b[n-2] = g[n-1] ^ g[n-2]           (XOR with previous Gray bit)
 * b[n-3] = g[n-1] ^ g[n-2] ^ g[n-3]  (continuing pattern)
 * ...
 * 
 * Or equivalently: b = g ^ (g >>> 1) ^ (g >>> 2) ^ ... ^ (g >>> (n-1))
 */
function grayToBinary(gray: number): number {
    let binary = 0;
    
    // Iterative XOR from MSB to LSB
    for (let g = gray; g !== 0; g >>>= 1) {
        binary ^= g;
    }
    
    return binary;
}
 
// Alternative: fixed number of iterations for known bit width
function grayToBinary32(gray: number): number {
    gray ^= gray >>> 16;
    gray ^= gray >>> 8;
    gray ^= gray >>> 4;
    gray ^= gray >>> 2;
    gray ^= gray >>> 1;
    return gray;
}
 
// Trace for Gray 1011 → Binary 1101
// binary starts at 0
// g = 1011: binary ^= 1011 → binary = 1011
// g = 0101: binary ^= 0101 → binary = 1110
// g = 0010: binary ^= 0010 → binary = 1100
// g = 0001: binary ^= 0001 → binary = 1101  ✓
 
console.log("Gray 0b1011 → Binary:", grayToBinary(0b1011));  // 13
 
// Verify round-trip conversion
for (let i = 0; i < 16; i++) {
    const gray = binaryToGray(i);
    const back = grayToBinary(gray);
    console.assert(back === i, `Failed for ${i}`);
}
console.log("✓ All round-trip conversions verified");

Conversion Formula Summary
Conversion	Formula	Complexity
Binary → Gray	G = B ⊕ (B >>> 1)	O(1)
Gray → Binary (iterative)	Loop: B ^= G; G >>>= 1	O(log n)
Gray → Binary (parallel)	Cascade of XOR shifts	O(log log n) parallel

Generating Gray Code Sequences

There are multiple elegant ways to generate complete Gray code sequences.

1
2
3
4
5
6
7
8
9
10
11
12
13
function generateGrayCodesFormula(bits: number): number[] {
    const count = 1 << bits;  // 2^bits
    const result: number[] = [];
    
    for (let i = 0; i < count; i++) {
        result.push(i ^ (i >>> 1));
    }
    
    return result;
}
 
console.log("3-bit Gray codes:", generateGrayCodesFormula(3));
// Output: [0, 1, 3, 2, 6, 7, 5, 4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function generateGrayCodesReflection(bits: number): number[] {
    if (bits === 0) return [0];
    
    // Start with 1-bit Gray code: [0, 1]
    let codes = [0, 1];
    
    for (let b = 2; b <= bits; b++) {
        const newCodes: number[] = [];
        
        // Original codes prefixed with 0 (they're already like this)
        for (const code of codes) {
            newCodes.push(code);
        }
        
        // Reversed codes prefixed with 1
        const highBit = 1 << (b - 1);
        for (let i = codes.length - 1; i >= 0; i--) {
            newCodes.push(highBit | codes[i]);
        }
        
        codes = newCodes;
    }
    
    return codes;
}
 
console.log("3-bit via reflection:", generateGrayCodesReflection(3));
// Output: [0, 1, 3, 2, 6, 7, 5, 4]
 
// Trace:
// bits=1: [0, 1]
// bits=2: [0, 1] + [10, 11] = [0, 1, 3, 2]
// bits=3: [0, 1, 3, 2] + [110, 111, 101, 100] = [0, 1, 3, 2, 6, 7, 5, 4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function generateGrayCodesBitFlip(bits: number): number[] {
    const count = 1 << bits;
    const result: number[] = [0];
    
    for (let i = 1; i < count; i++) {
        // Which bit to flip? Find the rightmost 1 bit in i
        // This tells us which bit changes from Gray(i-1) to Gray(i)
        const bitToFlip = i & (-i);  // Isolate rightmost set bit
        const position = Math.log2(bitToFlip);
        
        // Toggle that bit in the previous code
        const prev = result[result.length - 1];
        result.push(prev ^ (1 << position));
    }
    
    return result;
}
 
console.log("3-bit via bit flipping:", generateGrayCodesBitFlip(3));
// Output: [0, 1, 3, 2, 6, 7, 5, 4]
 
// The pattern of which bit flips:
// i=1 (001): flip bit 0  → 000 → 001
// i=2 (010): flip bit 1  → 001 → 011
// i=3 (011): flip bit 0  → 011 → 010
// i=4 (100): flip bit 2  → 010 → 110
// i=5 (101): flip bit 0  → 110 → 111
// i=6 (110): flip bit 1  → 111 → 101
// i=7 (111): flip bit 0  → 101 → 100

The Bit-Flip Pattern

The rightmost 1 bit in i tells us which bit to flip! This is because of how binary counting works: bit 0 changes every step, bit 1 every other step, bit 2 every 4 steps, etc. The Gray code transformation converts this to: flip the bit corresponding to the lowest set bit position in the counter.

The Surprising Towers of Hanoi Connection

One of the most elegant discoveries in recreational mathematics is that Gray code solves the Towers of Hanoi puzzle!

The connection:

Each bit in Gray code represents a disk (bit 0 = smallest, bit n-1 = largest)
The bit's value (0 or 1) represents which peg group the disk is on
Walking through Gray codes gives the exact sequence of moves!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
function solveTowersOfHanoi(disks: number): void {
    const totalMoves = (1 << disks) - 1;  // 2^n - 1 moves
    
    console.log(`Solving ${disks}-disk Towers of Hanoi in ${totalMoves} moves:\n`);
    
    // Track peg positions: peg[i] is the peg (0, 1, or 2) where disk i sits
    // Disks are numbered 0 (smallest) to n-1 (largest)
    const peg: number[] = new Array(disks).fill(0);  // All start on peg 0
    
    // Destination for odd vs even total disks
    const destination = disks % 2 === 0 ? 1 : 2;
    
    for (let move = 1; move <= totalMoves; move++) {
        // Which disk moves? The rightmost 1 bit position in move number
        const disk = Math.log2(move & -move) | 0;
        
        // Direction of move alternates based on disk parity and total disks
        // Smallest disk (0) cycles: 0→1→2→0 or 0→2→1→0 depending on n parity
        const fromPeg = peg[disk];
        let toPeg: number;
        
        if (disk === 0) {
            // Smallest disk: cycle in fixed direction
            toPeg = (fromPeg + (disks % 2 === 0 ? -1 : 1) + 3) % 3;
        } else {
            // Other disks: move to the only legal peg
            // (not the current peg, and not where a smaller disk sits)
            for (let p = 0; p < 3; p++) {
                if (p !== fromPeg) {
                    // Check if any smaller disk is on peg p
                    let blocked = false;
                    for (let d = 0; d < disk; d++) {
                        if (peg[d] === p) blocked = true;
                    }
                    if (!blocked) {
                        toPeg = p;
                        break;
                    }
                }
            }
        }
        
        peg[disk] = toPeg!;
        const diskName = `Disk ${disk + 1}`;
        console.log(`Move ${move}: ${diskName} from peg ${fromPeg} to peg ${toPeg!}`);
    }
}
 
solveTowersOfHanoi(3);
/* Output:
Solving 3-disk Towers of Hanoi in 7 moves:
 
Move 1: Disk 1 from peg 0 to peg 2
Move 2: Disk 2 from peg 0 to peg 1
Move 3: Disk 1 from peg 2 to peg 1
Move 4: Disk 3 from peg 0 to peg 2
Move 5: Disk 1 from peg 1 to peg 0
Move 6: Disk 2 from peg 1 to peg 2
Move 7: Disk 1 from peg 0 to peg 2
*/

The Deep Connection:

The Gray code bit that changes at step k tells us which disk to move:

Step 1 (001): bit 0 changes → move disk 1 (smallest)
Step 2 (010): bit 1 changes → move disk 2
Step 3 (011): bit 0 changes → move disk 1
Step 4 (100): bit 2 changes → move disk 3 (largest)
Step 5 (101): bit 0 changes → move disk 1
Step 6 (110): bit 1 changes → move disk 2
Step 7 (111): bit 0 changes → move disk 1

This matches exactly the well-known pattern: the smallest disk moves every odd step, other disks move according to their binary representation in the step number!

Why This Works

The Towers of Hanoi has an underlying structure where the state space is a path graph (each state connects to exactly two neighbors), and the optimal solution walks this path. Gray code is exactly such a path through bit patterns! The constraint that only one disk moves per step corresponds to exactly one bit changing per Gray code transition.

Programming Applications of Gray Code

Beyond hardware, Gray code appears in several algorithmic contexts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// Generate all subsets where consecutive subsets differ by one element
function* generateSubsetsGrayOrder<T>(items: T[]): Generator<T[]> {
    const n = items.length;
    const count = 1 << n;
    
    for (let i = 0; i < count; i++) {
        const gray = i ^ (i >>> 1);
        const subset: T[] = [];
        
        for (let bit = 0; bit < n; bit++) {
            if ((gray >>> bit) & 1) {
                subset.push(items[bit]);
            }
        }
        
        yield subset;
    }
}
 
// Get all subsets of [A, B, C] in Gray code order
const items = ['A', 'B', 'C'];
console.log("Subsets in Gray order:");
for (const subset of generateSubsetsGrayOrder(items)) {
    console.log(subset.length === 0 ? "∅" : subset.join(", "));
}
/* Output:
∅
A
A, B
B
B, C
A, B, C
A, C
C
*/
// Notice: each consecutive pair differs by adding/removing exactly one element!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// The n-bit Gray code can help with certain search problems
// where we want to explore a space making minimal changes per step
 
// Example: Optimizing a function that's evaluated on boolean variables
// where evaluating near previous points is cheaper (caching bit-operations)
 
function optimizeWithGrayCode(
    n: number,
    evaluate: (bits: number) => number
): { bestValue: number; bestBits: number } {
    const count = 1 << n;
    let bestValue = -Infinity;
    let bestBits = 0;
    
    // Previous bits for computing which bit changed
    let prevGray = 0;
    
    for (let i = 0; i < count; i++) {
        const gray = i ^ (i >>> 1);
        
        // Could use (prevGray ^ gray) to find the single changed bit
        // This enables efficient incremental evaluation
        
        const value = evaluate(gray);
        
        if (value > bestValue) {
            bestValue = value;
            bestBits = gray;
        }
        
        prevGray = gray;
    }
    
    return { bestValue, bestBits };
}
 
// Example usage: maximize number of 1s in specific positions
const result = optimizeWithGrayCode(4, (bits) => {
    // Custom evaluation function
    return ((bits & 0b1010) ? 10 : 0) + ((bits & 0b0101) ? 5 : 0);
});
 
console.log("Best configuration:", result.bestBits.toString(2).padStart(4, '0'));

Other Algorithmic Uses

•Genetic Algorithms: Gray-coded chromosomes can improve convergence by ensuring small genotype changes cause small phenotype changes
•Error Correction: Gray code is related to unit-distance codes used in error detection
•Combinatorial Generation: Generate permutations, combinations with adjacent transpositions
•Graph Problems: Gray code represents a Hamiltonian path on the hypercube graph
•Interview Problems: LeetCode #89 (Gray Code) directly asks for this sequence

LeetCode Problem: Gray Code (LC 89)

Let's walk through the classic LeetCode Gray Code problem as a practical application.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
 * LeetCode 89. Gray Code
 * 
 * Given n, return any valid n-bit Gray code sequence.
 * A Gray code sequence must:
 * - Begin with 0
 * - Contain 2^n unique integers (each in range [0, 2^n - 1])
 * - Have a difference of exactly one bit between consecutive integers
 * 
 * Example: n=2 → [0,1,3,2] or [0,2,3,1]
 */
 
// Solution 1: Direct formula (most elegant)
function grayCodeFormula(n: number): number[] {
    const result: number[] = [];
    const count = 1 << n;
    
    for (let i = 0; i < count; i++) {
        result.push(i ^ (i >>> 1));
    }
    
    return result;
}
 
// Solution 2: Iterative reflection
function grayCodeReflection(n: number): number[] {
    const result: number[] = [0];
    
    for (let bit = 0; bit < n; bit++) {
        const highBit = 1 << bit;
        
        // Mirror current list, adding highBit to each
        for (let i = result.length - 1; i >= 0; i--) {
            result.push(result[i] | highBit);
        }
    }
    
    return result;
}
 
// Solution 3: Backtracking (generates all valid sequences)
function grayCodeBacktrack(n: number): number[] {
    const count = 1 << n;
    const result: number[] = [0];
    const used = new Set<number>([0]);
    
    function backtrack(): boolean {
        if (result.length === count) {
            // Check cyclic property: last differs from first by 1 bit
            const diff = result[result.length - 1] ^ result[0];
            return (diff & (diff - 1)) === 0;  // Power of 2 check
        }
        
        const last = result[result.length - 1];
        
        // Try flipping each bit
        for (let bit = 0; bit < n; bit++) {
            const next = last ^ (1 << bit);
            
            if (!used.has(next)) {
                result.push(next);
                used.add(next);
                
                if (backtrack()) return true;
                
                result.pop();
                used.delete(next);
            }
        }
        
        return false;
    }
    
    backtrack();
    return result;
}
 
// Test all solutions
console.log("Formula:", grayCodeFormula(3));
console.log("Reflection:", grayCodeReflection(3));
console.log("Backtrack:", grayCodeBacktrack(3));
 
// All produce valid Gray code sequences, though specific order may differ

Solution Comparison
Approach	Time	Space	Elegance	Flexibility
Direct Formula	O(2ⁿ)	O(1) extra	★★★★★	Standard sequence only
Reflection	O(2ⁿ)	O(1) extra	★★★★	Standard sequence only
Backtracking	O(n × 2ⁿ)	O(2ⁿ)	★★★	Can find all sequences

Interview Insight

In an interview, start with the formula approach (shows knowledge of the elegant solution), but be prepared to explain the reflection construction (shows understanding of why it works). If asked for variations, the backtracking approach shows problem-solving flexibility.

Summary: Gray Code Mastered

We've explored Gray code from its hardware origins to its elegant mathematical properties and algorithmic applications.

Key Takeaways

•Gray code prevents glitches: Only one bit changes between consecutive values, eliminating transitional errors in hardware
•Simple conversion formula: Binary to Gray is n ^ (n >>> 1), Gray to binary uses iterative XOR
•Reflection construction: n-bit codes are (n-1)-bit codes with 0 prefix, plus reversed with 1 prefix
•Bit-flip pattern: The rightmost 1 bit in the counter tells which bit to flip
•Towers of Hanoi solution: Gray code directly encodes the optimal solution to the classic puzzle
•Subset generation: Gray order visits all subsets changing one element at a time
•Hypercube path: Gray code is a Hamiltonian path on the n-dimensional hypercube graph

Key Formulas:

// Binary → Gray
function binaryToGray(n: number): number {
    return n ^ (n >>> 1);
}

// Gray → Binary
function grayToBinary(g: number): number {
    let b = 0;
    for (; g !== 0; g >>>= 1) b ^= g;
    return b;
}

// Generate n-bit Gray codes
function grayCode(n: number): number[] {
    return Array.from({length: 1 << n}, (_, i) => i ^ (i >>> 1));
}

Module Complete:

With Gray code, we complete our exploration of classic bit manipulation problem types. You've mastered:

XOR Swap — Exchanging values without temporary storage
Bit Reversal — Flipping bit order with multiple algorithms
Arithmetic from Logic — Addition using only XOR and AND
Maximum XOR Pair — Trie-based optimization for XOR problems
Gray Code — The single-bit-difference sequence

These techniques form the essential toolkit for solving bit manipulation problems in interviews, competitive programming, and systems engineering.

Page Complete

You now understand Gray code deeply—its hardware motivation, mathematical elegance, conversion algorithms, and surprising applications. Gray code exemplifies how a simple constraint (one-bit changes) leads to a structure with far-reaching consequences across computer science and mathematics.