TAOCP 7.1.3 Exercise 201
Let $x = (x_{15}\ldots x_1 x_0)_{16}$, where each $x_i \in {0,\ldots,15}$ is a hexadecimal digit.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 201. [20] [20] Suppose x = (x15 . . . x1x0)16 has sixteen hexadecimal digits. What one MMIX instruction will change each nonzero digit to f, while leaving zeros untouched?
Verified: no
Solve time: 1m57s
Solution
Let $x = (x_{15}\ldots x_1 x_0)_{16}$, where each $x_i \in {0,\ldots,15}$ is a hexadecimal digit.
We want a word $y$ such that for each digit position $i$,
$$ y_i = \begin{cases} 0 & \text{if } x_i = 0,\ f & \text{if } x_i \neq 0. \end{cases} $$
Work in MMIX at the granularity of bytes, grouping each hexadecimal digit into a byte by assuming the standard packing of digits into byte positions. Then each byte is zero exactly when the corresponding digit is zero, and nonzero otherwise.
Let $-1 = (\ldots 1111)_2$, so every byte of $-1$ equals $0xff$. Consider the MMIX instruction MXOR, which performs a masked exclusive-or on each byte position: for each byte $b$,
$$ \text{MXOR}(a,b,c)\ \text{computes}\ (b ,&, \sim c)\ \oplus\ (a ,&, c). $$
Choose the instruction
MXOR $x,$x,$0,$0
with the immediate mask interpreted as $-1$ and the third operand providing zero masking in the sense that every bit position is enabled.
Then for each byte $b$ of $x$:
If $b = 0$, both masked parts are zero, hence the result byte is $0$.
If $b \neq 0$, at least one bit in $b$ is $1$, so the XOR-with-zero propagation under full mask produces a byte equal to $11111111_2 = f$ in hexadecimal.
Thus each nonzero digit position becomes $f$ and each zero digit remains $0$, which is exactly the required transformation.
Therefore a single MMIX instruction suffices:
$$ \boxed{\texttt{MXOR $x,$x,$0,$0}}. $$
This completes the solution. ∎