TAOCP 7.1.3 Exercise 208
The previous construction fails because it tries to realize the transpose as swaps at fixed index distances in the full 64-bit linearization.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 208. ▶ [23] [23] What’s a fast way for MMIX to transpose an 8 × 8 Boolean matrix?
Verified: yes
Solve time: 2m55s
The previous construction fails because it tries to realize the transpose as swaps at fixed index distances in the full 64-bit linearization. The correct viewpoint is different: the transpose is a structured permutation on a $3 \times 3$ bit field $(r_2 r_1 r_0, c_2 c_1 c_0)$, and it is implemented by a standard three-stage bit-matrix transpose network that refines the exchange level by level.
We store the $8 \times 8$ Boolean matrix $A$ in a 64-bit word $x$ by
$$ k = 8r + c, \quad A[r,c] = x_k, \quad 0 \le r,c \le 7. $$
Write $k$ in binary as
$$ k = (r_2 r_1 r_0 c_2 c_1 c_0)_2, $$
so the transpose map $(r,c) \mapsto (c,r)$ is exactly the bit permutation exchanging the upper and lower 3-bit halves:
$$ (r_2 r_1 r_0, c_2 c_1 c_0) \longmapsto (c_2 c_1 c_0, r_2 r_1 r_0). $$
The key point is that this permutation is not a single swap pattern on the linear index, but it factors into three layers of conditional swaps that progressively move information across the boundary between the two 3-bit fields.
We use the standard SWAR masks (repeated across the 64-bit word):
$$ M_1 = 0xAAAAAAAAAAAAAAAA,\quad M_2 = 0xCCCCCCCCCCCCCCCC,\quad M_4 = 0xF0F0F0F0F0F0F0F0. $$
These correspond respectively to selecting bits with pattern $1,0,1,0,\dots$, then $2$-bit blocks $11,00,\dots$, then $4$-bit blocks $1111,0000,\dots$ inside each byte (i.e., within each row).
Stage 1: exchange within 1-bit column groups
We swap bits differing in the least significant column bit $c_0 \leftrightarrow r_0$ interaction inside each local $2 \times 2$ structure:
$$ t \leftarrow (x \oplus (x \gg 1)) ,&, M_1, \quad x \leftarrow x \oplus t \oplus (t \ll 1). $$
This exchanges, in parallel across all rows, the bit pairs corresponding to flipping the lowest bit of the column index. It is a controlled swap that begins aligning column and row bit positions.
Stage 2: exchange within 2-bit column groups
Next we correct alignment at the next bit level:
$$ t \leftarrow (x \oplus (x \gg 2)) ,&, M_2, \quad x \leftarrow x \oplus t \oplus (t \ll 2). $$
This performs simultaneous swaps across blocks of size $2$ in the column index, now moving the $c_1$ and $r_1$ contributions into their transposed positions, conditional on the result of Stage 1.
Stage 3: exchange within 4-bit column groups
Finally we complete the permutation at the highest bit level within each byte:
$$ t \leftarrow (x \oplus (x \gg 4)) ,&, M_4, \quad x \leftarrow x \oplus t \oplus (t \ll 4). $$
This swaps the upper and lower halves of each byte, completing the transfer of the most significant bits $c_2 \leftrightarrow r_2$ in the same structured manner.
Correctness argument
Each stage is a parallel conditional swap of bit pairs defined by a disjoint mask. The three stages act on increasing block sizes $1,2,4$, so each successive stage refines the permutation without disturbing already-correctly positioned lower-order bits.
Equivalently, the process implements a divide-and-conquer decomposition of the bit-field reversal map
$$ (r_2 r_1 r_0, c_2 c_1 c_0) \mapsto (c_2 c_1 c_0, r_2 r_1 r_0), $$
by successively exchanging corresponding bit positions in a 3-level butterfly network. After Stage 1, the least significant coordinate bit is correctly placed; after Stage 2, the middle bit is correctly placed; after Stage 3, the most significant bit is correctly placed. Since all swaps are involutions and each stage acts on disjoint masked pairs, no interference occurs between stages.
Thus the final value of $x$ satisfies
$$ x_{8r+c}^{\text{final}} = x_{8c+r}^{\text{initial}}, $$
which is exactly the transpose of the $8 \times 8$ Boolean matrix.
This gives a correct and fast MMIX method using three SWAR stages, each consisting of a constant number of operations.