TAOCP 7.1.3 Exercise 93

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 93. [18] [18] What basic formula for subtraction is analogous to formula (8q) for addition?

Verified: no
Solve time: 5m11s

Solution

Formula (8q) for addition states the bitwise decomposition

$x + y = (x \oplus y) + 2(x \mathbin{&} y).$

To obtain the subtraction analogue, write

$x - y = x + (-y).$

Using $,-y = \bar{y} + 1,$ from (16),

$x - y = x + \bar{y} + 1.$

Apply the addition formula to $x + \bar{y}$:

$x + \bar{y} = (x \oplus \bar{y}) + 2(x \mathbin{&} \bar{y}).$

Substituting gives

$x - y = (x \oplus \bar{y}) + 2(x \mathbin{&} \bar{y}) + 1.$

Use the identity $x \oplus \bar{y} = \overline{x \oplus y}$ from (14), hence

$x - y = \overline{x \oplus y} + 2(x \mathbin{&} \bar{y}) + 1.$

Since $\overline{t} + 1 = -t$ by (17), this yields

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

Multiply by $-1$ and rearrange using $a - 2b = (a \oplus y) - 2((\bar{x}) \mathbin{&} y)$ in symmetric form, obtaining the clean symmetric identity

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

Equivalently,

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

Thus subtraction is expressed as a bitwise sum of a “difference without borrow” term and a correction term determined by borrow generation.

$$ \boxed{x - y = (x \oplus y) - 2((\bar{x}) \mathbin{&} y)} $$