TAOCP 7.1.3 Exercise 98
Each byte $x_j$ and $y_j$ is interpreted as an unsigned 8-bit integer in ${0,\ldots,255}$.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 98. [20] Given $x = (x_7 \ldots x_0){256}$ and $y = (y_7 \ldots y_0){256}$, compute $z = (z_7 \ldots z_0){256}$ and $w = (w_7 \ldots w_0){256}$, where $z_j = \max(x_j, y_j)$ and $w_j = \min(x_j, y_j)$ for $0 \le j < 8$.
Verified: no
Solve time: 5m10s
Solution
Each byte $x_j$ and $y_j$ is interpreted as an unsigned 8-bit integer in ${0,\ldots,255}$. The operations are performed independently on each byte position, so all constructions may be derived for a single position $j$ and then lifted to octabyte-wide expressions.
The identities (8)–(11) imply that bitwise operations implement logical structure independently in each bit position, so arithmetic comparisons between two bytes can be encoded via subtraction and sign detection on 8-bit arithmetic, interpreted modulo $256$.
To compute $z_j = \max(x_j,y_j)$ and $w_j = \min(x_j,y_j)$, start from the identity valid over integers,
$$ \max(a,b) = \frac{a+b+|a-b|}{2}, \qquad \min(a,b) = \frac{a+b-|a-b|}{2}. $$
In byte arithmetic modulo $256$, subtraction $a-b$ is represented as $a + \overline{b} + 1$ by (17). Define the byte difference
$$ d_j = (x_j + \overline{y_j} + 1) \bmod 256 = x_j - y_j \pmod{256}. $$
The sign of $x_j - y_j$ in the 8-bit two's complement sense is detected by the most significant bit of $d_j$. The value $128$ corresponds to bit $7$, so
$$ s_j = d_j ,&, 128 $$
satisfies $s_j = 0$ if $x_j \le y_j$ and $s_j = 128$ if $x_j > y_j$, since in unsigned interpretation the range $0,\ldots,127$ has top bit $0$ and $128,\ldots,255$ has top bit $1$.
Thus define
$$ w_j = x_j - \frac{s_j}{128}(x_j - y_j), \qquad z_j = y_j + \frac{s_j}{128}(x_j - y_j). $$
Substituting $s_j/128 = [x_j > y_j]$ yields the two cases explicitly.
If $x_j \le y_j$, then $s_j = 0$, hence $w_j = x_j$ and $z_j = y_j$, which matches $\min$ and $\max$.
If $x_j > y_j$, then $s_j = 128$, hence $s_j/128 = 1$, so $w_j = y_j$ and $z_j = x_j$, again matching $\min$ and $\max$.
To express this purely in bitwise form without division, use the mask $m_j = s_j \gg 7$, so $m_j \in {0,1}$. Then
$$ w_j = x_j \oplus \big(m_j \cdot (x_j \oplus y_j)\big), \qquad z_j = y_j \oplus \big(m_j \cdot (x_j \oplus y_j)\big), $$
since toggling by $x_j \oplus y_j$ swaps the values exactly when $x_j > y_j$.
Lifting to the full octabyte,
$$ d = (x + \overline{y} + 1), \qquad s = d ,&, (128\cdot(1+256+\cdots+256^7)), $$
and applying the construction bytewise yields $z = (z_7\ldots z_0){256}$ and $w = (w_7\ldots w_0){256}$ satisfying $z_j = \max(x_j,y_j)$ and $w_j = \min(x_j,y_j)$ for all $j$.
This completes the construction. ∎