Problem

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

Example

a = 11

b = 1

Return 100

Note

进位思想和https://segmentfault.com/a/1190000004543349相同。
从字符串a，b的最后一位（i，j）开始，a，b，carry累加进位，和存入sb，进位存入carry。a，b中位数较少者在越界情况下（i，j某一个小于0）取0继续计算。循环结束后，若最后一次结果中carry等于1，就在sb的最左边（最高位）插入1，然后将sb转换为String返回。

Solution

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 m = i >= 0 ? a.charAt(i) - '0' : 0;
            int n = j >= 0 ? b.charAt(j) - '0' : 0;
            int cur = m + n + carry;
            sb.insert(0, String.valueOf(cur % 2));
            carry = cur / 2;
            i--;
            j--;
        }
        if (carry == 1) sb.insert(0, '1');
        return sb.toString();
    }
}