TAOCP 7.1.3 Exercise 139
Represent each signed bit $x \in {-1,0,1}$ by two signed bits $(x^+,x^-)$ defined by x^+ = \begin{cases} 1 & x=1\\ 0 & x\in\{0,-1\} \end{cases}
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 139. [25] [25] If x and y are signed bits 0, +1, or −1, what 2-bit encoding is good for calculating their sum (z1z2)3 = x + y, where z1 and z2 are also required to be signed bits? (This is a “half adder” for balanced ternary numbers.)
Verified: yes
Solve time: 1m30s
Solution
Represent each signed bit $x \in {-1,0,1}$ by two signed bits $(x^+,x^-)$ defined by
$$ x^+ = \begin{cases} 1 & x=1\ 0 & x\in{0,-1} \end{cases} \qquad x^- = \begin{cases} 1 & x=-1\ 0 & x\in{0,1} \end{cases} $$
so that the encoding is
$$ 1 \mapsto (0,1), \quad 0 \mapsto (0,0), \quad -1 \mapsto (1,0). $$
The consistency condition $x^+ ,&, x^- = 0$ holds for all valid encodings.
Let $y$ be encoded similarly as $(y^+,y^-)$. The arithmetic identities
$$ x = x^+ - x^-, \qquad y = y^+ - y^- $$
hold since each variable takes values in ${-1,0,1}$.
Define the sum $s = x+y$. Then
$$ s = (x^+ + y^+) - (x^- + y^-). $$
The balanced ternary representation requires digits $z_1,z_2 \in {-1,0,1}$ such that
$$ s = 3z_1 + z_2. $$
For each possible value of $s \in {-2,-1,0,1,2}$, solving $3z_1+z_2=s$ with $z_1,z_2 \in {-1,0,1}$ yields the unique table
$$ 2 \mapsto (1,-1), \quad 1 \mapsto (0,1), \quad 0 \mapsto (0,0), \quad -1 \mapsto (0,-1), \quad -2 \mapsto (-1,1). $$
To compute $z_1$, only the extreme cases $s=2$ and $s=-2$ contribute nonzero values. The condition $s=2$ occurs exactly when $x=y=1$, and $s=-2$ occurs exactly when $x=y=-1$. Hence
$$ z_1 = (x^+ ,&, y^+) - (x^- ,&, y^-). $$
The quantity $z_2$ is determined from $z_2 = s - 3z_1$. Substituting $s = (x^+ + y^+) - (x^- + y^-)$ gives
$$ z_2 = (x^+ + y^+) - (x^- + y^-) - 3\bigl((x^+ ,&, y^+) - (x^- ,&, y^-)\bigr). $$
The pair $(z_1,z_2)$ produced by these formulas always lies in ${-1,0,1}^2$, since each term $x^+,x^-,y^+,y^-$ is binary-valued and the correction term subtracts exactly the overflow cases corresponding to $|s|=2$.
The encoding therefore permits computation of the balanced ternary half-adder using only signed-bit arithmetic and bitwise conjunction on indicator components. This completes the construction. ∎