题目描述

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

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

样例

示例 1:

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

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

算法

二进制求和，满二进一

首先让两个字符串等长，若不等长，在短的字符串前补零，否则之后的操作会超出索引。
然后从后到前遍历所有的位数，同位相加，这里有一个点，用的是字符相加，利用 ASCII 码，字符在内部都用数字表示，我们不需要知道具体数值，但可知 ‘0’-‘0’ = 0， ‘0’+1=‘1’，以此类推 。字符的加减，大小比较，实际上都是内部数字的加减，大小比较
判断相加后的字符，若大于等于字符 ‘2’‘2’，下一位需要进一
第 00 位数的相加在这里是单独处理的，因为它可能涉及到字符的插入（即是否需要在最前面加一位数 ‘1’‘1’

C++ 代码

class Solution {
public:
    string addBinary(string a, string b) {
        if (a.empty() && b.empty()) return "";
        if (a.empty()) return b;
        if (b.empty()) return a;
        string s(max(a.size(), b.size()), '0');
        int ia = a.size() - 1, ib = b.size() - 1, i = s.size() - 1, up = 0;
        // a和b同时加
        while (ia >= 0 && ib >= 0)
        {
            int tmp = a[ia] - '0' + b[ib] - '0' + up;
            if (tmp > 1)
            {
                tmp = tmp % 2;
                up = 1;
                s[i] = tmp + '0';
            }
            else
            {
                up = 0;
                s[i] = tmp + '0';
            }
            ia--; ib--; i--;
        }
        // a较长的部分加
        while (ia >= 0)
        {
            int tmp = a[ia] - '0' + up;
            if (tmp > 1)
            {
                tmp = tmp % 2;
                up = 1;
                s[i] = tmp + '0';
            }
            else
            {
                up = 0;
                s[i] = tmp + '0';
            }
            ia--; i--;
        }
        // b较长的部分加
        while (ib < b.size())
        {
            int tmp = b[ib] - '0' + up;
            if (tmp > 1)
            {
                tmp = tmp % 2;
                up = 1;
                s[i] = tmp + '0';
            }
            else
            {
                up = 0;
                s[i] = tmp + '0';
            }
            ib--; i--;
        }
        // 进位
        if (up > 0)
            s.insert(s.begin(), '1');
        return s;
    }
};