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

The input strings are both non-empty and contains only characters`1`or `0`.

Example 1:

``````Input:
a = "11", b = "1"

Output:
"100"
``````

Example 2:

``````Input:
a = "1010", b = "1011"

Output:
"10101"
``````

## Analysis

Easy难度，但是有一些需要注意的点：

## Solution

Preferred Implementation - Binary Conversion

Computation from string usually can be simplified by using a carry as such.

``````public class Solution {
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
int i = a.length() - 1, j = b.length() -1, carry = 0;
while (i >= 0 || j >= 0) {
int sum = carry;
if (j >= 0) sum += b.charAt(j--) - '0';
if (i >= 0) sum += a.charAt(i--) - '0';
sb.append(sum % 2);
carry = sum / 2;
}
if (carry != 0) sb.append(carry);
return sb.reverse().toString();
}
}
``````

Using Bit operation XOR

``````public class Solution {
public String addBinary(String a, String b) {
if(a == null || a.isEmpty())
return b;
if(b == null || b.isEmpty())
return a;

StringBuilder stb = new StringBuilder();
int i = a.length() - 1;
int j = b.length() - 1;
int aBit;
int bBit;
int carry = 0;
int result;

while(i >= 0 || j >= 0 || carry == 1) {
aBit = (i >= 0) ? Character.getNumericValue(a.charAt(i--)) : 0;
bBit = (j >= 0) ? Character.getNumericValue(b.charAt(j--)) : 0;
result = aBit ^ bBit ^ carry;
carry = ((aBit + bBit + carry) >= 2) ? 1 : 0;
stb.append(result);
}
return stb.reverse().toString();
}
}
``````

207 / 294 test cases passed.

``````Input:
"10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101"
"110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"
Output:
"11101000101011001000011011000001100011110011010010011000000000"
Expected:
"110111101100010011000101110110100000011101000101011001000011011000001100011110011010010011000000000"
``````

Wrong Way：

``````class Solution {
public String addBinary(String a, String b) {
char[] chA = a.toCharArray();
char[] chB = b.toCharArray();
long longA = 0;
long longB = 0;
long numA = convertToLong(chA);
long numB = convertToLong(chB);
long sum = numA + numB;
String s = convertToBinaryString(sum);
return s;
}
private long convertToLong(char[] chs) {
long num = 0;
for (char ch : chs) {
num = num << 1;
num = num + ch - '0';
}
return num;
}

private String convertToBinaryString(long num) {
if (num == 0) {
return "0";
}
List<String> strList = new ArrayList<String>();
while (num > 0) {
long tmp = num % 2;