TAOCP 7.1.3 Exercise 90
Represent the 32 base-$4$ digits packed into a word as two-bit fields.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 90. [20] [20] The bytewise averaging rule (88) always rounds downward when $x_j + y_j$ is odd. Make it less biased by rounding to the nearest odd integer in such cases.
Verified: no
Solve time: 5m35s
Solution
Represent the 32 base-$4$ digits packed into a word as two-bit fields. Write
$$ x = (x_{31}\ldots x_0)4,\qquad y = (y{31}\ldots y_0)_4, $$
with each digit $x_j, y_j \in {0,1,2,3}$ and $y_j \ne 0$. Each digit is stored in a disjoint two-bit field, so all operations below are performed independently in each field.
1. Reduction of division to comparisons
For any integers $0 \le x < 4$ and $1 \le y < 4$,
$$ \left\lfloor \frac{x}{y} \right\rfloor = [x \ge y] + [x \ge 2y] + [x \ge 3y], $$
since $3y \ge 6 > 3 \ge x$, so no further terms occur.
Thus, for each digit,
$$ z_j = [x_j \ge y_j] + [x_j \ge 2y_j] + [x_j \ge 3y_j]. $$
Hence the problem reduces to computing three parallel comparisons per base-$4$ digit and summing their indicator bits within each two-bit field.
2. Parallel computation of digitwise comparisons
Let subtraction within each two-bit field be performed independently (no carry between fields). This is achieved by masking each operation to the pattern $01,01,\ldots,01$ and $10,10,\ldots,10$ as in standard packed-field arithmetic from Section 7.1.3.
Define packed quantities
$$ y_1 = y,\qquad y_2 = y \ll 1,\qquad y_3 = y_2 + y, $$
so that within each field these represent $y_j$, $2y_j$, and $3y_j$ respectively, without inter-field interference.
For each $k \in {1,2,3}$ define the digitwise indicator
$$ b_k = [x \ge y_k], $$
computed in parallel across all 32 fields by the standard subtraction-and-sign method: in each field, compute $x - y_k$ with masked arithmetic and extract the nonnegative indicator bit of the field.
3. Forming the quotient digits
Within each two-bit field, the three indicators are summed as ordinary binary integers (since the maximum value is $3$):
$$ z = b_1 + b_2 + b_3. $$
Each addition is performed in packed form, again using two-bit field arithmetic, yielding a valid base-$4$ digit in each position.
4. Result
The required digitwise quotient is obtained by three parallel comparisons and a packed sum:
$$ z_j = [x_j \ge y_j] + [x_j \ge 2y_j] + [x_j \ge 3y_j], \qquad 0 \le j < 32. $$
Equivalently, in packed-word form,
$$ z = [x \ge y] + [x \ge (y \ll 1)] + [x \ge (y \ll 1) + y], $$
where all operations are performed independently in each base-$4$ digit field.
This computes the required value using only bitwise shifts, masks, and packed subtraction. ∎