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

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

给出两个表示二进制的字符串，求相加后的结果，字符串形式返回。

考虑到二进制相加进位最大为1，相加结果最大是11，对2取余是当前位的值，除以2可以得到进位的值。用两个指针分别指向两个字符串末尾，依次计算每位的值以及是否产生进位。

public String addBinary(String a, String b) {
    if (a == null || b == null) {
        return a == null ? b : a;
    }

    StringBuilder buff = new StringBuilder();
    int alen = a.length(), blen = b.length();
    int extra = 0;
    for (int i = alen - 1, j = blen - 1; i >= 0 || j >= 0; i--, j--) {
        int now = 0;
        int cur = 0;
        if (i >= 0 && j >= 0) {
            now = a.charAt(i) - '0' + b.charAt(j) - '0' + extra;
        } else if (i >= 0) {
            now = a.charAt(i) - '0' + extra;
        } else {
            now = b.charAt(j) - '0' + extra;
        }

        cur = now % 2;
        extra = now / 2;
        buff.insert(0, cur);
    }

    if (extra > 0) {
        buff.insert(0, extra);
    }

    return buff.toString();
}

discuss中的答案和自己思路是一样的，但是在处理每一位相加的时候，只需要分别判断i和j是否越界。每次操作StringBuilder时也不需要每次指明insert到0位置，只需要最后reverse即可。进位的命名一般用carry。

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