二进制加法

位运算是将数字用二进制形式表示之后，对每位上0或1的运算，二进制及其位运算是现代计算机科学的基石，

位运算种类：非~、与&、或|、异或^、左移<<、右移>>

  • 按位与&：对应二进制位上，a与b必须同时为真
  • 按位或|：对应二进制进位上，a与b有一边为真即可
  • 异或运算^：对应二进制位上，相同则为0，不同则为1（逆运算首先满足交换律）

关于异或运算的补充：

  1. 异或运算是逆运算：由 a ^ b = c 可得 c ^ a = b； c ^ b = a；
  2. 相同的数异或运算为0：n ^ n = 0 ;
  3. 任何数与0异或运算值不变：0 ^ n = n；

问：在文件中有一堆整数，每一次数都出现了两次，其中有一个值只出现了一次，如何快速找到只出现一次的这个数的值？

答：利用异或运算解决，将所有整数互相异或，最后得到的值即为只出现一次的值

  • 左移 m << n ：二进制数整 m 左移n 位
  • 右移 m >> n：二进制数整 m 右移 n 位
运算
按位与& 0 & 0 = 0 1 & 0 = 0 0 & 1 = 0 1 & 1 = 1
按位或| 0 | 0 = 0 1 | 0 = 1 0 | 1 = 1 1 | 1 = 1
按位异或^ 0 ^ 0 = 0 1 ^ 0 = 1 0 ^ 1 = 1 1 ^ 1 = 0

1.数制转换

主要思路：将输入的二进制转换为10进制，使用10进制进行运算，将得到的结果转化回二进制即可。

存在问题：outside the range of representable values of type ‘int’，将int类型改为long long 无法存储，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    string _10to2(int num) {
        if (num == 0) return "0";
        int len = 0; int x = num; while (x) {x /= 2; len++;}
        string str = "";
        for (int i = 0; i < len; ++i) str += "0";

        int i = len - 1;
        while (num) {
            str[i] = num % 2 + '0';
            num /= 2;
            i--;
        }
        return str;
    }

    int _2to10(string str) {
        int num = 0;
        int len = str.size();
        for (int i = 0; i < len; ++i) {
            num += pow(2, len - i - 1) * (str[i] - '0');
            //num = num * 10 + str[i] - '0';
        }
        return num;
    }

    string addBinary(string a, string b) {
        int numa = _2to10(a);
        int numb = _2to10(b);
        int sum = numa + numb;
        string ans = _10to2(sum);
        return ans;
    }
};

2.模拟二进制加法

主要思路：参考大整数加法，完成二进制加法运算

写法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//for循环写法
class Solution {
public:
    string addBinary(string a, string b) {
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        string str;
        int t = 0;
        int lena = a.size();
        int lenb = b.size();
        for (int i = 0; i < lena || i <lenb; ++i) {
            if (i < lena && a[i] == '1') t += 1;
            if (i < lenb && b[i] == '1') t += 1;
            str.push_back((t % 2) + '0');
            t /= 2;
        }
        if (t) str.push_back('1');
        reverse(str.begin(), str.end());
        return str;
    }
};

写法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//while循环写法 减少两次reverse函数调用
class Solution {
public:
    string addBinary(string a, string b) {
        string str;
        int t = 0;
        int l1 = a.length() - 1;
        int l2 = b.length() - 1;
        while (l1 >= 0 || l2 >= 0) {
            if (l1 >= 0 && a[l1] == '1') t += 1;
            if (l2 >= 0 && b[l2] == '1') t += 1;
            str.push_back((t % 2) + '0');
            t /= 2;
            l1--;
            l2--;
        }
        if (t) str.push_back('1');
        reverse(str.begin(), str.end());
        return str;
    }
};
  • 时间复杂度：$O(n)$，这里的时间复杂度来源于顺序遍历 $a$ 和 $b$
  • 空间复杂度：$O(1)$，除去答案所占用的空间，这里使用了常数个临时变量

3.位运算

不允许使用加减乘除，则可以使用位运算替代上述运算中的一些加减乘除的操作

  1. 把 a 和 b 转换成整型数字 x 和 y，在接下来的过程中，x 保存结果，y 保存进位。
  2. 当进位不为 0 时
    • 计算当前 x 和 y 的无进位相加结果：answer = x ^ y
    • 计算当前 x 和 y 的进位：carry = (x & y) << 1
    • 完成本次循环，更新 x = answer，y = carry
  3. 返回 x 的二进制形式

为什么这个方法是可行的呢？

在第一轮计算中，answer 的最后一位是 x 和 y 相加之后的结果，carry 的倒数第二位是 x 和 y 最后一位相加的进位。

接着每一轮中，由于 carry 是由 x 和 y 按位与并且左移得到的，那么最后会补零，所以在下面计算的过程中后面的数位不受影响，而每一轮都可以得到一个低 i 位的答案和它向低 i+1 位的进位，也就模拟了加法的过程。

1
2
3
4
5
6
7
8
class Solution:
    def addBinary(self, a, b) -> 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:]