TAOCP 7.1.3 Exercise 46
Let $x$ be a register containing bits $x_0, x_1, \ldots$, and fix distinct positions $i \neq j$.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 46. [22] Method (68) uses six operations to interchange two bits $x_i \leftrightarrow x_j$ of a register. Show that this interchange can actually be done with only three MMIX instructions.
Verified: no
Solve time: 1m43s
Solution
Let $x$ be a register containing bits $x_0, x_1, \ldots$, and fix distinct positions $i \neq j$. The goal is to interchange $x_i$ and $x_j$ while leaving all other bits unchanged.
Define
$$ t \leftarrow \bigl((x \gg i) \oplus (x \gg j)\bigr) ,&, 1. $$
This extracts the parity of the difference between the two target bits. Since right shifting by $k$ moves bit $x_k$ into position $0$, the expression $(x \gg i) \oplus (x \gg j)$ has least significant bit equal to $x_i \oplus x_j$. Hence $t = x_i \oplus x_j$.
Next define
$$ m \leftarrow (t \ll i) \mid (t \ll j). $$
If $t = 0$, then $m = 0$. If $t = 1$, then $m$ has exactly two 1-bits at positions $i$ and $j$. In both cases, $m$ has 1s exactly where the swap must toggle bits.
Finally perform
$$ x \leftarrow x \oplus m. $$
This is the only modification step applied to the register.
To verify correctness, consider the two cases determined by $(x_i, x_j)$.
If $x_i = x_j$, then $t = x_i \oplus x_j = 0$, hence $m = 0$ and $x$ is unchanged. The bits at positions $i$ and $j$ remain equal and unchanged.
If $x_i \neq x_j$, then $t = 1$, so $m$ has 1s in positions $i$ and $j$. XOR with $m$ flips exactly those two bits, hence both $x_i$ and $x_j$ are complemented. Since they were unequal, complementing both interchanges their values, while every other bit $x_k$ with $k \notin {i,j}$ remains unchanged because $m_k = 0$.
Thus the operation swaps bits $x_i \leftrightarrow x_j$.
The computation consists of three MMIX-level instructions corresponding to the three assignments: computation of $t$, formation of $m$, and update of $x$.
This completes the proof. ∎