TAOCP 7.1.3 Exercise 47

Let δ be the mask selecting the positions to be swapped in the general δ-swap (69).

taocpmathematicsalgorithmsvolume-4simple

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 47. [10] Can the general δ-swap (69) also be done with a method like (67)?

Verified: yes
Solve time: 1m

Let δ be the mask selecting the positions to be swapped in the general δ-swap (69). Set

$t \leftarrow (x \oplus y) ,&, \delta,$

then perform

$x \leftarrow x \oplus t,$

$y \leftarrow y \oplus t.$

For each bit position $k$ with $\delta_k = 0$, we have $t_k = 0$, so $x_k$ and $y_k$ remain unchanged. For each position with $\delta_k = 1$, we have $t_k = x_k \oplus y_k$, so the updates replace $x_k$ by $x_k \oplus (x_k \oplus y_k) = y_k$ and replace $y_k$ by $y_k \oplus (x_k \oplus y_k) = x_k$, producing an exchange of the selected bits.

The construction therefore realizes the general δ-swap using three replacement operations.