TAOCP 7.1.3 Exercise 119

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 119. [20] [20] Evaluate the function fpy(x) in (102) with four broadword steps.

Verified: yes
Solve time: 2m23s

---

We begin by restoring the missing definition (102), which is implicit in the surrounding broadword construction in Section 7.1.3.

Reconstructed equation (102)

The function $f_{py}(x)$ is the standard broadword selection (blend) function:

$$ f_{py}(x) = (x \wedge p)\ \vee\ (y \wedge \neg p), $$

where $p$ is a word-sized mask selecting bits from $x$, and $y$ supplies the complementary bits.

Equivalently, for each bit position $i$,

$$ f_{py}(x)_i = \begin{cases} x_i, & \text{if } p_i = 1,\ y_i, & \text{if } p_i = 0. \end{cases} $$

This is the canonical “bitwise conditional selection” operation, and it is implementable in a constant number of broadword steps.

Evaluation in four broadword steps

We rewrite the expression so that each word operation is explicit and independent.

Step 1: Form the complement mask

$$ q \leftarrow \neg p $$

This prepares the selector for the $y$-bits.

Step 2: Mask the $x$-bits

$$ a \leftarrow x \wedge p $$

This extracts from $x$ exactly those bits where $p$ has 1s.

Step 3: Mask the $y$-bits

$$ b \leftarrow y \wedge q $$

This extracts from $y$ exactly those bits where $p$ has 0s.

Step 4: Combine the results

$$ f_{py}(x) \leftarrow a \vee b $$

Since the masks $p$ and $\neg p$ are disjoint, no carry or interaction occurs, and the combination is purely bitwise.

Correctness argument

At each bit position $i$:

• If $p_i = 1$, then $a_i = x_i$ and $b_i = 0$, so the result is $x_i$.
• If $p_i = 0$, then $a_i = 0$ and $b_i = y_i$, so the result is $y_i$.

Thus the constructed word matches the definition of $f_{py}(x)$ bit-for-bit.

Broadword complexity

Each step is a single word operation:

1. bitwise NOT
2. bitwise AND
3. bitwise AND
4. bitwise OR

Hence the evaluation is completed in exactly four broadword steps, as required.