TAOCP 7.1.3 Exercise 4

Using identity (16) in Section 7.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 4. ▶ [M16] Let $x^C = \bar{x}$, $x^N = -x$, $x^P = x + 1$, and $x^P = x - 1$ denote the complement, the negative, the successor, and the predecessor of an infinite-precision integer $x$. Then we have $x^{CC} = x^{NN} = x^{SP} = x^{PS} = x$. What are $x^{CN}$ and $x^{NC}$?

Verified: yes
Solve time: 1m37s

Solution

Using identity (16) in Section 7.1.3,

$-x = \bar{x} + 1,$

so

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

Computation of $x^{CN}$

By definition $x^C = \bar{x}$. Hence

$x^{CN} = (-x^C) = -\bar{x}.$

Using $\bar{x} = -x - 1$,

$-\bar{x} = -(-x - 1) = x + 1.$

Thus

$x^{CN} = x + 1,$

which is the successor operation $x^S$.

Computation of $x^{NC}$

By definition $x^N = -x$. Hence

$x^{NC} = \overline{x^N} = \overline{-x}.$

Using again $\bar{y} = -y - 1$ with $y = -x$,

$\overline{-x} = -(-x) - 1 = x - 1.$

Thus

$x^{NC} = x - 1,$

which is the predecessor operation $x^P$.

This completes the proof. ∎