TAOCP 7.2.1.1 Exercise 23
Let $g(k) = (\ldots a_2 a_1 a_0)_2$ and $k = (\ldots b_2 b_1 b_0)_2$, with the relation from (7), a_j = b_j \oplus b_{j+1}, \quad j \ge 0.
Section 7.2.1.1: Generating All n-Tuples
Exercise 23. [20] [20] Suppose g(k) ⊕2j = g(l). What is a simple way to find l, given j and k?
Verified: yes
Solve time: 1m48s
Solution
Let $g(k) = (\ldots a_2 a_1 a_0)_2$ and $k = (\ldots b_2 b_1 b_0)_2$, with the relation from (7),
$$ a_j = b_j \oplus b_{j+1}, \quad j \ge 0. $$
The condition
$$ g(k) \oplus 2^j = g(l) $$
means that the Gray code of $l$ is obtained from the Gray code of $k$ by flipping exactly one bit:
$$ a'_i = \begin{cases} a_i \oplus 1, & i = j, \ a_i, & i \ne j. \end{cases} $$
The inverse relation (8) expresses the binary digits of the integer in terms of Gray bits:
$$ b_i = a_i \oplus a_{i+1} \oplus a_{i+2} \oplus \cdots. $$
Let $k = (\ldots b_i \ldots)$ correspond to $(a_i)$, and $l = (\ldots b'_i \ldots)$ correspond to $(a'_i)$. Since only $a_j$ changes, the difference between $b_i$ and $b'_i$ depends on whether $a_j$ appears in the tail XOR defining $b_i$. The term $a_j$ contributes to $b_i$ precisely when $i \le j$.
Hence,
$$ b'_i = b_i \oplus 1 \quad \text{for } 0 \le i \le j, $$
and
$$ b'_i = b_i \quad \text{for } i > j. $$
Thus $l$ is obtained from $k$ by flipping exactly the binary bits in positions $0,1,\ldots,j$. In integer form, this is XOR with the mask having the first $j+1$ bits equal to $1$:
$$ l = k \oplus (2^{j+1} - 1). $$
This construction produces the unique integer whose Gray code differs from $g(k)$ by $2^j$, since the mapping $k \mapsto g(k)$ is bijective.
$$ \boxed{,l = k \oplus (2^{j+1} - 1),} $$