Why Adjacent Numbers Differ by Only One Bit

The guarantee that adjacent numbers in the Gray code sequence differ by exactly one bit comes from the formula: Gray(i) = i ^ (i >> 1).

Step-by-Step Explanation

1. Understanding the Formula:

i is the current number
i >> 1 shifts the binary representation of i by one bit to the right
The XOR operation (^) compares the bits of i and i >> 1, flipping only the bits that differ

2. Why Adjacent Numbers Differ by One Bit:

When moving from i to i+1 in binary, only one bit changes. The XOR operation focuses on this change by comparing i and its shifted version (i >> 1), ensuring the result changes by just one bit.

3. Example (n = 2):

i	i (binary)	i >> 1 (binary)	i ^ (i >> 1)	Gray Code (binary)
0	00	00	00	00
1	01	00	01	01
2	10	01	11	11
3	11	01	10	10

So, the Gray code sequence for n = 2 is [0, 1, 3, 2], and each pair of adjacent numbers differs by exactly one bit.

Why It Works:

The XOR operation ensures that only one bit changes between successive Gray codes.
No duplicates occur because each i produces a unique Gray code through the formula.
The sequence naturally progresses through all possible combinations of n bits, ensuring completeness.

Latest Posts in Leetcode

89. Gray Code - LeetCode Solution | C++ | Go | Kotlin | Java | JS | TS | Python