Adding two numbers in base -2

Base -2 numbers have unique representation like other bases.

The rules: (digit 1, digit 2, carry) => digit, carry next digit, carry follow digit

(0,0,0) => (0,0,0)
(1,0,0) == (0,1,0) => (1,0,0)
(1,1,0) => (0,1,1)
(1,1,1) => (1,1,1)

The idea is that for each 2 ones in position i we can get them by having 1 from next and 1 from next->next

Attached proof for the 3rd case

Note: The value of the carry for each digit can be > 1.

for each i:
   n=num1[i]+num2[i]+carry[i]
   res[i]=n%2
   carry[i+1]+=n/2
   carry[i+2]+=n/2

Note: n/2 is integer floor division (floor(n/2.0))

Sample problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2062