class Solution
{
public:
string addBinary(string a, string b)
{
string s = "";
int c = 0, i = a.size()  1, j = b.size()  1;
while(i >= 0  j >= 0  c == 1)
{
c += i >= 0 ? a[i ]  '0' : 0;
c += j >= 0 ? b[j ]  '0' : 0;
s = char(c % 2 + '0') + s;
c /= 2;
}
return s;
}
};
Short code by c++

My solution ,another easy to understand style
string addBinary(string a, string b) { int length1 = a.size(), length2 = b.size(); if(0 == length1) return b; if(0 == length2) return a; int iIndex1 = length1  1, iIndex2 = length2  1; int ic = 0, ia, ib, sum; string output; while(iIndex1 != 1  iIndex2 != 1) { if(1 == iIndex1) ia = 0; else ia = a[iIndex1]  '0'; if(1 == iIndex2) ib = 0; else ib = b[iIndex2]  '0'; sum = ia + ib + ic; if(sum >= 2) ic = 1; else ic = 0; output.insert(0, sum % 2 == 1 ? "1" : "0"); if(iIndex1 >= 0) iIndex1; if(iIndex2 >= 0) iIndex2; } if(ic) output.insert(0, "1"); return output; }

string addBinary(string a, string b) { int carry = 0; int len = a.size() > b.size() ? a.size() : b.size(); string res; for (int i = 0; i < len; i++) { int na = i < a.size() ? (a[a.size()  1  i]  '0') : 0; int nb = i < b.size() ? (b[b.size()  1  i]  '0') : 0; int sum = na + nb + carry; res = to_string(sum % 2) + res; carry = sum / 2; } if (carry) res = '1' + res; return res;
}

What's the complexity of this solution, it seems to cost n^2 time, for every loop it will replicate the total string rather than append to it directly.
Thus, why not reverse it first and reverse the result at last, it will cost O(n) time actually. If I made a mistake, please pointed out to me.

string addBinary(string a, string b) { if (a.size() < b.size()) { a = string(b.size()  a.size(), '0') + a; } else { b = string(a.size()  b.size(), '0') + b; } bool c = 0, tmp = 0; for (int i = (int)a.size()  1; i >= 0; i) { tmp = ((a[i] & 1) + (b[i] & 1) + c) > 1; b[i] ^= ((a[i] ^ c) & 1); c = tmp; } return c ? "1" + b : b; }
'0' = 48 = 0110000
'1' = 49 = 0110001


The complexity is O(n^2),
with following test case, it took 149ms, while O(n) alg only need 6ms.
"1" "1111....1111" # total 70000 "1"s
with following test case, it gave back "memory limit exceed" error, while O(n) alg still work fine.
"1" "1111....1111" # total 100000 "1"s
It's better to avoid pattern
string = char + string
in loop. Use s[i] to alter string.btw, it seems nobody care about the binary strings starting with multiple zeros,
Your input "0001" "0000001" Your answer "0000010" Expected answer "10"

My accepted answer using bitwise operators
public String addBinary(String a, String b) { int i = a.length()  1; int j = b.length()  1; int c = 0; String str = ""; while (i >= 0  j >= 0  c == 1) { c += i >= 0 ? a.charAt(i)  '0': 0; c += j >= 0 ? b.charAt(j)  '0': 0; str = (c & 1) + str; c = c >> 1; } return str; }