TAOCP 7.1.3 Exercise 96

For (93), the addition identity in (8q) has the form $x + y = (x \oplus y) + 2(x \,\&\, y).$ The subtraction analogue is obtained by replacing addition with subtraction and replacing carry propagation...

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 96. [21] Explain (93), and find a similar formula that sets test flags $t_j \leftarrow 128[x_j \le y_j]$.

Verified: no
Solve time: 4m25s

Solution

For (93), the addition identity in (8q) has the form

$x + y = (x \oplus y) + 2(x ,&, y).$

The subtraction analogue is obtained by replacing addition with subtraction and replacing carry propagation by borrow propagation. A borrow occurs exactly in those bit positions where $y$ has a $1$ and $x$ has a $0$, namely where $\bar{x} ,&, y = 1$. Borrow propagation shifts left by one bit, giving $2(\bar{x} ,&, y)$. Therefore

$x - y = (x \oplus y) - 2(\bar{x} ,&, y).$

Using shift notation from (19),

$x - y = (x \oplus y) - \big((\bar{x} ,&, y) \ll 1\big).$

This expresses subtraction as a bitwise sum corrected by the propagated borrow term.

To obtain test flags for bytewise comparison, write

$x = (x_7 \ldots x_0){256}, \qquad y = (y_7 \ldots y_0){256}.$

Each digit $x_j, y_j$ lies in ${0,\ldots,255}$ and arithmetic on these digits is interpreted independently modulo $256$.

For a fixed byte position $j$, consider the quantity

$d_j = (y_j - x_j - 1) \bmod 256.$

If $x_j \le y_j$, then $y_j - x_j - 1 \ge -1$, so after reduction modulo $256$ the result lies in ${255, 254, \ldots, 128}$. In particular the most significant bit of $d_j$ equals $1$ exactly in this case. If $x_j > y_j$, then $y_j - x_j - 1 \le -2$, so $d_j \in {127, \ldots, 0}$ and its most significant bit is $0$.

Hence the indicator $[x_j \le y_j]$ is given by the top bit of $d_j$, namely

$[x_j \le y_j] = \left(\frac{d_j}{128}\right).$

Therefore the required test flags are obtained by scaling this bit:

$t_j = 128[x_j \le y_j] = (y_j - x_j - 1) ,&, 128.$

Equivalently, using bit extraction,

$t_j = \big((y_j - x_j - 1) ,&, 128\big).$

Combining all bytes in parallel gives the word-level form

$t = (y - x - 1) ,&, (128 \cdot (1 + 256 + \cdots + 256^7)).$

This completes the derivation of both the subtraction identity and the bytewise comparison flags. ∎