TAOCP 4.1 Exercise 34

We are asked to represent an integer $n$ in a **balanced binary form**, that is, as $(\ldots a_2 a_1 a_0)_2 = \sum_{i=0}^{\infty} a_i 2^i, \quad a_i \in \{-1, 0, 1\},$ using the **fewest nonzero digit...

taocpmathematicsalgorithmsvolume-2medium

Section 4.1: Positional Number Systems

Exercise 34. ▶ [22] (G. W. Reitwiesner, 1960.) Explain how to represent a given integer $n$ in the form $(\ldots a_2 a_1 a_0)_2$, where each $a_i$ is $-1$, 0, or 1, using the fewest nonzero digits.

Verified: yes
Solve time: 3m41s

Solution

We are asked to represent an integer $n$ in a balanced binary form, that is, as

$(\ldots a_2 a_1 a_0)2 = \sum{i=0}^{\infty} a_i 2^i, \quad a_i \in {-1, 0, 1},$

using the fewest nonzero digits. Such a representation is sometimes called a minimal signed-digit binary representation or Reitwiesner representation.

Let $n \ge 0$ be given; the negative case follows by negating all digits.

We construct the representation recursively from the least significant bit upward. Let $n_0 = n$. For $i \ge 0$, define $a_i$ and the carry $c_{i+1}$ as follows:

  1. Compute $r_i = n_i \bmod 2$. Then $r_i \in {0,1}$.
  2. Set

$$ a_i = \begin{cases} 0, & r_i = 0,\[2mm] 1, & r_i = 1 \text{ and } \left\lfloor \dfrac{n_i}{2} \right\rfloor \text{ even},\[1mm] -1, & r_i = 1 \text{ and } \left\lfloor \dfrac{n_i}{2} \right\rfloor \text{ odd}. \end{cases} $$ 3. Compute the next carry (or residual) as

$$ n_{i+1} = \frac{n_i - a_i}{2}. $$

Continue this procedure until $n_{i+1} = 0$.

Justification of minimality

Suppose $n_i \equiv 1 \pmod 2$. We must choose $a_i \in {-1,1}$ to ensure $n_{i+1} = (n_i - a_i)/2$ is an integer. To minimize the number of nonzero digits, we pick $a_i$ so that $n_{i+1}$ is even whenever possible, since an even number can contribute zero to the next digit. This choice ensures that two consecutive nonzero digits never appear, which is exactly the condition for minimal Hamming weight in the balanced binary representation. By construction, each step either produces $a_i = 0$ or propagates a carry of minimal magnitude, and the process terminates after $\lfloor \log_2 n \rfloor + 1$ steps.

Example

Let $n = 23$. We compute $a_0, a_1, \ldots$:

  • $i=0$: $n_0 = 23$, $r_0 = 23 \bmod 2 = 1$, $\lfloor 23/2 \rfloor = 11$ odd $\implies a_0 = -1$, $n_1 = (23 - (-1))/2 = 12$.
  • $i=1$: $n_1 = 12$, $r_1 = 12 \bmod 2 = 0 \implies a_1 = 0$, $n_2 = 12/2 = 6$.
  • $i=2$: $n_2 = 6$, $r_2 = 0 \implies a_2 = 0$, $n_3 = 3$.
  • $i=3$: $n_3 = 3$, $r_3 = 1$, $\lfloor 3/2 \rfloor = 1$ odd $\implies a_3 = -1$, $n_4 = (3 - (-1))/2 = 2$.
  • $i=4$: $n_4 = 2$, $r_4 = 0 \implies a_4 = 0$, $n_5 = 1$.
  • $i=5$: $n_5 = 1$, $r_5 = 1$, $\lfloor 1/2 \rfloor = 0$ even $\implies a_5 = 1$, $n_6 = (1 - 1)/2 = 0$.

Thus, the minimal signed-digit binary representation of $23$ is

$(1,0,0, -1, 0, -1)_2,$

or, written from $a_5$ to $a_0$:

$(1,0,0, -1, 0, -1)_2.$

Proof of uniqueness

Suppose there exist two representations with fewer nonzero digits. Let $i$ be the least index where the digits differ. Then the difference $2^i (a_i - a'_i)$ must equal a sum of higher powers of two with coefficients in ${-1,0,1}$, which is impossible unless $a_i = a'_i$ by minimality, a contradiction. Hence the representation is unique.

This completes the proof.

∎

Summary

  1. At each step, select $a_i \in {-1,0,1}$ so that $(n_i - a_i)/2$ is an integer and, when possible, even.
  2. Continue until the residual is zero.
  3. The resulting representation has the fewest nonzero digits and is unique.

$$ \boxed{(\ldots a_2 a_1 a_0)_2 \text{ with minimal Hamming weight}} $$