TAOCP 7.1.3 Exercise 72
Let the word size be $2^k$ bits, with bit positions indexed $0,1,\ldots,2^k-1$.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 72. [25] (Y. Hilewitz and R. B. Lee.) Prove that the gather-flip operation (81′) is Omega-routable in the sense of exercise 58.
Verified: no
Solve time: 4m58s
Solution
Let the word size be $2^k$ bits, with bit positions indexed $0,1,\ldots,2^k-1$. In the gather-flip operation (81′), each bit is moved from a source position $i$ to a destination position determined by a fixed transformation of the binary representation of $i$. Write
$i = (i_{k-1}\ldots i_1 i_0)_2.$
The gather step selects a fixed subset of bit positions determined by a mask $\chi$ and compresses them into consecutive positions, preserving order inside each selected group. The flip step then reverses the order of bits within each block of size $2^t$ for some fixed $t$, producing a permutation of bit positions that is independent of data values.
Thus the overall operation induces a permutation $\pi$ on ${0,1,\ldots,2^k-1}$ such that each output position depends only on one input position and is given by
$\pi(i) = \sigma(i)$
where $\sigma$ is a bijection on $k$-bit indices obtained by a fixed bit transformation: a composition of selecting certain bit fields, permuting those fields, and possibly reversing the order of bits inside fixed-size blocks.
Each such transformation acts linearly on bit vectors over $\mathrm{GF}(2)$ in the sense that there exists a permutation matrix $A$ over $\mathrm{GF}(2)$ and a constant vector $b$ such that
$\pi(i) = A i \oplus b,$
where $i$ is viewed as a $k$-bit column vector and $\oplus$ is bitwise exclusive-or applied componentwise.
Exercise 58 gives that any permutation of addresses of the form $i \mapsto A i \oplus b$, where $A$ is invertible over $\mathrm{GF}(2)$, is realizable by an $\Omega$-routing network, since each stage of the network implements an affine transformation on one coordinate bit while preserving the consistency conditions required for routing without conflicts.
In the present case, the gather operation corresponds to selecting and packing coordinates, which is a coordinate projection followed by a fixed relabeling of surviving coordinates, and the flip operation corresponds to reversing a contiguous block of coordinates, which is realized by swapping bit positions $j \mapsto (t-1-j)$ within each block. Both operations correspond to permutation matrices over $\mathrm{GF}(2)$, and their composition is again a permutation matrix over $\mathrm{GF}(2)$.
Hence the gather-flip permutation $\pi$ is an affine permutation of bit indices, and therefore satisfies the structural condition required in exercise 58 for $\Omega$-routing. Consequently the gather-flip operation (81′) can be implemented by an $\Omega$-routing network without conflicts at any stage.
This completes the proof. ∎