TAOCP 7.1.3 Exercise 56

Number the bits of the 64-bit register from $0$ (least significant) to $63$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 56. [24] Suggest a way to transpose a $7 \times 9$ bit matrix in a 64-bit register.

Verified: yes
Solve time: 1m09s

Solution

Number the bits of the 64-bit register from $0$ (least significant) to $63$. The $7 \times 9$ matrix occupies positions

$k = 9i + j, \qquad 0 \le i \le 6,; 0 \le j \le 8,$

with one unused position at $k = 63$. The transpose maps entry $(i,j)$ to $(j,i)$, hence induces a permutation $\pi$ on ${0,\ldots,62}$ defined by

$\pi(9i + j) = 7j + i.$

The value $k = 63$ is fixed.

This permutation extends to a permutation of all $64$ bit positions by defining $\pi(63) = 63$, so the bit-rearrangement task is a permutation of a 64-bit word.

Each permutation decomposes uniquely into disjoint cycles. For a cycle

$c = (a_0, a_1, \ldots, a_{L-1}), \qquad \pi(a_t) = a_{t+1 \bmod L},$

the bits in these positions must be rotated cyclically. The cycle can be executed by repeated exchanges of bit values along the cycle.

A swap of bits in positions $p$ and $q$ in a word $x$ is performed by the operation

$t = ((x \gg p) ,&, 1) \oplus ((x \gg q) ,&, 1),$

followed by

$x \leftarrow x \oplus (t \ll p) \oplus (t \ll q).$

If the bits agree, then $t = 0$ and no change occurs; if they differ, both bits are flipped, which exchanges their values.

Applying this swap operation successively along a cycle of length $L$ performs a cyclic rotation of the bits in that cycle using $L-1$ swaps. Each swap preserves all bits outside ${p,q}$ and affects only those two positions, so cycles remain independent.

Since the permutation on $64$ positions decomposes into disjoint cycles covering all positions, performing the above swap procedure for each cycle transforms the register according to $\pi$, which is exactly the transposition of the $7 \times 9$ matrix into a $9 \times 7$ matrix stored in the same bit order.

The resulting configuration places the bit originally at position $9i + j$ into position $7j + i$, hence implements matrix transposition within the 64-bit register. This completes the construction. ∎