📃 题目描述

题目链接：

• 剑指 Offer II 002. 二进制加法 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 67. 二进制求和 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

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

示例 1:

输入: a = "11", b = "10"
输出: "101"

示例 2:

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

🔔 解题思路

有不少人看到这个题目的第一反应是将二进制字符串转换成int型整数或long型整数，然后把两个整数相加得到和之后再将和转换成二进制字符串。例如，将二进制字符串"11"转换成3，"10"转换成2，两个整数的和为5，将之转换成二进制字符串就得到"101"。这种解法可能会导致溢出。这个题目没有限制二进制字符串的长度。当二进制字符串比较长时，它表示的整数可能会超出int型整数或long型整数的范围，此时不能直接将其转换成整数。

因此，加法操作只能针对两个字符串进行。可以参照十进制加法来完成二进制加法。在进行十进制加法时，总是将两个数字的右端对齐，然后从它们的个位开始从右向左相加同一位置的两个数位，如果前一位有进位还要加上进位。

二进制加法也可以采用类似的方法，从字符串的右端出发向左做加法。与十进制不同的是，二进制是逢二进一，当两个数位加起来等于2时就会产生进位。可以用如下所示的参考代码实现二进制加法：

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        
        // 进位，逢二进一
        int carry = 0;
        
        while (i >= 0 || j >= 0) {
            int digitA = i >= 0 ? a.charAt(i) - '0' : 0;
            int digitB = j >= 0 ? b.charAt(j) - '0' : 0;

            int sum = digitA + digitB + carry;
            if (sum >= 2) {
                sum -= 2;
                carry = 1;
            }
            else {
                // 进位归 0
                carry = 0;
            }

            sb.append(sum);

            i --;
            j --;
        }
        
        // 处理最后一个进位
        if (carry == 1) {
            sb.append(carry);
        }
        
        return sb.reverse().toString();
    }
}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：O(N)