TAOCP 7.1.3 Exercise 71
Let $\theta_0,\theta_1,\ldots,\theta_{d-1}$ be the masks used in compression procedure (80).
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 71. [20] Explain how to reverse the procedure of (80), going from the compact value $y = (y_{r-1} \ldots y_1 y_0)2$ to a number $z = (z{63} \ldots z_1 z_0)2$ that has $z{j_i} = y_i$ for $0 \le i < r$.
Verified: no
Solve time: 3m45s
Solution
Let $\theta_0,\theta_1,\ldots,\theta_{d-1}$ be the masks used in compression procedure (80). These masks are pairwise disjoint, and each bit position selected by the compression scheme belongs to exactly one $\theta_i$. Let $y = (y_{r-1}\ldots y_1 y_0)_2$, where each $y_i \in {0,1}$ represents the packed value obtained by the forward compression.
The inverse problem is to construct a word $z$ such that, for every original bit position $j_i$ selected in the compression, the bit of $z$ at position $j_i$ equals $y_i$, and all other bit positions are $0$.
Each $\theta_i$ acts as the characteristic mask of the set of bit positions assigned to the $i$th component of the compression. Since the sets are disjoint, bitwise combination of masked contributions produces no interference.
For each $i$, the value $y_i$ is extracted from $y$ by
$$ y_i = (y \gg i) ,&, 1, $$
by definition of bit extraction in Section 7.1.3.
Define
$$ z = \bigvee_{i=0}^{r-1} \bigl( (y_i \cdot \theta_i) \bigr), $$
where multiplication by $y_i \in {0,1}$ is ordinary integer multiplication, so that $y_i \cdot \theta_i$ equals $\theta_i$ if $y_i = 1$ and equals $0$ otherwise. Because the masks $\theta_i$ are disjoint, the bitwise OR coincides with ordinary addition, so this construction is well-defined in the integer representation used in Section 7.1.3.
For any bit position $k$, there exists at most one index $i$ such that the $k$th bit of $\theta_i$ is $1$. If no such $i$ exists, the $k$th bit of $z$ is $0$. If such an $i$ exists, the $k$th bit of $z$ equals the corresponding bit of $y_i$, since $y_i \cdot \theta_i$ contributes exactly $\theta_i$ when $y_i = 1$ and contributes nothing otherwise. Hence the $k$th bit of $z$ equals the bit that was placed into position $k$ by compression.
This reconstructs all original bit positions indexed by the compression mapping, since every such position lies in exactly one mask $\theta_i$. No other bit positions are altered, since they lie in no $\theta_i$ and remain $0$.
Therefore the reverse transformation of (80) is implemented by distributing each bit of $y$ into its corresponding mask and combining the results.
This completes the construction. ∎