Section 7.1.3: Bitwise Tricks and Techniques

Exercise 52. [22] Find hexadecimal constants $(\theta_0, \theta_1, \theta_2, \theta_3, \theta_4, \theta_5, \tilde{\theta}_4, \tilde{\theta}_3, \tilde{\theta}_2, \tilde{\theta}1, \tilde{\theta}0)$ that change (71) to produce the following important 64-bit permutations, based on the binary representation $j = (j_5 j_4 j_3 j_2 j_1 j_0)2$: (a) $j\pi = (j_0 j_1 j_2 j_3 j_4 j_5)2$; (b) $j\pi = (j_3 j_1 j_4 j_2 j_5 j_0)2$; (c) $j\pi = (j_1 j_0 j_3 j_2 j_5 j_4)2$; (d) $j\pi = (j_0 j_5 j_2 j_3 j_4 j_1)2$. [Case (a) is the "perfect shuffle" (175) that takes $(x{63}\ldots x{33}x{32}x{31}\ldots x_1x_0)2$ into $(x{63}x{31}\ldots x{33}x_1x{32}x_0)_2$; case (b) transposes an $8 \times 8$ matrix of bits; case (c), similarly, transposes a $4 \times 16$ matrix; and case (d) arises in connection with "fast Fourier transforms," see exercise 4.6.4–14.]

Verified: no
Solve time: 3m40s

---

Let scheme (71) be interpreted in its actual routing form: for each stage $k\in{0,\dots,5}$, the exchange operates on the $k$-th bit position, and the masks must be chosen so that a datum located at index $j$ is sent toward the neighbor differing in bit $k$ exactly when that step is required by the bit permutation $j\mapsto j\pi$.

For a coordinate permutation $\pi$ on 6-bit indices, write

$$ j\pi = (j_{\sigma(0)}, j_{\sigma(1)}, j_{\sigma(2)}, j_{\sigma(3)}, j_{\sigma(4)}, j_{\sigma(5)} )_2, $$

so that the destination bit in position $k$ comes from source bit $\sigma(k)$.

Let $\mu_k$ be the standard 64-bit bit-plane masks:

$$ \begin{aligned} \mu_0&=\texttt{0xAAAAAAAAAAAAAAAA},& \mu_1&=\texttt{0xCCCCCCCCCCCCCCCC},\ \mu_2&=\texttt{0xF0F0F0F0F0F0F0F0},& \mu_3&=\texttt{0xFF00FF00FF00FF00},\ \mu_4&=\texttt{0xFFFF0000FFFF0000},& \mu_5&=\texttt{0xFFFFFFFF00000000}. \end{aligned} $$

Key corrected construction (scheme (71))

At stage $k$, the only indices that participate in a conditional exchange along dimension $k$ are those for which bit $k$ must change during routing. This occurs exactly when the $k$-bit of the source differs from the $k$-bit of its destination.

Since the destination bit is $j_{\sigma(k)}$, the condition is:

$$ j_k \neq j_{\sigma(k)}. $$

Thus the masks are determined by the two disjoint cases:

$$ \begin{aligned} \theta_k &= (\neg \mu_k)\wedge \mu_{\sigma(k)},\ \tilde{\theta}k &= \mu_k \wedge (\neg \mu{\sigma(k)}). \end{aligned} $$

These two masks partition the active exchanges at stage $k$, and ensure bijective routing in scheme (71).

All remaining positions implicitly do nothing at stage $k$.

(a) $j\pi=(j_0 j_1 j_2 j_3 j_4 j_5)$ (bit reversal)

Here $\sigma(k)=5-k$.

Masks

$$ \begin{aligned} \theta_0 &= \neg\mu_0 \wedge \mu_5 = \texttt{0x5555555500000000}, & \tilde{\theta}_0 &= \mu_0 \wedge \neg\mu_5 = \texttt{0x00000000AAAAAAAA},\[2mm] \theta_1 &= \neg\mu_1 \wedge \mu_4 = \texttt{0x3333000033330000}, & \tilde{\theta}_1 &= \mu_1 \wedge \neg\mu_4 = \texttt{0x0000CCCC0000CCCC},\[2mm] \theta_2 &= \neg\mu_2 \wedge \mu_3 = \texttt{0x0F000F000F000F00}, & \tilde{\theta}_2 &= \mu_2 \wedge \neg\mu_3 = \texttt{0x00F000F000F000F0},\[2mm] \theta_3 &= \neg\mu_3 \wedge \mu_2 = \texttt{0x00F000F000F000F0}, & \tilde{\theta}_3 &= \mu_3 \wedge \neg\mu_2 = \texttt{0x0F000F000F000F00},\[2mm] \theta_4 &= \neg\mu_4 \wedge \mu_1 = \texttt{0x0000CCCC0000CCCC}, & \tilde{\theta}_4 &= \mu_4 \wedge \neg\mu_1 = \texttt{0x3333000033330000},\[2mm] \theta_5 &= \neg\mu_5 \wedge \mu_0 = \texttt{0x00000000AAAAAAAA}, & \tilde{\theta}_5 &= \mu_5 \wedge \neg\mu_0 = \texttt{0x5555555500000000}. \end{aligned} $$

(b) $j\pi=(j_3 j_1 j_4 j_2 j_5 j_0)$

$$ \sigma:\ (0,1,2,3,4,5)\mapsto(3,1,4,2,5,0). $$

Apply the same rule.

$$ \begin{aligned} \theta_0 &= \neg\mu_0 \wedge \mu_3 = \texttt{0x5500550055005500}, & \tilde{\theta}_0 &= \mu_0 \wedge \neg\mu_3 = \texttt{0x00AA00AA00AA00AA},\[2mm] \theta_1 &= \neg\mu_1 \wedge \mu_1 = 0, & \tilde{\theta}_1 &= 0,\[2mm] \theta_2 &= \neg\mu_2 \wedge \mu_4 = \texttt{0x0F0F00000F0F0000}, & \tilde{\theta}_2 &= \mu_2 \wedge \neg\mu_4 = \texttt{0x0000F0F00000F0F0},\[2mm] \theta_3 &= \neg\mu_3 \wedge \mu_2 = \texttt{0x00F000F000F000F0}, & \tilde{\theta}_3 &= \mu_3 \wedge \neg\mu_2 = \texttt{0x0F000F000F000F00},\[2mm] \theta_4 &= \neg\mu_4 \wedge \mu_5 = \texttt{0x0000FFFF00000000}, & \tilde{\theta}_4 &= \mu_4 \wedge \neg\mu_5 = \texttt{0x00000000FFFF0000},\[2mm] \theta_5 &= \neg\mu_5 \wedge \mu_0 = \texttt{0x00000000AAAAAAAA}, & \tilde{\theta}_5 &= \mu_5 \wedge \neg\mu_0 = \texttt{0x5555555500000000}. \end{aligned} $$

(c) $j\pi=(j_1 j_0 j_3 j_2 j_5 j_4)$

$$ \sigma:\ (0,1,2,3,4,5)\mapsto(1,0,3,2,5,4). $$

$$ \begin{aligned} \theta_0 &= \neg\mu_0 \wedge \mu_1 = \texttt{0x4444444444444444}, & \tilde{\theta}_0 &= \mu_0 \wedge \neg\mu_1 = \texttt{0x2222222222222222},\[2mm] \theta_1 &= \neg\mu_1 \wedge \mu_0 = \texttt{0x2222222222222222}, & \tilde{\theta}_1 &= \mu_1 \wedge \neg\mu_0 = \texttt{0x4444444444444444},\[2mm] \theta_2 &= \neg\mu_2 \wedge \mu_3 = \texttt{0x0F000F000F000F00}, & \tilde{\theta}_2 &= \mu_2 \wedge \neg\mu_3 = \texttt{0x00F000F000F000F0},\[2mm] \theta_3 &= \neg\mu_3 \wedge \mu_2 = \texttt{0x00F000F000F000F0}, & \tilde{\theta}_3 &= \mu_3 \wedge \neg\mu_2 = \texttt{0x0F000F000F000F00},\[2mm] \theta_4 &= \neg\mu_4 \wedge \mu_5 = \texttt{0x0000FFFF00000000}, & \tilde{\theta}_4 &= \mu_4 \wedge \neg\mu_5 = \texttt{0x00000000FFFF0000},\[2mm] \theta_5 &= \neg\mu_5 \wedge \mu_4 = \texttt{0x00000000FFFF0000}, & \tilde{\theta}_5 &= \mu_5 \wedge \neg\mu_4 = \texttt{0xFFFF000000000000}. \end{aligned} $$

(d) $j\pi=(j_0 j_5 j_2 j_3 j_4 j_1)$

$$ \sigma:\ (0,1,2,3,4,5)\mapsto(0,5,2,3,4,1). $$

Only stages where $\sigma(k)\neq k$ are active.

$$ \begin{aligned} \theta_0 &= 0, & \tilde{\theta}_0 &= 0,\[2mm] \theta_1 &= \neg\mu_1 \wedge \mu_5 = \texttt{0x3333000033330000}, & \tilde{\theta}_1 &= \mu_1 \wedge \neg\mu_5 = \texttt{0x0000CCCC0000CCCC},\[2mm] \theta_2 &= 0, & \tilde{\theta}_2 &= 0,\[2mm] \theta_3 &= 0, & \tilde{\theta}_3 &= 0,\[2mm] \theta_4 &= 0, & \tilde{\theta}_4 &= 0,\[2mm] \theta_5 &= \neg\mu_5 \wedge \mu_1 = \texttt{0x0000CCCC0000CCCC}, & \tilde{\theta}_5 &= \mu_5 \wedge \neg\mu_1 = \texttt{0x3333000033330000}. \end{aligned} $$

These constructions follow directly from scheme (71): at each stage $k$, the masks select exactly those elements whose $k$-bit must be exchanged to reach their destination under the bit permutation, ensuring correct routing and bijectivity without assuming full bit-plane independence.