Add Binary

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

The input strings are both non-empty and contains only characters1or 0.

Example 1:

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

Output:
 "100"

Example 2:

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

Output:
 "10101"

Analysis

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

在计算过程不可以将a，b都转化为数（Integer/Long）来求和，因为测试样例和题中并没有限制数据的长度大小，因此会溢出导致错误。

返回String字符串，动态字符串可以用StringBuilder（或者StringBuffer，如果用多线程，因为StringBuffer是sync），减小字符串拼接时间复杂度 （O(n^2) - > O(n)）

从低位到高位的顺序进行相加求和，因此得到的StringBuilder是逆序，需要翻转后输出。

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();
    }
}

错误方法会在数据较大时溢出从而导致错误：

Wrong Answer：

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;
            strList.add(Long.toString(tmp));
            num = num / 2;
        }

        Collections.reverse(strList);
        String str = String.join("", strList);
        return str;
    }
}