[LeetCode] 67. 二进制求和

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入：a = "11", b = "1"
输出："100"

示例 2：

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

提示：

1 <= a.length, b.length <= 10⁴
a 和 b 仅由字符 '0' 或 '1' 组成
字符串如果不是 "0" ，就不含前导零

思路:

从字符串末尾取字符，转为数字再相加就行，只是要注意处理进位值

AC代码:

一种无脑写法是：

class Solution {
public:
    string addBinary(string a, string b) {
        string Result;
        int CarryOver = 0;
        while(a.size() || b.size())
        {
            int temp = 0;
            if(a.back() == '1')
            {
                temp++;
            }
            if(a.size())
            {
                a.pop_back();
            }
            if(b.back() == '1')
            {
                temp++;
            }
            if(b.size())
            {
                b.pop_back();
            }
            temp = temp+ CarryOver;
            CarryOver = temp / 2;
            temp = temp % 2;
            Result = (to_string(temp) + Result);
        }
        if(CarryOver>0)
            Result = ("1" + Result);
        return Result;
    }
};Code language: C++ (cpp)

进一步地，可以用按位逻辑运算来处理每一位二进制值和进位，再拼接到字符串首部，这样会快不少：

class Solution {
public:
    string addBinary(string a, string b) {
        string Result;
        int CarryOver = 0;
        
        while(a.size() || b.size())
        {
            int bitA = 0, bitB = 0;
            
            if(a.size()) {
                bitA = a.back() - '0';
                a.pop_back();
            }
            
            if(b.size()) {
                bitB = b.back() - '0';
                b.pop_back();
            }
            int sum = bitA ^ bitB ^ CarryOver;
            
            CarryOver = (bitA & bitB) | (bitB & CarryOver) | (bitA & CarryOver);
            
            Result = char('0' + sum) + Result;
        }
        
        if(CarryOver)
            Result = '1' + Result;
            
        return Result;
    }
};Code language: C++ (cpp)

但如果会使用 string 库，那就能更简洁：

class Solution {
public:
    string addBinary(string a, string b) {
        string output;
        string::reverse_iterator it_a = a.rbegin();
        string::reverse_iterator it_b = b.rbegin();
        uint8_t carry = 0;

        while (it_a != a.rend() || it_b != b.rend()) {
            uint8_t sum = 0;
            if (it_a != a.rend()) {
                sum += (*it_a - '0');
                ++it_a;
            }
            if (it_b != b.rend()) {
                sum += (*it_b - '0');
                ++it_b;
            }
            sum += carry;
            carry = sum / 2;
            if (sum % 2 == 0) {
                output = '0' + output;
            }
            else {
                output = '1' + output;
            }
        }

        if (carry > 0) {
            output = '1' + output;
        }

        return output;
    }
};Code language: C++ (cpp)

不过内存用量最少且最快的写法是这样：

class Solution {
public:
    string addBinary(string a, string b) {
        int n = max(a.size(), b.size()), c = 0;
        string r(n + 1, '0');
        
        for (int i = 0; i < n; ++i) {
            int da = i < a.size() ? a[a.size()-1-i] - '0' : 0;
            int db = i < b.size() ? b[b.size()-1-i] - '0' : 0;
            int s = da + db + c;
            r[n-i] = '0' + (s & 1);
            c = s >> 1;
        }
        r[0] = '0' + c;
        
        return c ? r : r.substr(1);
    }
};Code language: C++ (cpp)