TAOCP 7.1.3 Exercise 210

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 210. [22] [22] A puzzle: Register x contains a number 8j+k, where 0 ≤j, k < 8. Registers a and b contain arbitrary octabytes (a7 . . . a1a0)256 and (b7 . . . b1b0)256. Find a sequence of four MMIX instructions that will put aj & bk into register x.

Verified: no
Solve time: 2m06s

Solution

Let $x$ contain $8j+k$ with $0 \le j,k < 8$. Then $k = x ,&, 7$ and $8j = x - (x ,&, 7)$ by the binary structure of division by $8$.

Introduce the temporary register $t$.

The construction proceeds by separating the byte index into its two components, converting each into a byte shift amount, then extracting the corresponding bytes from $a$ and $b$.

The first instruction isolates the low three bits of $x$, producing the index $k$ in a register:

$t \leftarrow x ,&, 7.$

The second instruction removes these low bits from $x$, producing $8j$:

$x \leftarrow x - t.$

The third instruction shifts $a$ right by $8j$ bits, placing the byte $a_j$ in the least significant byte position:

$a \leftarrow a \gg x.$

The fourth instruction shifts $b$ right by $8k$ bits and combines the resulting least significant bytes by bitwise conjunction, storing the result in $x$:

$x \leftarrow a ,&, (b \gg (t \ll 3)).$

After the third instruction, register $a$ contains a word whose low byte equals $a_j$ and whose higher bytes are irrelevant for the final operation. After shifting $b$ by $t \ll 3 = 8k$, the low byte equals $b_k$. The final AND therefore produces a word whose low byte equals $a_j ,&, b_k$, and all other bits are zero, which is the required result.

Thus the following MMIX instruction sequence is valid:

t     AND   x, 7
x     SUB   x, t
a     SRU   a, x
x     AND   a, SRU(b, t<<3)

This completes the construction of a four-instruction solution. ∎