Jianbo Dai's

mq066.二进制求和

 
  • Mar 05, 2021

题目链接

很久没有做算法题了，居然看到简单题也很生疏。当即就看了一题解，我印象中有做过类似的题目的来着。有两种做法，第一种就是模拟，末尾对齐，逐位相加。在二进制中我们需要逢二进一。具体来说，我们先取n为a和b中较大的一个length，循环n次，从最低位开始遍历。我们用一个变量carry表示上一个位置的进位，初始值为0。记当前位置对齐的两个位为ai和bi，则每一位的答案为(carry+ai+bi)mod2，下一位的进位为[(carry+ai+bi)//2]。重复上述步骤，直到数字a和b的每一位计算完毕。最后如果carry的最高位不为0，则将最高位添加到计算结果的末尾。注意，为了使得各个位置对齐，可以先反转这个代表二进制数字的字符串然后低下标对应低位，高下标对应高位。要记住最终答案也要进行翻转。这个算法的时间复杂度是O（n），空间复杂度是O（1）。

还有另外一种思路是使用位运算。把a和b转换成整型数字x和y，然后用x保存结果，y保存进位。当进位不为0时：1.计算当前x和y的无进位相加结果: answer = x ^ y；2.计算当前x和y的进位: carry = (x & y) « 1；3.完成本次循环，更新 x = answer, y = carry。最后返回x的二进制形式。为什么该方法可行呢？因为在第一轮计算中，answer的最后一位是x和y相加后的结果，carry的倒数第二位是x和y最后一位相加的进位。接着每一轮中，由于carry是由x和y按位与并且左移得到的，那么最后会补零，所以在下面的计算中后面的数位不受影响，而每一轮都可以得到一个第i的答案和它向第i+1位的进位，也就模拟了加法的过程。

python:

class Solution:
    def addBinary1(self, a: str, b: str) -> str:
        ans = []
        a, b = a[::-1], b[::-1]
        maxlen = max(len(a), len(b))
        carry = 0
        for i in range(maxlen):
            if i < len(a):
                carry += 1 if a[i] == "1" else 0
            if i < len(b):
                carry += 1 if b[i] == "1" else 0
            print(carry)
            if carry % 2 == 1:
                ans.append(1)
            else:
                ans.append(0)
            carry //= 2

        if carry == 1:
            ans.append(1)
        ans = ans[::-1]

        return "".join([str(x) for x in ans])
		
    def addBinary2(self, a: str, b: str) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            answer = x ^ y
            carry = (x & y) << 1
            x, y = answer, carry
        return bin(x)[2:]

C++:

class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int n = max(a.size(), b.size()), carry = 0;
        for (size_t i = 0; i < n; ++i) {
            carry += i < a.size() ? (a.at(i) == '1') : 0;
            carry += i < b.size() ? (b.at(i) == '1') : 0;
            ans.push_back((carry % 2) ? '1' : '0');
            carry /= 2;
        }
        if (carry) {
            ans.push_back('1');
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};
Search