TAOCP 7.1.3 Exercise 137
We restart from a correct packed-word model and derive the operation at the level of bitplanes, ensuring that every symbol is handled as a complete 2-bit field.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 137. [21] [21] Show that the operation in exercise 136(c) is simpler with packed vectors like (131) than with the unpacked form (130).
Verified: yes
Solve time: 3m58s
We restart from a correct packed-word model and derive the operation at the level of bitplanes, ensuring that every symbol is handled as a complete 2-bit field.
We encode the elements of ${a,b,c}$ as
$$ a=00,\quad b=01,\quad c=10, $$
and a packed vector is a word consisting of $m$ such disjoint 2-bit fields. Let $x_1,x_0$ denote the two bitplanes of the packed word $X$, and similarly $y_1,y_0$ for $Y$.
The operation from exercise 136(c) is
$$ a\circ y=a,\quad b\circ a=a,\quad b\circ b=a,\quad b\circ c=c,\quad c\circ y=y. $$
We introduce fieldwise indicator masks computed from $X$:
$$ A = \neg x_1 \wedge \neg x_0,\quad B = \neg x_1 \wedge x_0,\quad C = x_1 \wedge \neg x_0. $$
These are 1-bit-per-field masks. When used with a bitplane such as $y_1$ or $y_0$, they are automatically broadcast across the corresponding bitplane, so $C \wedge y_1$ means “select the first bit of $Y$ in all fields where $x=c$”, and similarly for other combinations.
We also need the indicator for $y=c$:
$$ C_Y = y_1 \wedge \neg y_0. $$
Now we compute the result bitplanes $z_1,z_0$.
Case decomposition
If $x=c$, then the operation copies $y$, hence contributes
$$ z_1 \leftarrow C \wedge y_1,\quad z_0 \leftarrow C \wedge y_0. $$
If $x=b$, then the result is $c$ exactly when $y=c$, and $a$ otherwise. Since $c=10$, this contributes only to the high bit:
$$ z_1 \leftarrow B \wedge C_Y,\quad z_0 \leftarrow 0. $$
If $x=a$, the result is always $a=00$, contributing nothing.
Combination
Combining the two nontrivial cases gives
$$ z_1 = (C \wedge y_1)\ \vee\ (B \wedge C_Y), $$
$$ z_0 = C \wedge y_0. $$
These are standard word-level Boolean operations applied in parallel to all $m$ fields, with no interaction between fields because each bitplane is processed uniformly and field boundaries are fixed.
Correctness of packing
Each operation above acts on entire bitplanes, not on individual bits within fields, so every 2-bit symbol is treated as a unit. There are no carries or cross-field interactions, since only bitwise $\wedge,\vee,\neg$ are used on fixed-width words.
Comparison with unpacked representation
In the unpacked representation (130), each coordinate $x_i \circ y_i$ requires evaluating a 3-by-3 table entry separately, hence $m$ independent constant-time operations.
In the packed representation (131), the entire vector operation is computed using a fixed number of word-level operations:
$$ \neg,\ \wedge,\ \vee \text{ on } x_1,x_0,y_1,y_0, $$
namely a constant number of Boolean combinations independent of $m$.
Thus the operation becomes a small fixed circuit acting on whole words, rather than $m$ separate table lookups. This is the sense in which the packed-vector form is simpler. ∎