# Question

Formatted question description: https://leetcode.ca/all/67.html

67	Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".



# Algorithm

When adding each bit, there may be a carry, which will affect the result of the subsequent addition. And the length of the two input strings may also be different. At this time, we need to create a new string, whose length is the larger of the two input strings, and add the character ‘0’ to the beginning of the shorter input string to fill the larger length. At this time, the characters are taken out from the end of the two strings one by one, and then converted into numbers, and added. If it is greater than or equal to 2, mark the carry flag carry, and add a character ‘0’ to the new string.

# Code

Java

• import java.math.BigInteger;

public class Solution {
public String addBinary(String a, String b) {

if (a == null || b == null || a.length() == 0 || b.length() == 0) {
return "";
}

// swap to a is longer than b
if (a.length() < b.length()) {
}

String result = "";
int carry = 0;

int i = a.length() - 1; // pointer of string a
int j = b.length() - 1; // pointer of string b

while (j >= 0 || i >= 0) {
add = (a.charAt(i) - '0') + (j < 0? 0 : (b.charAt(j) - '0')) + carry;

} else {
carry = 0;
}

i--;
j--;
}

// final check
if (carry > 0) {
result = carry + result;
}

return result;
}
}

public class Solution_BigInteger { // actually, still possible overflow, just passed OJ test cases
public String addBinary(String a, String b) {
if (a == null || b == null)
return "";
if (a.length() == 0)
return b;
if (b.length() == 0)
return a;

// easily overflow
// int a = Integer.parseInt(a);

BigInteger aa = new BigInteger(a, 2);
BigInteger bb = new BigInteger(b, 2);

}
}

}

• // OJ: https://leetcode.com/problems/add-binary/
// Time: O(A+B)
// Space: O(1)
class Solution {
public:
string addBinary(string a, string b) {
int i = a.size() - 1, j = b.size() - 1, carry = 0;
string ans;
while (i >= 0 || j >= 0 || carry) {
if (i >= 0) carry += a[i--] - '0';
if (j >= 0) carry += b[j--] - '0';
ans += '0' + (carry & 1);
carry >>= 1;
}
return string(rbegin(ans), rend(ans));
}
};

• class Solution(object):
"""
:type a: str
:type b: str
:rtype: str
"""
diff = abs(len(a) - len(b))
if len(a) > len(b):
b = "0" * diff + b
else:
a = "0" * diff + a

ret = ""
carry = 0
ai, bi = len(a) - 1, len(b) - 1
al, bl = len(a), len(b)
while ai >= 0 and bi >= 0:
ac, bc = a[ai], b[bi]
if ac == "1" and bc == "1":
if carry == 1:
ret += "1"
else:
ret += "0"
carry = 1
elif ac == "0" and bc == "0":
if carry == 1:
ret += "1"
else:
ret += "0"
carry = 0
else:
if carry == 1:
ret += "0"
else:
ret += "1"

ai -= 1
bi -= 1

if carry == 1:
ret += "1"
return ret[::-1]