TAOCP 7.1.3 Exercise 1

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 1. ▶ [15] What is the net effect of setting $x \leftarrow x \oplus y$, $y \leftarrow y \oplus (x \mathbin{&} m)$, $x \leftarrow x \oplus y$?

Verified: yes
Solve time: 1m45s

Solution

Let the initial values be $x_0$ and $y_0$.

After the first assignment,

$x_1 = x_0 \oplus y_0, \qquad y_1 = y_0.$

After the second assignment,

$y_2 = y_1 \oplus (x_1 ,&, m) = y_0 \oplus \big((x_0 \oplus y_0),&, m\big),$

while $x_2 = x_1$ remains unchanged.

After the third assignment,

$x_3 = x_2 \oplus y_2 = (x_0 \oplus y_0) \oplus \left(y_0 \oplus \big((x_0 \oplus y_0),&, m\big)\right).$

Using associativity and cancellation of $\oplus$,

$x_3 = x_0 \oplus \big((x_0 \oplus y_0),&, m\big).$

Thus,

$y_3 = y_0 \oplus \big((x_0 \oplus y_0),&, m\big).$

Define

$t = (x_0 \oplus y_0),&, m.$

Then the final state is

$x_3 = x_0 \oplus t, \qquad y_3 = y_0 \oplus t.$

For each bit position $k$, if $m_k = 0$ then $t_k = 0$ and both $x_k$ and $y_k$ remain unchanged. If $m_k = 1$, then $t_k = (x_{0,k} \oplus y_{0,k})$, so the pair $(x_{0,k}, y_{0,k})$ is transformed to $(x_{0,k} \oplus 1, y_{0,k} \oplus 1)$ exactly when the bits differ, and remains unchanged when they are equal. This interchanges the two bits in precisely the positions where $m$ has a $1$-bit.

Therefore the net effect is

$\boxed{(x, y) \mapsto \big(x \oplus ((x \oplus y),&, m),; y \oplus ((x \oplus y),&, m)\big)}.$

This completes the solution. ∎