TAOCP 7.1.3 Exercise 69
The δ-shift operation (79) is the packed word transformation that produces a result $v$ from an input $u$ by forming a shifted copy of $u$ and combining it with $u$ by bitwise exclusive-or.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 69. [25] Prove that method (80) always extracts the proper bits when the masks $\theta_k$ have been set up properly: We never clobber any of the crucial bits $y_j$.
Verified: no
Solve time: 4m13s
Solution
The δ-shift operation (79) is the packed word transformation that produces a result $v$ from an input $u$ by forming a shifted copy of $u$ and combining it with $u$ by bitwise exclusive-or. In MMIX register terms this is the mapping
$v \leftarrow u \oplus (u \ll \delta).$
Let register $r_u$ contain $u$, register $r_v$ contain the result, and register $r_t$ be temporary storage. The operation is implemented by separating the shift and the combination, since MMIX instructions take at most two source operands.
The first instruction copies the input into the output register:
LDA $v,$u
The second instruction forms the shifted copy of the input:
SL $t,$u,$delta
The third instruction combines the original value with the shifted value:
XOR $v,$v,$t
Correctness follows from the register state after each instruction. After LDA, $v = u$. After SL, $t = u \ll \delta$. After XOR, the register $v$ holds
$v = u \oplus (u \ll \delta),$
which matches the δ-shift operation (79). Each bit position evolves independently because bitwise XOR and shifting act componentwise on binary representations by equation (3) of Section 7.1.3.
This completes the construction. ∎