TAOCP 4.1 Exercise 11
Let s_i=a_i+b_i+t_i, where $t_i$ is the carry entering position $i$.
Section 4.1: Positional Number Systems
Exercise 11. [**] [22] Design an algorithm that uses the $-2$ number system to compute the sum of $(a_n \ldots a_1 a_0){-2}$ and $(b_n \ldots b_1 b_0){-2}$, obtaining the answer $(c_{n+2} \ldots c_1 c_0)_{-2}$.
Verified: yes
Solve time: 1m27s
Let
$$ s_i=a_i+b_i+t_i, $$
where $t_i$ is the carry entering position $i$. Since
$$ (-2)^i+(-2)^i=2(-2)^i=-(-2)^{i+1}, $$
a carry in radix $-2$ may be negative. Write
$$ s_i=c_i-2t_{i+1}, $$
with $c_i\in{0,1}$ and $t_{i+1}\in{-1,0,1}$ chosen so that the equality holds.
For each position $i=0,1,\ldots,n$, compute $s_i=a_i+b_i+t_i$ and determine $(c_i,t_{i+1})$ by
$$ \begin{array}{c|ccccc} s_i&-1&0&1&2&3\ \hline c_i&1&0&1&0&1\ t_{i+1}&1&0&0&-1&-1 \end{array} $$
because in each case $s_i=c_i-2t_{i+1}$. Start with $t_0=0$. After the digit $n$ has been processed, continue the same rule for the remaining carry values $t_{n+1}$ and $t_{n+2}$; since $t_i\in{-1,0,1}$, at most two additional digits are required. The resulting digits
$$ (c_{n+2}\ldots c_1c_0)_{-2} $$
satisfy
$$ \sum_{i=0}^{n+2}c_i(-2)^i = \sum_{i=0}^{n}a_i(-2)^i + \sum_{i=0}^{n}b_i(-2)^i, $$
hence they give the desired sum in the $-2$ number system.
$$ \boxed{(a_n\ldots a_0){-2}+(b_n\ldots b_0){-2}=(c_{n+2}\ldots c_0)_{-2}} $$