0034力扣67题---二进制求和

力扣67题---二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为非空字符串且只包含数字1和0。

示例1:    输入:a="11",b="1"  输出:"100"

示例2:   输入:a="1010",b="1011"  输出:"10101"

提示：

每个字符串仅由字符'0'或'1'组成。

1<=a.length,b.length<=10^4

字符串如果不是"0"，就都不含前导零。

考虑一个最朴素的方法：先将 aa 和 bb 转化成十进制数，求和后再转化为二进制数。
利用 Python 和 Java 自带的高精度运算，我们可以很简单地写出这个程序：(但是提交通不过)

    public String addBinary(String a, String b) {
        return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
    }

如果字符串超过 3333 位，不能转化为 Integer

如果字符串超过 6565 位，不能转化为 Long

如果字符串超过 500000001500000001 位，不能转化为 BigInteger

因此，为了适用于长度较大的字符串计算，我们应该使用更加健壮的算法。

大佬的代码：

    public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();
        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2;
        }
        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();
        return ans.toString();
    }