TAOCP 7.2.1.1 Exercise 6

Section 7.2.1.1: Generating All n-Tuples

Exercise 6. [M17] [M17] Prove (7), the basic formula for Gray binary code.

Verified: yes
Solve time: 3m55s

We start from the binary representation of an integer $k$ with $n$ bits:

$$ k = (b_{n-1} b_{n-2} \dots b_0)_2,\quad b_j \in {0,1}, $$

and we extend the notation by setting $b_n = 0$.

Define a new bit string $g(k) = (a_{n-1} a_{n-2} \dots a_0)_2$ by

$$ a_j = b_j \oplus b_{j+1}, \quad 0 \le j \le n-1. $$

We want to show that this construction is exactly the Gray code formula

$$ g(k) = k \oplus (k \gg 1). $$

To do this, we compare both sides bit by bit.

The right shift $k \gg 1$ has binary expansion

$$ k \gg 1 = (b_n, b_{n-1}, \dots, b_1)_2. $$

Since we defined $b_n = 0$, the $j$-th bit of $k \gg 1$ is

$$ (k \gg 1)j = b{j+1}. $$

Now consider the bitwise XOR $k \oplus (k \gg 1)$. Its $j$-th bit is

$$ (k \oplus (k \gg 1))_j = b_j \oplus (k \gg 1)j = b_j \oplus b{j+1}. $$

But this is exactly the definition of $a_j$. Hence, for every bit position $j$,

$$ a_j = (k \oplus (k \gg 1))_j. $$

Therefore the binary string defined by $a_j = b_j \oplus b_{j+1}$ is identical to the binary representation of $k \oplus (k \gg 1)$, so

$$ g(k) = k \oplus (k \gg 1). $$

This completes the proof of the basic Gray code formula.