TAOCP 7.1.3 Exercise 105

Let $x = (x_7 \ldots x_0)_{256}$ and $y = (y_7 \ldots y_0)_{256}$, where each $x_i$ and $y_i$ is an 8-bit byte interpreted as an integer in ${0,\ldots,255}$.

taocpmathematicsalgorithmsvolume-4hard

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 105. [30] Given $x = (x_7 \ldots x_0){256}$ and $y = (y_7 \ldots y_0){256}$, discuss bitwise operations that will sort the bytes into order, so that $x_0 \le y_0 \le \cdots \le x_7 \le y_7$ afterwards.

Verified: no
Solve time: 2m08s

Setup

Let $x = (x_7 \ldots x_0){256}$ and $y = (y_7 \ldots y_0){256}$, where each $x_i$ and $y_i$ is an 8-bit byte interpreted as an integer in ${0,\ldots,255}$. Bitwise operations on words act independently on each bit position, so a shift by $8k$ bits aligns byte $i$ with byte $i+k$.

For two packed words $a$ and $b$, define the per-byte compare-exchange mask

$m = ((a - b) \gg 7) ,&, 1,$

where the shift extracts the sign bit of each byte result, interpreted in two's complement per byte. Then define

$\min(a,b) = b \oplus \bigl((a \oplus b) ,&, m\bigr), \qquad \max(a,b) = a \oplus \bigl((a \oplus b) ,&, m\bigr).$

Each byte position computes $\min(a_i,b_i)$ and $\max(a_i,b_i)$ simultaneously.

The task is to permute the 16 bytes of $x$ and $y$ so that after execution

$x_0 \le y_0 \le x_1 \le y_1 \le \cdots \le x_7 \le y_7.$

This is a bitonic merge of two sequences of length $8$ into alternating sorted order.

Solution

Form the concatenation of the two 8-byte sequences as a conceptual 16-element array

$a_0=x_0,\ldots,a_7=x_7,\quad a_8=y_0,\ldots,a_{15}=y_7.$

The required output corresponds to sorting this sequence and placing the even-ranked elements in $x$ and the odd-ranked elements in $y$.

A bitonic sorting network on 16 inputs suffices. Its structure is determined recursively: a bitonic sequence of length $2^k$ is formed by concatenating an increasing sequence and a decreasing sequence, and it is merged by stages that compare elements distance $2^{k-1},2^{k-2},\ldots,1$ apart.

Here the two inputs are treated as a bitonic sequence after reversing $y$ internally, since

$x_0 \le \cdots \le x_7 \quad \text{and} \quad y_7 \le \cdots \le y_0$

forms a bitonic sequence after reversal of $y$. The reversal is implemented by permuting byte lanes using shifts by multiples of $8$ bits and masks selecting byte positions.

The merge proceeds in stages indexed by $t \in {3,2,1,0}$. At stage $t$, comparisons occur between byte positions differing by $2^t$ within the 16-element array. In packed form this is implemented by shifting the word by $8\cdot 2^t$ bits and applying a compare-exchange on aligned bytes.

Let $A$ denote the current 128-bit vector storing all 16 bytes. For each stage $t$, define

$B = A \gg (8\cdot 2^t),$

where bytes shifted out are discarded and zero-filled. Then compute the compare-exchange mask per byte

$m_t = ((A - B) \gg 7) ,&, 1,$

and update

$A \leftarrow A \oplus \bigl((A \oplus B) ,&, m_t\bigr).$

After the stage sequence $t=3,2,1,0$, the array $A$ is sorted in nondecreasing order.

Finally, distribute alternating bytes: assign

$x_i = A_{2i}, \qquad y_i = A_{2i+1} \quad (0 \le i \le 7).$

This assignment is a pure byte extraction, implemented by masking and shifting by $8k$ bits.

The resulting packed words satisfy

$x_0 \le y_0 \le x_1 \le y_1 \le \cdots \le x_7 \le y_7.$

This completes the construction of the required bitwise sorting procedure. ∎

Verification

Each compare-exchange step uses only $\min$ and $\max$ per byte, so every operation preserves the multiset of bytes in each compared pair.

At stage $t$, all comparisons are between disjoint pairs of byte positions separated by $2^t$, so no byte participates in more than one exchange per stage. Hence each stage preserves all previously established order relations inside blocks of size $2^{t+1}$.

The standard property of the bitonic merge network ensures that after stage $t$, every block of length $2^{t+1}$ is correctly partitioned into a lower half and an upper half relative to all elements in that block. Induction on $t$ shows that after $t=0$, the entire 16-byte sequence is sorted.

Extracting even and odd positions does not alter the relative order within the sorted sequence, so the final interleaving satisfies

$x_0 \le y_0 \le \cdots \le x_7 \le y_7.$

This completes the proof. ∎

Notes

The construction is a direct packed implementation of a 16-input bitonic sorting network. The key bitwise ingredient is the per-byte compare-exchange based on the sign bit of $a-b$, which avoids branching and operates in parallel across all byte lanes.