二进制求和 图解题解

这道题到底在问什么

a

"1010"

b

"1011"

输出

"10101"

先想最直接的笨办法

笨办法是把二进制转成十进制相加再转回去——但数一长就溢出。更稳的办法是直接模仿手算竖式,永远不溢出。（动画第 3 步）

最优解：一步一步想明白

1. 3笨办法是把二进制转成十进制相加再转回去——但数一长就溢出。更稳的办法是直接模仿手算竖式,永远不溢出。
2. 4盯死两条规则:本位 = 和 % 2、进位 = 和 ÷ 2。和最大是 1+1+1=3,所以本位最多写 1、进位最多 1,绝不会乱。
3. 5a=1010 b=1011 结果留 5 格下面 5 个空格是给结果留的位置(两数最长 4 位,加法最多多进 1 位 → 留 5 格)。我们从最右一列往左逐列填。
4. 6a=1010 摆进低 4 格先把 a = 1010 靠右摆进格子看清对齐(灰色只是示意,不是最终结果)。注意末位 0 落在最右那一列。
5. 7b=1011 同样靠右b = 1011 也靠右摆,它的末位 1 和 a 的末位 0 正好同列。两数末尾对齐了,就能像竖式那样逐列加。现在清空,正式开算。
6. 8a位=0 b位=1 carry=0最右列:a 的末位是 0、b 的末位是 1、进位 0。和 = 1。本位写 1,没有进位。
7. 9最右位 = 1把 1 填进最右格(变绿表示已确定),进位还是 0。指针准备左移到下一列。
8. 10a位=1 b位=1 carry=0往左挪一列:a 这位是 1、b 这位是 1,进位 0。和 = 2 —— 逢二进一!本位写 0,进位 1 留给下一列。
9. 11本位 0 · 进位 1填入 0。注意 carry 变成 1 了——这个 1 必须带到下一列一起加,千万别丢。
10. 12a位=0 b位=0 carry=1这一列 a、b 都是 0,但别忘了上一列带来的进位 1!和 = 0+0+1 = 1。本位写 1,进位清 0。
11. 13本位 1 · 进位 0填入 1,进位归 0。结果已经攒到 101(从右往左读)。继续左移。
12. 14a位=1 b位=1 carry=0到两数的最高位:a 是 1、b 是 1。和 = 2,又逢二进一!本位写 0,进位 1。
13. 15本位 0 · 进位 1 还没完填入 0。两个数都加完了,但 carry 还剩 1!这就是为什么结果要多留一格——进位还得再写出来。
14. 16a、b 都没了 carry=1a、b 都没位了,只剩 进位 1。和 = 1,本位写 1。这一步常被忘掉——循环条件必须带上「carry 不为 0 也要继续」。
15. 1710101 ✓最高位填 1,5 格全确定。整行从左往右读就是答案 10101——十进制验证 10 + 11 = 21,完全对上。
16. 18结果留 3 格换个数 11 + 1 再走一遍,这次专盯雷区说的进位连锁——一个进位怎么一路顶到最高位。两数最长 2 位,留 3 格。
17. 19a位=1 b位=1 carry=0最右列:a 末位 1、b 末位 1。和 = 2,逢二进一,本位写 0,进位 1。
18. 20本位 0 · 进位 1填入 0,进位 1 带往下一列。
19. 21a位=1 b没了 carry=1b 已经没位了(当 0 算),a 这位 1 加进位 1 = 2,又逢二进一!本位 0,进位还是 1——连锁了。
20. 22本位 0 · 进位 1 还在填 0。两个数都加完了,但 carry 仍是 1,循环靠 carry 条件继续。
21. 23只剩 carry=1最高位把进位 1 写出来,结果 100(= 十进制 4 = 3 + 1)。看清了吗——一个进位从最右一路顶到了最左,这就是连锁。
22. 24这就是「大数加法」的通用套路。把它从二进制换成十进制(逢十进一)、换成任意进制都成立——核心永远是对齐末位、逐列带进位。
23. 28a=1 b=1 → 错写成 0算 1 + 1:本位写 0、进位 1,可如果循环条件不带 carry,这里就直接结束,结果只剩 0。正确答案是 10——那个进位的 1 必须再补一列。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def addBinary(self, a, b):
        i, j = len(a) - 1, len(b) - 1   # 两个末尾下标
        carry = 0
        res = []
        while i >= 0 or j >= 0 or carry:  # 进位没清也要继续
            s = carry
            if i >= 0: s += int(a[i]); i -= 1
            if j >= 0: s += int(b[j]); j -= 1
            res.append(str(s % 2))      # 本位
            carry = s // 2              # 进位
        return "".join(reversed(res))   # 倒序拼回

class Solution {
public:
    string addBinary(string a, string b) {
        int i = a.size() - 1, j = b.size() - 1;
        int carry = 0;
        string res;
        while (i >= 0 || j >= 0 || carry) {
            int s = carry;
            if (i >= 0) s += a[i--] - '0';
            if (j >= 0) s += b[j--] - '0';
            res += char('0' + s % 2);   // 本位
            carry = s / 2;              // 进位
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1, j = b.length() - 1;
        int carry = 0;
        StringBuilder res = new StringBuilder();
        while (i >= 0 || j >= 0 || carry > 0) {
            int s = carry;
            if (i >= 0) s += a.charAt(i--) - '0';
            if (j >= 0) s += b.charAt(j--) - '0';
            res.append((char) ('0' + s % 2)); // 本位
            carry = s / 2;                    // 进位
        }
        return res.reverse().toString();
    }
}

复杂度

面试官可能追问