Addition in base -1+i
Python 2, 98 97 91 84 bytes

s=input();L=1
for _ in`s`*8:s+=1098*int(str(s).translate('0011'*64));L*=10
print s%L


This does I/O in decimal. The integers have to be separated by the non-alphanumeric character +.

Thanks to @xnor for golfing off 2 bytes!

Try it on Ideone.

How it works

In Arithmetic in Complex Bases, the author shows how to add and multiply complex numbers in bases of the form -n + i.

For base -1 + i, addition is done similarly to regular, binary addition with carry, with two differences:


Instead of carrying 1 to the next higher position, we carry 110 to the next three.
Carry digits can propagate indefinitely. However, without leading zeroes, the sum a + b has at most eight digits more than the maximum of a and b.


We proceed as follows.


First, we add a and b as if their digits were decimal digits.

For a = 10101 and b = 11011, this gives 21112.
Next, we form a new number by replacing the digits larger than 1 with a 1, others with a 0.1

For the sum 21112, this gives 10001.
For each digit larger than 1, we have to subtract 2 from that digit and carry 110 to the next three higher positions. Since 1098 = 10 * 110 - 2, we can achieve this by multiplying the result from step 2 by 1098, then adding that product to the sum.2

For the sum 21112, this gives 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210.
We repeat steps 2 and 3 a total of d * 8 times, where d is the number of digits of a + b. 3

For the initial sum 21112, the results are

                      11002210
                      12210010
                    1220010010
                  122000010010
                12200000010010
              1220000000010010
            122000000000010010
          12200000000000010010
        1220000000000000010010
      122000000000000000010010
    12200000000000000000010010
  1220000000000000000000010010
122000000000000000000000010010
                             .
                             .
                             .

We take the final sum modulo 10d + 8, discarding all but the last d + 8 digits.

For the initial sum 21112, the final result is 10010.




1 This is achieved with translate. Repeating the string 0011 64 times makes one repetition line up with the sequence of ASCII characters 0123, achieving the desired replacement.

2 Note that the digits of this sum cannot exceed 3 (initial value 1 plus two 1's from carries).

3 This happens to work for d = 1, and d * 8 > d + 8 otherwise. The code may repeat the steps (d + 1) * 8 times, since s has a trailing L if s is a long integer.