LeetCode Add Binary：字符串二进制加法模拟

题目大意

给定两个二进制字符串，返回它们的和（二进制字符串）。

模拟竖式加法

1. 对齐长度：短串前补 0
2. 从右向左逐位相加，维护进位 carry
3. 当前位 = (a+b+carry) % 2，新进位 = (a+b+carry) / 2
4. 最后若有进位，最高位补 1

C++ 实现

class Solution {
public:
    string addBinary(string a, string b) {
        if (a.empty()) return b;
        if (b.empty()) return a;
        // 对齐
        if (a.size() < b.size()) swap(a, b);
        b.insert(b.begin(), a.size() - b.size(), '0');
        string res;
        int carry = 0;
        for (int i = a.size()-1; i >= 0; --i) {
            int sum = (a[i]-'0') + (b[i]-'0') + carry;
            res.push_back('0' + (sum & 1));
            carry = sum >> 1;
        }
        if (carry) res.push_back('1');
        reverse(res.begin(), res.end());
        return res;
    }
};

关键技巧

• sum & 1 取最低位，sum >> 1 取进位
• 结果反向构建，最后 reverse
• 处理空串边界

复杂度

• 时间：O(max(|a|,|b|))
• 空间：O(max(|a|,|b|))

扩展：大整数加法通用模板

相同逻辑适用于任意进制，只需修改基数。