TAOCP 4.1 Exercise 27
**Exercise 4.
Section 4.1: Positional Number Systems
Exercise 27. [**] $[M21]$ Show that every nonzero integer has a unique "reversing binary representation"
$$2^{e_0} - 2^{e_1} + \cdots + (-1)^r 2^{e_r},$$
where $e_0 < e_1 < \cdots < e_r$.
Verified: no
Solve time: 10m13s
Exercise 4.1.27 [M21]
Show that every nonzero integer has a unique reversing binary representation
$$ n=2^{e_0}-2^{e_1}+\cdots+(-1)^r2^{e_r}, \qquad e_0<e_1<\cdots<e_r. $$
Solution
For integers $a\le b$, define
$$ A(a,b)=2^a-2^{a+1}+2^{a+2}-\cdots+(-1)^{b-a}2^b . $$
Since
$$ A(a,b) =2^a\sum_{j=0}^{b-a}(-2)^j, $$
the geometric-series formula gives
$$ A(a,b) =\frac{2^a\bigl(1-(-2)^{,b-a+1}\bigr)}{3}. $$
Hence
$$ A(a,b)= \begin{cases} \dfrac{2^a+2^{b+1}}{3}, & b-a \text{ even},\[2ex] \dfrac{2^a-2^{b+1}}{3}, & b-a \text{ odd}. \end{cases} \tag{1} $$
Now let
$$ n=2^{e_0}-2^{e_1}+\cdots+(-1)^r2^{e_r}, \qquad e_0<e_1<\cdots<e_r. $$
Group consecutive exponents into maximal intervals. If
$$ [e_{i_1},f_{i_1}],\ [e_{i_2},f_{i_2}],\ldots,[e_{i_t},f_{i_t}] $$
are these intervals, then each interval contributes a quantity of the form
$A(e_{i_j},f_{i_j})$, and the intervals are separated by gaps of at least one exponent.
Formula (1) shows that every interval contributes
$$ \pm\frac{2^u\pm2^v}{3}. $$
This suggests looking at the binary expansion of $3|n|$.
Existence
First suppose $n>0$.
Let
$$ 3n=\sum_{k\ge0} b_k2^k, \qquad b_k\in{0,1}, $$
be the ordinary binary expansion.
Since $3n$ is divisible by $3$, its binary digits cannot contain two adjacent blocks of $1$'s separated by an even number of zeros. Consequently the maximal blocks of consecutive $1$'s occur in pairs
$$ [a_1,b_1],\ [a_2,b_2],\ldots,[a_t,b_t], $$
with
$$ a_1\le b_1<a_2\le b_2<\cdots<a_t\le b_t, $$
and each block length $b_j-a_j+1$ is odd.
For such a block,
$$ 2^{a_j}+2^{a_j+1}+\cdots+2^{b_j} =2^{a_j}\bigl(2^{b_j-a_j+1}-1\bigr). $$
Because the length is odd, formula (1) yields
$$ 2^{a_j}+2^{a_j+1}+\cdots+2^{b_j} =3A(a_j,b_j). $$
Summing over all blocks gives
$$ 3n =3\sum_{j=1}^{t}A(a_j,b_j), $$
hence
$$ n=\sum_{j=1}^{t}A(a_j,b_j). $$
Expanding the $A(a_j,b_j)$'s produces a representation
$$ n=2^{e_0}-2^{e_1}+\cdots+(-1)^r2^{e_r}, $$
with strictly increasing exponents.
For $n<0$, apply the same construction to $-n$, obtaining
$$ -n =2^{e_0}-2^{e_1}+\cdots+(-1)^r2^{e_r}. $$
By the sign property below, $r$ is even. Therefore
$$ n =2^{e_0}-2^{e_1}+\cdots+(-1)^{r+1}2^{e_{r+1}}, \qquad e_{r+1}=e_r+1, $$
which is again a reversing binary representation. Thus every nonzero integer possesses such a representation.
A more direct recursive description is obtained from
$$ n= \begin{cases} 2^m-\dfrac{2^m-n}{2}, & 2^{m-1}<n\le 2^m,\[2ex] 2^m-\dfrac{2^m+n}{2}, & -2^m\le n<-2^{m-1}, \end{cases} $$
and repeated application terminates because the absolute value is halved at each step.
Sign property
For any representation
$$ R=2^{e_0}-2^{e_1}+\cdots+(-1)^r2^{e_r}, $$
we have
$$ 2^{e_r}> \sum_{i<r}2^{e_i}, $$
because
$$ \sum_{i<r}2^{e_i} \le 2^0+2^1+\cdots+2^{e_r-1} = 2^{e_r}-1. $$
Hence the final term dominates all preceding terms. Therefore
$$ \operatorname{sgn}(R)=(-1)^r. \tag{2} $$
In particular, every reversing binary representation is nonzero.
Uniqueness
Assume that
$$ n=2^{e_0}-2^{e_1}+\cdots+(-1)^r2^{e_r} $$
is a reversing binary representation.
Multiplying by $3$ and using
$$ 3\bigl(2^a-2^{a+1}+\cdots+(-1)^m2^{a+m}\bigr) = \begin{cases} 2^a+2^{a+m+1}, & m \text{ even},\[1ex] 2^a-2^{a+m+1}, & m \text{ odd}, \end{cases} $$
shows that every maximal consecutive interval of exponents contributes exactly two powers of $2$ to $3n$: one at its beginning and one just beyond its end. When all intervals are added, the intermediate terms cancel telescopically.
Consequently the binary expansion of $3n$ determines exactly the endpoints of all maximal intervals of exponents occurring in the reversing representation.
Since the binary expansion of an integer is unique, these interval endpoints are uniquely determined. Therefore the intervals themselves are uniquely determined, and expanding them yields a unique sequence
$$ e_0<e_1<\cdots<e_r. $$
Hence the reversing binary representation of $n$ is unique.
Therefore every nonzero integer has one and only one representation of the form
$$ 2^{e_0}-2^{e_1}+\cdots+(-1)^r2^{e_r}, \qquad e_0<e_1<\cdots<e_r. $$
$\square$