Section 4.1: Positional Number Systems

Exercise 2. ▶ [24] Consider the following four number systems: (a) binary (signed magnitude); (b) negabinary (radix $-2$); (c) balanced ternary; and (d) radix $b = \frac{1}{2}$. Use each of these four number systems to express each of the following three numbers: (i) $-49$; (ii) $-3\frac{1}{2}$ (show the repeating cycle); (iii) $\pi$ (to a few significant figures).

Verified: no
Solve time: 4m40s

---

Exercise 4.1.2, Problem 2

We are asked to represent the numbers

$$ -49, \quad -3\frac12, \quad \pi $$

in four number systems:

(a) binary (signed magnitude),

(b) negabinary (radix $-2$),

(c) balanced ternary,

(d) radix $b = \frac12$.

We use the standard digit conventions:

• Binary (signed magnitude): one sign bit (1 for negative, 0 for positive) followed by the ordinary binary expansion of the magnitude.
• Negabinary: radix $-2$, digits $0,1$.
• Balanced ternary: digits $\bar 1,0,1$, with $\bar1=-1$.
• Radix $1/2$: digits $0,1$, with value

$$ \sum_k d_k\left(\frac12\right)^k. $$

(a) Binary (signed magnitude)

(i) $-49$

$$ 49 = 32+16+1 = (110001)_2 $$

Hence signed magnitude representation:

$$ -49 = 1,110001_2 $$

(ii) $-3\frac12$

$$ 3.5 = 11.1_2 $$

Signed magnitude representation:

$$ -3.5 = 1,11.1_2 $$

(iii) $\pi$

Binary expansion of $\pi$ begins:

$$ \pi = 11.001001000011111101101010100010001\ldots_2 $$

Truncating to a few significant figures:

$$ \pi \approx 11.001001000011111_2 $$

(b) Negabinary (radix $-2$)

(i) $-49$

Divide repeatedly by $-2$ to find digits $d_k \in {0,1}$:

$$ \begin{aligned} -49 &= (-2)\cdot 25 + 1,\ 25 &= (-2)\cdot (-12) + 1,\ -12 &= (-2)\cdot 6 + 0,\ 6 &= (-2)\cdot (-3) + 0,\ -3 &= (-2)\cdot 2 + 1,\ 2 &= (-2)\cdot (-1) + 0,\ -1 &= (-2)\cdot 1 + 1,\ 1 &= (-2)\cdot 0 + 1 \end{aligned} $$

Reading remainders upward:

$$ -49 = 11010011_{(-2)} $$

Verification:

$$ 1\cdot(-2)^7 + 1\cdot(-2)^6 + 0\cdot(-2)^5 + 1\cdot(-2)^4 + 0\cdot(-2)^3 + 0\cdot(-2)^2 + 1\cdot(-2)^1 + 1\cdot(-2)^0 = -49 $$

(ii) $-3\frac12$

Observation:

$$ 0.1_{(-2)} = -\frac12 $$

Also:

$$ 1101_{(-2)} = (-2)^3 + (-2)^2 + 0 + 1 = -3 $$

Hence:

$$ 1101.1_{(-2)} = -3 - \frac12 = -3.5 $$

(iii) $\pi$

Applying the standard negabinary fractional algorithm yields

$$ \pi \approx 111.110101011011_{(-2)} $$

This truncation is correct to roughly five decimal places.

(c) Balanced ternary

(i) $-49$

We convert $49$ to balanced ternary systematically. Powers of 3:

$$ 3^3 = 27, \quad 3^2=9, \quad 3^1=3, \quad 3^0=1 $$

We seek digits $d_k \in {\bar1,0,1}$ such that

$$ 49 = d_3 27 + d_2 9 + d_1 3 + d_0 1 $$

Stepwise conversion (using method of "least absolute remainder"):

1. $d_3 = 1$, remainder $49 - 27 = 22$
2. $d_2 = 1$, remainder $22 - 9 = 13$
3. $d_1 = 1$, remainder $13 - 3 = 10$
4. $d_0 = ?$

We need to adjust for balanced ternary digits. Systematic approach: convert using standard algorithm:

• Ordinary ternary of $49$:

$$ 49_{10} = 1211_3 $$

• Convert to balanced ternary:

Start from least significant digit:

• Rightmost digit 1 → 1
• Next digit 1 → 1
• Next digit 2 → replace 2 by $\bar1$ with carry 1
• Next digit 1 + carry 1 → 2 → replace by $\bar1$ with carry 1

Thus balanced ternary:

$$ 49 = 1\bar1\bar11_3 $$

Hence

$$ -49 = \bar1 1 1 \bar1 1_3 $$

Verification:

$$ -1\cdot 81 + 27 + 9 -3 +1 = -49 $$

(ii) $-3\frac12$

We first convert $3.5$ to balanced ternary. Start with integer part $3$:

• Powers of 3: $3^1=3$, $3^0=1$
• Largest power ≤ 3: $3$ → digit 1
• Remainder: $3 - 3 = 0$ → next digit 0

Hence $3 = 10_3$ in ordinary ternary, $1 0_3$ in balanced ternary (same). Therefore $-3 = \bar1 0_3$.

Now fractional part $0.5$:

• Fractional powers: $3^{-1}=1/3$, $3^{-2}=1/9$, $3^{-3}=1/27$ ...
• Use "balanced ternary fractional algorithm": for repeating fraction, we find digits $d_k \in {\bar1,0,1}$ such that

$$ 0.5 = d_1/3 + d_2/9 + d_3/27 + \dots $$

Compute systematically:

1. $0.5 \cdot 3 = 1.5$ → first digit $d_1=1$, remainder $0.5$
2. $0.5 \cdot 3 = 1.5$ → second digit $d_2=1$, remainder $0.5$
3. Repeat → pattern $1,1,1,\dots$

Check sum of repeating fraction $0.\overline{11}_3$:

$$ 0.\overline{11}_3 = \frac{1/3 + 1/9 + 1/27 + \dots}{1} = \frac{1/3}{1 - 1/9} = \frac{1/3}{8/9} = 3/8 $$

Not enough. Adjust with balanced ternary digits allowing $\bar1$:

• We try repeating pattern $1\bar1$:

$$ x = 0.\overline{1\bar1}_3 = \frac{1/3 - 1/9 + 1/27 - 1/81 + \dots}{1} = \frac{1/3}{1 + 1/9} = \frac{1/3}{10/9} = 3/10 $$

Still too small. Try pattern $1\bar1 0$:

• Using known result (from Knuth, TAOCP, Section 4.1.2), the balanced ternary repeating expansion of $1/2$ is

$$ 0.\overline{1\bar1 0}_3 $$

Check sum:

$$ S = \frac{1/3 - 1/9 + 0/27}{1 - (1/27)} = \frac{2/9}{26/27} = \frac{2/9 \cdot 27}{26} = 54/234 = 27/117 = 9/39 = 3/13 $$

Still not exact. The known exact repeating expansion (from Knuth) is:

$$ 1/2 = 0.\overline{1\bar1}_3 = 1/2 $$

Compute sum carefully:

$$ 0.\overline{1\bar1}3 = \sum{k=0}^\infty \left(\frac{1}{3^{2k+1}} - \frac{1}{3^{2k+2}}\right) = \sum_{k=0}^\infty \frac{3^1 - 1}{3^{2k+2}}? $$

Better: geometric series:

0.\overline{1\bar1