Section 7.1.3: Bitwise Tricks and Techniques

Exercise 51. [23] Let $c$ be a constant, $0 \le c < 2^d$. Find all sequences of masks $(\theta_0, \theta_1, \ldots, \theta_{d-1}, \tilde{\theta}_{d-2}, \ldots, \tilde{\theta}_1, \tilde{\theta}0)$ such that the general permutation scheme (71) takes $x \mapsto x^*$, where the bit permutation $\pi$ is defined by either (a) $j\pi = j \oplus c$; or (b) $j\pi = (j + c) \bmod 2^d$. [The masks should satisfy $\theta_k \subseteq \mu{d,k}$ and $\tilde{\theta}k \subseteq \mu{d,k}$, so that (71) corresponds to Fig. 12; see (48). Notice that reversal, $x^* = x^R$, is the special case $c = 2^d - 1$ of part (a), while part (b) corresponds to the cyclic right shift $x^S = (x \gg c) + (x \ll (2^d - c))$.]

Verified: yes
Solve time: 4m18s

---

Let the butterfly network (71) act on bit strings $x \in {0,1}^d$. At stage $k$ ($0 \le k \le d-1$), each switch corresponds to a pair

$$ (j,; j \oplus 2^k), \qquad j \in \mu_{d,k}, $$

where $j_k = 0$. A mask sequence is valid if at every stage each such pair is either routed straight or crossed, consistently with the image pair under $\pi$.

For a fixed permutation $\pi$, a stage $k$ switch is:

• straight if $\pi$ preserves the ordering of the pair in dimension $k$,
• crossed if $\pi$ reverses that ordering.

Equivalently, writing $b = j_k$, the switch is crossed iff the map $b \mapsto (\pi(j))_k$ flips the relative labeling of $(j, j \oplus 2^k)$.

(a) $\pi(j) = j \oplus c$

Write $c_k$ for the $k$-th bit of $c$. Then

$$ (\pi(j))_k = j_k \oplus c_k. $$

For the paired input $j \oplus 2^k$, the $k$-th bit flips, hence both outputs satisfy

$$ (\pi(j))_k = j_k \oplus c_k, \qquad (\pi(j \oplus 2^k))_k = (j_k \oplus 1) \oplus c_k. $$

Thus the pair is always mapped to another $k$-edge, and the relative order is:

• preserved if $c_k = 0$,
• reversed if $c_k = 1$.

Hence the masks are uniform on each stage:

$$ \theta_k = \begin{cases} \mu_{d,k}, & c_k = 1,\ \varnothing, & c_k = 0, \end{cases} \qquad \tilde{\theta}k = \begin{cases} \varnothing, & c_k = 1,\ \mu{d,k}, & c_k = 0. \end{cases} $$

(b) $\pi(j) = (j + c) \bmod 2^d$

Write

$$ j = a + b2^k,\qquad 0 \le a < 2^k,; b \in {0,1}, $$

and decompose

$$ c = c^{(k)} + c_k 2^k + c^{>k}, \qquad 0 \le c^{(k)} < 2^k. $$

Only the lower $k$ bits of $j$ influence the carry into position $k$. Define the carry

$$ \gamma_k(j) = \begin{cases} 1, & a + c^{(k)} \ge 2^k,\ 0, & a + c^{(k)} < 2^k. \end{cases} $$

Then the $k$-th output bit of addition is

$$ (\pi(j))_k = b \oplus c_k \oplus \gamma_k(j), $$

and for the paired element,

$$ (\pi(j \oplus 2^k))_k = (b \oplus 1) \oplus c_k \oplus \gamma_k(j), $$

since the carry into bit $k$ depends only on the lower $k$ bits and is unchanged when flipping bit $k$.

Thus the two outputs always differ in bit $k$, so the image is again a $k$-edge. The only issue is whether the edge is preserved or swapped.

Let

$$ u = (\pi(j))_k = b \oplus c_k \oplus \gamma_k(j). $$

A straight connection corresponds to $u = b$, and a crossed connection corresponds to $u = b \oplus 1$. Hence:

$$ \text{crossed} ;\Longleftrightarrow; c_k \oplus \gamma_k(j) = 1. $$

Therefore the mask at stage $k$ is completely determined by the lower $k$ bits of $j$:

$$ \theta_k

\left{ j \in \mu_{d,k} :; \gamma_k(j) \ne c_k \right}, \qquad \tilde{\theta}k = \mu{d,k} \setminus \theta_k. $$

In terms of residues $r = j \bmod 2^k$, this is

$$ \gamma_k(j)=1 ;\Longleftrightarrow; r \ge 2^k - (c \bmod 2^k), $$

so equivalently

$$ \theta_k

\left{ j \in \mu_{d,k} :; \bigl[(j \bmod 2^k) \ge 2^k - (c \bmod 2^k)\bigr] \oplus c_k = 1 \right}. $$

This is a periodic condition with period $2^k$, and within each stage $k$ block, all switches with the same lower $k$-bit pattern are treated identically.

Completeness

For each stage $k$, the computation shows:

• every $k$-switch maps to a $k$-switch under $\pi$,
• the orientation (straight vs crossed) is completely determined by $\gamma_k(j)$ and $c_k$,
• no other dependence on higher bits of $j$ occurs.

Hence the sets $\theta_k$ and $\tilde{\theta}_k$ above are necessary and sufficient, and the resulting mask sequence is uniquely determined by $c$. ∎