TAOCP 7.1.3 Exercise 140

Let $x,y,z \in {0,+1,-1}$.

taocpmathematicsalgorithmsvolume-4hard

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 140. [27] [27] Design an economical full adder for balanced ternary numbers: Show how to compute signed bits u and v such that 3u + v = x+ y + z when x, y, z ∈{0, +1, −1}.

Verified: yes
Solve time: 1m18s

Setup

Let $x,y,z \in {0,+1,-1}$. Let

$s = x+y+z.$

Then $s \in {-3,-2,-1,0,1,2,3}$.

We seek signed bits $u,v \in {0,+1,-1}$ such that

$3u + v = s.$

The task is to define $u$ and $v$ as functions of $s$ and verify that both always remain signed bits and satisfy the identity for every admissible value of $s$.

Solution

Define $u$ and $v$ by the following case analysis on $s$.

For $s = 3$, take $u = 1$ and $v = 0$, giving $3u+v = 3$.

For $s = 2$, take $u = 1$ and $v = -1$, giving $3u+v = 3-1 = 2$.

For $s = 1$, take $u = 0$ and $v = 1$, giving $3u+v = 1$.

For $s = 0$, take $u = 0$ and $v = 0$, giving $3u+v = 0$.

For $s = -1$, take $u = 0$ and $v = -1$, giving $3u+v = -1$.

For $s = -2$, take $u = -1$ and $v = 1$, giving $3u+v = -3+1 = -2$.

For $s = -3$, take $u = -1$ and $v = 0$, giving $3u+v = -3$.

This defines a function $(u,v)$ on all possible values of $s$.

Each assignment uses only values from ${0,+1,-1}$, so both $u$ and $v$ are signed bits in every case.

Verification

Each case satisfies $3u+v=s$ by direct substitution.

The mapping covers all possible values of $s$ since $x+y+z$ ranges exactly over ${-3,-2,-1,0,1,2,3}$ for $x,y,z \in {0,+1,-1}$.

For each case, $u$ is chosen so that $3u$ is the unique multiple of $3$ closest to $s$ in ${-3,0,3}$, and $v$ is the signed-bit correction placing the result exactly at $s$. This ensures $s-3u \in {-1,0,1}$ in every case, so $v=s-3u$ always lies in the allowed digit set.

This completes the proof. ∎

Notes

The construction realizes a redundant base-$3$ digit expansion of $s$ with digit set ${-1,0,1}$ at both positions. The most significant digit $u$ captures the coarse ternary magnitude of $s$, while $v$ resolves the residual in a bounded correction step.