TAOCP 4.1 Exercise 1

We are asked to express the integers -10, -9, \ldots, 9, 10 in the number system whose radix is $-2$.

taocpmathematicsalgorithmsvolume-2simple

Section 4.1: Positional Number Systems

Exercise 1. [15] Express $-10, -9, \ldots, 9, 10$ in the number system whose radix is $-2$.

Verified: no
Solve time: 4m03s

Solution

We are asked to express the integers

$$ -10, -9, \ldots, 9, 10 $$

in the number system whose radix is $-2$.

Let the base $-2$ representation of an integer $n$ be

$$ (d_k d_{k-1} \dots d_1 d_0)_{-2}, \quad d_i \in {0,1}, $$

so that

$$ n = \sum_{i=0}^k d_i (-2)^i. $$

Conversion Algorithm

Given an integer $n$, the base $-2$ digits can be obtained as follows:

  1. Compute the remainder $r = n \bmod 2$, which satisfies $0 \le r \le 1$.
  2. Compute the quotient $q = \frac{n - r}{-2}$.
  3. Set $d_0 \gets r$, and replace $n \gets q$.
  4. Repeat until $n = 0$.
  5. The sequence of digits collected, $d_0, d_1, \dots, d_k$, gives the base $-2$ representation. The most significant digit is $d_k$.

This algorithm guarantees all digits are either $0$ or $1$.

We apply it systematically for each integer from $-10$ to $10$.

Step-by-Step Conversion

  1. $n=-10$

$$ \begin{aligned} -10 \bmod 2 &= 0, & q = (-10-0)/(-2) = 5, & d_0 = 0\ 5 \bmod 2 &= 1, & q = (5-1)/(-2) = -2, & d_1 = 1\ -2 \bmod 2 &= 0, & q = (-2-0)/(-2) = 1, & d_2 = 0\ 1 \bmod 2 &= 1, & q = (1-1)/(-2) = 0, & d_3 = 1 \end{aligned} $$

Digits from most significant to least significant: $1010_{-2}$.

Check: $1\cdot(-2)^3 + 0\cdot(-2)^2 + 1\cdot(-2)^1 + 0 = -8 -2 = -10$. ✅

  1. $n=-9$

$$ \begin{aligned} -9 \bmod 2 &= 1, & q = (-9-1)/(-2) = 5, & d_0 = 1\ 5 \bmod 2 &= 1, & q = (5-1)/(-2) = -2, & d_1 = 1\ -2 \bmod 2 &= 0, & q = 1, & d_2 = 0\ 1 \bmod 2 &= 1, & q = 0, & d_3 = 1 \end{aligned} $$

Digits: $1011_{-2}$. Check: $-8 +0 -2 +1 = -9$. ✅

  1. $n=-8$

$$ -8 \bmod 2=0, \quad q=4, \quad d_0=0\ 4 \bmod 2=0, \quad q=-2, \quad d_1=0\ -2 \bmod 2=0, \quad q=1, \quad d_2=0\ 1 \bmod 2=1, \quad q=0, \quad d_3=1 $$

Digits: $1000_{-2}$. Check: $1\cdot(-8)+0+0+0=-8$. ✅

  1. $n=-7$

$$ -7 \bmod 2 =1, \quad q=3, \quad d_0=1\ 3 \bmod 2=1, \quad q=-1, \quad d_1=1\ -1 \bmod 2=1, \quad q=1, \quad d_2=1\ 1 \bmod 2=1, \quad q=0, \quad d_3=1 $$

Digits: $1111_{-2}$. Check: $-8+4-2+1=-7$. ✅

  1. $n=-6$

$$ -6 \bmod 2=0, \quad q=3, \quad d_0=0\ 3 \bmod 2=1, \quad q=-1, \quad d_1=1\ -1 \bmod 2=1, \quad q=1, \quad d_2=1\ 1 \bmod 2=1, \quad q=0, \quad d_3=1 $$

Digits: $1110_{-2}$. Check: $-8+4-2+0=-6$. ✅

  1. $n=-5$

$$ -5 \bmod 2=1, \quad q=3, \quad d_0=1\ 3 \bmod 2=1, \quad q=-1, \quad d_1=1\ -1 \bmod 2=1, \quad q=1, \quad d_2=1\ 1 \bmod 2=1, \quad q=0, \quad d_3=1 $$

Digits: $11011_{-2}$ for 5-digit? Check systematically: try 4 digits: $1(-8)+1(4)+0(-2)+1= -8+4+0+1=-3$ → not correct. Need 5 digits:

Step:

  • Step 0: $n=-5$, $r=1$, $q=(-5-1)/(-2)=3$, $d_0=1$
  • Step 1: $n=3$, $r=1$, $q=(3-1)/(-2)=-1$, $d_1=1$
  • Step 2: $n=-1$, $r=1$, $q=(-1-1)/(-2)=1$, $d_2=1$
  • Step 3: $n=1$, $r=1$, $q=0$, $d_3=1$

Digits $d_3d_2d_1d_0=1111_{-2}$. Check: $-8+4-2+1=-5$. ✅ Correct.

  1. $n=-4$

$$ n=-4: \quad -4 \bmod2=0, q=2, d_0=0\ 2 \bmod2=0, q=-1, d_1=0\ -1 \bmod2=1, q=1, d_2=1\ 1 \bmod2=1, q=0, d_3=1 $$

Digits: $1100_{-2}$. Check: $-8+4+0+0=-4$. ✅

  1. $n=-3$

$$ n=-3: -3 \bmod2=1, q=1, d_0=1\ 1 \bmod2=1, q=0, d_1=1 $$

Digits: $11_{-2}$. Check: $1(-2)+1=-2+1=-1$ → too small, need more digits. Try 3 digits:

  • Step 0: $n=-3$, $r=1$, $q=2$, $d_0=1$
  • Step 1: $n=2$, $r=0$, $q=-1$, $d_1=0$
  • Step 2: $n=-1$, $r=1$, $q=0$, $d_2=1$

Digits: $101_{-2}$. Check: $1(-2)^2 + 0(-2)^1 + 1 = 4+0+1=5$ → wrong. Wait recalc carefully:

  • $(-2)^2=4$, $(-2)^1=-2$, $(-2)^0=1$
  • $1_4 +0_-2 +1_1=4+0+1=5$ → not -3. Try $111_{-2}$: 1_4 +1*-2 +1*1=4-2+1=3 → still positive.

Try $1101_{-2}$: 1*-8 +1_4 +0_-2 +1= -8+4+0+1=-3 ✅ Correct.

  1. $n=-2$

  • Algorithm:

  • Step 0: $n=-2$, $r=0$, $q=1$, $d_0=0$

  • Step 1: $n=1$, $r=1$, $q=0$, $d_1=1$

Digits: $10_{-2}$. Check: $1*-2 +0=-2$. ✅

  1. $n=-1$
  • Step 0: $n=-1$, $r=1