[Question]
  [
[Gaussian integers](https://en.wikipedia.org/wiki/Gaussian_integer) 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 => 0                                      # 0 + 0 = 0
0, 1 => 1                                      # 0 + 1 = 1
1, 1 => 1100                                   # 1 + 1 = 2
1100, 1100 => 111010000                        # 2 + 2 = 4
1101, 1101 => 111011100                        # 3 + 3 = 6
110111001100, 1110011011100 => 0               # 42 + (-42) = 0
11, 111 => 0                                   # i + (-i) = 0
11, 110 => 11101                               # i + (-1-i) = -1
10101, 11011 => 10010                          # (-3-2i) + (-2+3i) = (-5+i)
1010100101, 111101 => 1110100000100            # (-19+2i) + (3-4i) = (-16-2i)
```
Longer test cases:
```
11011011010110101110010001001, 111100010100101001001010010101 => 0
111111111111111111111111111111, 111111111111111111111111111111 => 100100100100100100100100100100
101101110111011101110111011101, 101101110111011101110111011101 => 11101001010001000100010001000100011100
100100010101001101010110101010, 100010011101001011111110101000 => 110000110010101100001100111100010
```
  
[Answer]
# 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](http://ideone.com/bDgD34).
### How it works
In [Arithmetic in Complex Bases](https://www.math.uwaterloo.ca/~wgilbert/Research/ArithCxBases.pdf), 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.
1. First, we add **a** and **b** as if their digits were decimal digits.
For **a = 10101** and **b = 11011**, this gives **21112**.
2. 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**.
3. 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**.
4. 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
                             .
                             .
                             .
```
5. 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.
[Answer]
# Pyth, 34 bytes
```
_shM.u,%J/eMeN\12-+PMeNm.B6/J2k,kQ
```
Try it online: [Demonstration](http://pyth.herokuapp.com/?code=_shM.u%2C%25J%2FeMeN%5C12-%2BPMeNm.B6%2FJ2k%2CkQ&input=%22100100010101001101010110101010%22%2C+%22100010011101001011111110101000%22&test_suite_input=%220%22%2C+%220%22%0A%220%22%2C+%221%22%0A%221%22%2C+%221%22%0A%221100%22%2C+%221100%22%0A%221101%22%2C+%221101%22%0A%22110111001100%22%2C+%221110011011100%22%0A%2211%22%2C+%22111%22%0A%2211%22%2C+%22110%22%0A%2210101%22%2C+%2211011%22%0A%221010100101%22%2C+%22111101%22%0A%2211011011010110101110010001001%22%2C+%22111100010100101001001010010101%22%0A%22111111111111111111111111111111%22%2C+%22111111111111111111111111111111%22%0A%22101101110111011101110111011101%22%2C+%22101101110111011101110111011101%22%0A%22100100010101001101010110101010%22%2C+%22100010011101001011111110101000%22&debug=0) or [Test Suite](http://pyth.herokuapp.com/?code=_shM.u%2C%25J%2FeMeN%5C12-%2BPMeNm.B6%2FJ2k%2CkQ&input=%22100100010101001101010110101010%22%2C%20%22100010011101001011111110101000%22&test_suite=1&test_suite_input=%220%22%2C%20%220%22%0A%220%22%2C%20%221%22%0A%221%22%2C%20%221%22%0A%221100%22%2C%20%221100%22%0A%221101%22%2C%20%221101%22%0A%22110111001100%22%2C%20%221110011011100%22%0A%2211%22%2C%20%22111%22%0A%2211%22%2C%20%22110%22%0A%2210101%22%2C%20%2211011%22%0A%221010100101%22%2C%20%22111101%22%0A%2211011011010110101110010001001%22%2C%20%22111100010100101001001010010101%22%0A%22111111111111111111111111111111%22%2C%20%22111111111111111111111111111111%22%0A%22101101110111011101110111011101%22%2C%20%22101101110111011101110111011101%22%0A%22100100010101001101010110101010%22%2C%20%22100010011101001011111110101000%22&debug=0) (takes quite a while). It should satisfy the time restriction though easily, since the online compiler is quite slow in comparison with the normal (offline) compiler. 
### Explanation:
My algorithm is basically an implementation of addition with carrying. But instead of carrying `1`, I have to carry `110` (`1100` in base `-1+i` is the same as `2` in base `-1+i`). This works mostly fine, but you can get stuck in an infinite loop printing zeros. For instance if you are adding `1` with `11` and currently have the carry `110`. So I basically add until I get stuck in a loop and then stop. I think that a loop that a loop will always print zeros and therefore this should be fine. 
```
_shM.u,%J/eMeN\12-+PMeNm.B6/J2k,kQ   implicit: Q = input list of strings
                               ,kQ   create the pair ["", Q]
    .u                               modify the pair N (^) until loop:
      ,                                replace N with a new pair containing:
            eN                           N[1] (the remaining summand)
          eM                             take the last digits of each summand
         /    \1                         count the ones
        J                                store the count in J
       %J       2                        J % 2 (this is the first element of the new pair)
                   PMeN                  remove the last digit of each summand
                  +    m   /J2           and add J / 2 new summand:
                        .B6                 with the value "110" (binary of 6)
                 -            k          remove empty summand
    .u                               returns all intermediate results
  hM                                 extract the digits
 s                                   sum them up to a long string
_                                    reverse
```
[Answer]
# Python 2, ~~69~~ 67 bytes
```
f=lambda a,b:a*a+b*b^58and 2*f(a*b%2*6,f(a/2,b/2))|a+b&1if a else b
```
I/O is done with base 2 integers.
-2 thanks @Dennis.
[Answer]
# Jelly, ~~29~~ ~~28~~ ~~26~~ ~~24~~ ~~21~~ 20 bytes
```
DBḅ1100ḌµDL+8µ¡Dṣ2ṪḌ
```
This does I/O in decimal. The integers have to be separated by the non-alphanumeric character `+`.
[Try it online!](http://jelly.tryitonline.net/#code=RELhuIUxMTAw4biMwrVETCs4wrXCoUThuaMy4bmq4biM&input=&args=MTEwMTEwMTEwMTAxMTAxMDExMTAwMTAwMDEwMDErMTExMTAwMDEwMTAwMTAxMDAxMDAxMDEwMDEwMTAx) or [verify all test cases](http://jelly.tryitonline.net/#code=RELhuIUxMTAw4biMwrVETCs4wrXCoUThuaMy4bmq4biMCsOH4oKs&input=&args=MCswLCAwKzEsIDErMSwgMTEwMCsxMTAwLCAxMTAxKzExMDEsIDExMDExMTAwMTEwMCsxMTEwMDExMDExMTAwLCAxMSsxMTEsIDExKzExMCwgMTAxMDErMTEwMTEsIDEwMTAxMDAxMDErMTExMTAxLCAxMTAxMTAxMTAxMDExMDEwMTExMDAxMDAwMTAwMSsxMTExMDAwMTAxMDAxMDEwMDEwMDEwMTAwMTAxMDEsIDExMTExMTExMTExMTExMTExMTExMTExMTExMTExMSsxMTExMTExMTExMTExMTExMTExMTExMTExMTExMTEsIDEwMTEwMTExMDExMTAxMTEwMTExMDExMTAxMTEwMSsxMDExMDExMTAxMTEwMTExMDExMTAxMTEwMTExMDEsIDEwMDEwMDAxMDEwMTAwMTEwMTAxMDExMDEwMTAxMCsxMDAwMTAwMTExMDEwMDEwMTExMTExMTAxMDEwMDA).
### Background
In [Arithmetic in Complex Bases](https://www.math.uwaterloo.ca/~wgilbert/Research/ArithCxBases.pdf), 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.
1. First, we add **a** and **b** as if their digits were decimal digits.
For **a = 10101** and **b = 11011**, this gives **21112**.
2. For each digit larger than **1**, we have to subtract **2** from that digit and carry **110** to the next three higher positions. We can achieve this by converting each decimal digit to binary, the resulting binary arrays from base **1100** to integer, and interpret the resulting list of **0**'s, **1**'s, **1100**'s and **1101**'s as a non-canonical base **10** number.1
For the sum **21112**, this gives **21112 + 1098 \* 10001 = 21112 + 10981098 = 11002210**.
3. We repeat steps **2** a total of **d + 8** times, where **d** is the number of digits of **a + b**.
For the initial sum **21112**, the results are
```
                      11002210
                      12210010
                    1220010010
                  122000010010
                12200000010010
              1220000000010010
            122000000000010010
          12200000000000010010
        1220000000000000010010
      122000000000000000010010
    12200000000000000000010010
  1220000000000000000000010010
122000000000000000000000010010
```
4. We discard all but the last **d + 8** digits from the final result. This is achieved by discarding everything after the last **2**.2
For the initial sum **21112**, the final result is **10010**.
### How it works
```
DBḅ1100ḌµDL+8µ¡Dṣ2ṪḌ  Main link. Argument: a + b (implicit sum)
        µ    µ¡       Execute the chain before the first µ n times, where n is
                      the result of executing the chain before the second µ.
         D            Convert a + b to base 10.
          L           Length; count the decimal digits.
           +8         Add 8 to the number of digits.
D                     Convert the initial/previous sum to base 10.
 B                    Convert each digit (0 - 3) to binary.
  ḅ1100               Convert each binary array from base 1100 to integer.
       Ḍ              Interpret the resulting list as a base 10 number.
               D      Convert the final sum to base 10.
                ṣ2    Split at occurrences of 2.
                  Ṫ   Select the last chunk.
                   Ḍ  Convert from base 10 to integer.
```
---
1 Note that the digits of this sum cannot exceed **3** (initial value **1** plus two **1**'s from carries).
2 This works because the last digit that will cancel out cannot be a **3**.
[Answer]
## [Retina](https://github.com/mbuettner/retina), 100 bytes
```
r+`(.*)(\d|(?!\4))( .*)(.?)
$2$4:$1$3
T` 0
+`1:11(1*:1*)11
:$1
^:*
:::
}`:(1*:1*:)11
1:1$1
(1)*:
$#1
```
This takes the input separated with a comma. The output always starts with three leading zeroes.
[Try it online!](http://retina.tryitonline.net/#code=citgKC4qKShcZHwoPyFcNCkpKCAuKikoLj8pCiQyJDQ6JDEkMwpUYCAwCitgMToxMSgxKjoxKikxMQo6JDEKXjoqCjo6Ogp9YDooMSo6MSo6KTExCjE6MSQxCigxKSo6CiQjMQ&input=MTAwMTAwMDEwMTAxMDAxMTAxMDEwMTEwMTAxMDEwIDEwMDAxMDAxMTEwMTAwMTAxMTExMTExMDEwMTAwMA)
I really wonder if there's a shorter solution for the first stage...
[Answer]
## Python 3, 289 bytes
This performs digitwise addition from least to most significant digit (in other words, the exact same algorithm you were taught in primary school). The differences are that (a) it's in binary, not decimal, so you carry whenever a digit is 2 or more, and (b) `1 + 1 = 1100`, not `10`.
Actually, it's also necessary to note that `11 + 111 = 0`, or else sums that should become zero will never terminate.
```
from collections import*
def a(*s,p=0):
 r=defaultdict(int,{0:0})
 for S in s:
  n=0
  for d in S[::-1]:r[n]+=d=='1';n+=1
 while p<=max(r):
  while r[p]>1:
   r[p]-=2
   if r[p+1]>1<=r[p+2]:r[p+1]-=2;r[p+2]-=1
   else:r[p+2]+=1;r[p+3]+=1
  p+=1
 return str([*map(r.get,sorted(r))])[-2::-3]
```
More golfing is surely possible.
[Answer]
## JavaScript (ES6), ~~146~~ 126 bytes
```
r=n=>n&&n%2-r(n>>=1)-i(n)
i=n=>n&&r(n>>=1)-i(n)
g=(x,y,b=(x^y)&1)=>x|y&&b+2*g(b-x+y>>1,b-x-y>>1)
(x,y)=>g(r(x)+r(y),i(x)+i(y))
```
`g` converts a Gaussian integer (real and imaginary parts) into base `i-1`, while `r` and `i` converts a base `i-1` integer into a Gaussian integer (real and imaginary parts respectively). Once the conversions are in place, I just have to do the arithmetic.
Edit: Saved 20 bytes by calculating the real and imaginary parts separately.
[Answer]
C++ 416 bytes, plus `#include <vector>\n#include <algorithm>\n` (another 40)
```
using I=int;using v=std::vector<I>;void r(v&x){v r{rbegin(x),rend(x)};x=r;}v a(v L,v R){r(L);r(R);L.resize(std::max(L.size(),R.size()));for(int&r:R)L[&r-R.data()]+=r;while(1){L.resize(L.size()+3);auto it=find(rbegin(L),rend(L),2);if(it==rend(L))break;I i=-1+it.base()-begin(L);i&&L[i+1]&&L[i-1]/2?L[i+1]=L[i]=L[i-1]=0:(++L[i+2],++L[i+3],L[i]=0);}L.erase( std::find(rbegin(L),rend(L),1).base(),end(L));r(L);return L;}
```
or, with more whitespace:
```
using I=int;
using v=std::vector<I>;
void r(v&x){v r{rbegin(x),rend(x)};x=r;}
v a(v L,v R) {
  r(L);r(R);
  L.resize(std::max(L.size(),R.size()));
  for(int&r:R)
    L[&r-R.data()]+=r;
  while(1) {
    L.resize(L.size()+3);
    auto it=find(rbegin(L), rend(L), 2);
    if(it==rend(L)) break;
    I i=-1+it.base()-begin(L);
    i&&L[i+1]&&L[i-1]/2?
      L[i+1]=L[i]=L[i-1]=0
    :
      (++L[i+2],++L[i+3],L[i]=0);
  }
  L.erase( std::find(rbegin(L),rend(L),1).base(), end(L));
  r(L);
  return L;
}
```
Barely golfed. It takes input as a vector of ints, and returns a vector of ints.
[Live example](http://coliru.stacked-crooked.com/a/f18051950b814357).
[Answer]
# Retina, ~~157~~ ~~151~~ ~~134~~ ~~133~~ ~~124~~ 123 bytes
*1 byte off thanks to Martin Büttner.*
```
(.+),(.+)
$.1$*0$2,$.2$*0$1,
1
0x
+`(0x*)(,.*)0(x*),
$2,$1$3
{`,
(^|0x0xx0xx)
000
(0x*)(0x*)(0x*0)xx
$1x$2x$3
)`^0+
0
0x
1
```
[Try it online!](http://retina.tryitonline.net/#code=KC4rKSwoLispCiQuMSQqMCQyLCQuMiQqMCQxLAoxCjB4CitgKDB4KikoLC4qKTAoeCopLAokMiwkMSQzCntgLAoKKF58MHgweHgweHgpCjAwMAooMHgqKSgweCopKDB4KjApeHgKJDF4JDJ4JDMKKWBeMCsKMAoweAox&input=MTAwMTAwMDEwMTAxMDAxMTAxMDEwMTEwMTAxMDEwLDEwMDAxMDAxMTEwMTAwMTAxMTExMTExMDEwMTAwMA)
Converts to unary, and then repeat the following replacements (shown here in decimal):
```
122 -> 000
0002 -> 1100 (this can also be 0012 -> 1110 and 1112 -> 2210 or even 2222 -> 3320 or even 3333 -> 4431)
```
Basically, when larger than two: take away two, add nothing in the previous digit, add one to the previous digit, then add one to the previous digit.
In pseudocode:
```
if(a[n]>2):
    a[n] -= 2;
    a[n-2] += 1;
    a[n-3] += 1;
```
### Unary implementation:
Each digit (e.g. `3`) is shown as the number of `x`s (e.g. `xxx`) and then prefixed with `0`.
For example, `1234` would be expressed as `0x0xx0xxx0xxxx`.
This leaves `0` unchanged, as `101` would be expressed by `0x00x`.
Since initially and finally, there is only `0` and `1`, the conversion could be easily done by `1->0x` and `0x->1`.
[Click here to see every step](http://retina.tryitonline.net/#code=OmAoLispLCguKykKJC4xJCowJDIsJC4yJCowJDEsCjpgMQoweAorOmAoMHgqKSgsLiopMCh4KiksCiQyLCQxJDMKKyg6YCwKCjpgKF58MHgweHgweHgpCjAwMAo6YCgweCopKDB4KikoMHgqMCl4eAokMXgkMngkMwo6KWBeMCsKMAo6YDB4CjE&input=MTAwMTAwMDEwMTAxMDAxMTAxMDEwMTEwMTAxMDEwLDEwMDAxMDAxMTEwMTAwMTAxMTExMTExMDEwMTAwMA).
]