Addition in base -1+i Gaussian integers are complex numbers of the form a+bi where a and b are both integers. In base -1+i, all Gaussian integers can be uniquely represented using the digits 0 and 1, without the need for a symbol to denote sign.

For instance, 1100 in base -1+i represents the decimal number 2, since

1*(-1+i)^3 + 1*(-1+i)^2 + 0*(-1+i)^1 + 0*(-1+i)^0
= (2+2i) + (-2i) + 0 + 0
= 2


Input will be two Gaussian integers in base -1+i  represented using the digits 01. This can take one of the following forms:


Two separate digit strings,
Two decimal integers consisting of 01 representing the base -1+i numbers (e.g. 1100 for 2 in base -1+i),
Two binary integers representing the base -1+i numbers (e.g. decimal 12 or 0b1100 for 2 in base -1+i)
A single string separating two digit strings/binary integers by a single non-alphanumeric separator (e.g. 1100 1100 or 12,12 for 2+2)


Output the sum of the two Gaussian integers, also in base -1+i and represented using the digits 01 (in one of the formats allowed as input, not necessarily the same choice). The output is allowed to contain a finite number of leading zeroes.

Your function or program must terminate within 2 seconds for inputs of at most 30 digits each.

Additional clarifications


You may assume that the input contains no extraneous leading zeroes. For the special case of 0, you may choose either 0 or the empty string as the representation.


Test cases

0, 0 =&gt; 0                                      # 0 + 0 = 0
0, 1 =&gt; 1                                      # 0 + 1 = 1
1, 1 =&gt; 1100                                   # 1 + 1 = 2
1100, 1100 =&gt; 111010000                        # 2 + 2 = 4
1101, 1101 =&gt; 111011100                        # 3 + 3 = 6
110111001100, 1110011011100 =&gt; 0               # 42 + (-42) = 0
11, 111 =&gt; 0                                   # i + (-i) = 0
11, 110 =&gt; 11101                               # i + (-1-i) = -1
10101, 11011 =&gt; 10010                          # (-3-2i) + (-2+3i) = (-5+i)
1010100101, 111101 =&gt; 1110100000100            # (-19+2i) + (3-4i) = (-16-2i)


Longer test cases:

11011011010110101110010001001, 111100010100101001001010010101 =&gt; 0
111111111111111111111111111111, 111111111111111111111111111111 =&gt; 100100100100100100100100100100
101101110111011101110111011101, 101101110111011101110111011101 =&gt; 11101001010001000100010001000100011100
100100010101001101010110101010, 100010011101001011111110101000 =&gt; 110000110010101100001100111100010
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.