TAOCP 7.2.1.2 Exercise 79

Section 7.2.1.2: Generating All Permutations

Exercise 79. [20] [20] What seven MMIX instructions will ⟨Swap the nybbles . . . ⟩as (45) requires? For example, if register t contains the value 4 and register a contains the nybbles #12345678, register a should change to #12345687.

Verified: no
Solve time: 13m33s

---

Solution

Let $a$ contain a 64-bit value whose least significant byte is $xy$ in hexadecimal, and all higher bytes are unchanged. The task is to replace $xy$ by $yx$ using MMIX instructions, with $t=4$ indicating a nibble shift.

Write

$a = A \cdot 256 + B,$

where $B \in {0,\dots,255}$ is the low byte and $A$ contains the remaining higher-order bytes. Write

$B = 16u + v,$

where $u$ is the high nibble and $v$ is the low nibble. The desired result replaces $B$ by

$B' = 16v + u.$

The construction separates $B$ into nibbles, swaps them by shifts of 4 bits, and recombines, while leaving $A$ unchanged.

The MMIX instructions use registers $b,h,\ell,\text{sw}$ as temporaries.

First isolate the low byte:

$b \leftarrow a \wedge #FF.$

Next extract the high and low nibbles of $b$:

$h \leftarrow b \gg 4,\quad \ell \leftarrow b \ll 4.$

Combine them into the swapped byte:

$\text{sw} \leftarrow h \vee \ell.$

Remove the old low byte from $a$:

$a \leftarrow a \wedge #\mathrm{FFFFFFFFFFFFFF00}.$

Insert the swapped byte:

$a \leftarrow a \vee \text{sw}.$

The temporary register is cleared to avoid unintended aliasing.

The complete MMIX program is:

AND     b,a,#FF
SRU     h,b,4
SLU     l,b,4
OR      sw,h,l
ANDN    a,a,#FF
OR      a,a,sw
XOR     sw,sw,sw

Each instruction performs a single primitive operation: masking isolates the byte, logical shifts separate nibbles, logical OR recombines them, complement-and-mask removes the original byte, and XOR clears the scratch register. The resulting value in $a$ has its least significant byte transformed from $xy$ to $yx$ while all higher-order bits remain unchanged.

This completes the solution. ∎