此文记录我面试中遇到的问题以便学习积累。

我查了一下这个面试题还是比较常见的，只是我这种不刷Leecode的人没见过。

题目：两个二进制的字符串，求这两个二进制相加以后的和，输出当然也是二进制的格式了。

/**

* Given two binary strings, return their sum (also a binary string).

*

* For example, a = "11" b = "1" Return "100".

*/

示例 1:?

输入: a = "11", b = "1"

输出: "100"

?示例 2:?

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

输出: "10101"

?提示：?

· 每个字符串仅由字符 '0' 或 '1' 组成。

· 1 <= a.length, b.length <= 10^4（字符串的长度其实可以无限长，如果长度在有限的整型数字范围还会有另外一种解法）

· 字符串如果不是 "0" ，就都不含前导零。

分析思路：

为啥 "11" + "1" = "100"？

因为是二进制的，所以只要加和是2 就要进位了：

• 首先想到的是整个字符串转二进制处理，行不通，因为字符串长度不限，所以会有溢出的问题。

• 然后想到只能分而治之了，把字符串拆开一位一位的处理，那么再加上考虑进位的问题就可以了。

以下是C++ 的实现版本：

#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
using namespace std;

string addBinary(string a, string b) {
  int l1=a.length()-1,l2=b.length()-1;
  string sum = "";
  int s=0,c=0;
  while(l1>=0 || l2>=0 || c)
  {
    int num1 = l1>=0?a[l1--]-'0':0;
    int num2 = l2>=0?b[l2--]-'0':0;
    s = num1 + num2 + c;
    c = s>>1;
    sum = char(s%2 + '0') + sum;
  }
  return sum;
}

int main() {

cout << addBinary("11","1");

return 0;

}

下面是Java 代码的实现：

    public static String addBinary(String a, String b) {
      
        int i = a.length() - 1;
        int j = b.length() - 1;
        int da = 0;
        int db = 0;
        int carry = 0;
      
        StringBuffer result = new StringBuffer();
      
        while (i >= 0 && j >= 0) {
            da = a.charAt(i--) == '0' ? 0 : 1;
            db = b.charAt(j--) == '0' ? 0 : 1;
            int d = da + db + carry;
            result.append(d % 2 == 0 ? '0' : '1');
            carry = d >> 1;
        }
        if (i >= 0) {
            while (i >= 0) {
                da = a.charAt(i--) == '0' ? 0 : 1;
                int d = da + carry;
                result.append(d % 2 == 0 ? '0' : '1');
                carry = d >> 1;
            }
        } else if (j >= 0) {
            while (j >= 0) {
                db = b.charAt(j--) == '0' ? 0 : 1;
                int d = db + carry;
                result.append(d % 2 == 0 ? '0' : '1');
                carry = d >> 1;
            }
        }
        if (carry == 1) {
            result.append('1');
        }
        return result.reverse().toString();
    }

    public static void main(String args[])
    {
        String consult=addBinary("11","1");
        System.out.print("consult is "+consult);
    }

下面是Python 代码的实现：

    def addBinary(self, a, b):
        while len(a) > len(b):
            b = '0' + b
        while len(a) < len(b):
            a = '0' + a
        sum_val = [0] * len(a)
        # 记录逐位相加的结果，
        # 判断是否有进位
        add_bit = 0
        carry = 0
        for i in range( len(a)-1, -1, -1):
            add_bit = int(a[i]) + int(b[i]) + carry
            # 字符只包含 1 和 0
            # 不包含进位，相加结果最大为 2
            # 包含进位，可能为 3
            if add_bit >= 2:
                carry = 1
                # 逢 2 进位，当前位置的元素则为 add_res - 2
                sum_val[i] = str(add_bit - 2)
            else:
                carry = 0
                sum_val[i] = str(add_bit)
        # 最后还需要再次确认，最终的运算中是否有进位
        return ''.join(['1'] + sum_val) if carry else ''.join(sum_val)       

如果字符长度有限，可以使用二进制相与和异或计算的方法：

（此处ZZ博客：https://www.cnblogs.com/yiluolion/p/13183738.html）

这里再提及下，按位与，异或 运算。?按位与 运算：是指参与运算的两数对应二进制相与。运算的规则是，当对应的进制位都为 1 时，结果才为 1，否则都为 0。?异或 运算：也叫半加运算，因为它的运算法则相当于不带进位的二进制加法。例如：?

• 0⊕0=0，
• 1⊕0=1，
• 0⊕1=1，
• 1⊕1=0
  ?
  可以看出，异或运算法则与加法法则相同，但是不带进位。
  ?
  回到当前的题目，我们现在要用位运算来模拟加法求出结果。现在我们拆解一下，先进行 异或 运算，求得无进位结果。根据 按位与，同为 1，结果位才是 1 的运算规则，可以求得进位。循环运算，直到最终进位为 0 时，也就能得到结果。
  ?
  具体的算法设计如下：
  ?
• 首先将给定字符串 a, b 转换为整数型数字 m, n
• 当有进位时：先进行 异或 运算： ans = m ^ n再进行 按位与 运算获得进位： carry = (m & n) << 1。（这里左移是因为进位应该在更高一位）重置 m, n 的值。此时 m 表示无进位相加结果， n 表示进位，继续循环
• 上面 m 相当于存储结果，返回 m 的二进制形式（注意返回字符中 0b）
  ?

代码实现

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        # 转换为整数型数值 !! 此处要考虑溢出危险
        m, n = int(a, 2), int(b, 2)
?
        # n 在循环中存储进位
        # 当进位为 0，循环结束
        while n:
            # 异或计算无进位相加结果
            ans = m ^ n
            # 计算进位
            # 进位应该在更高一位，所以需要左移
            carry = (m & n) << 1
            # 重置 m，n；此时 m 存储结果，n 存储进位
            m = ans
            n = carry
        # m 存储结果，当 n 为 0，表示无进位
        # 循环结束，返回 m 的二进制形式
        # 注意转换成二进制形式的前缀 '0b'
        return bin(m)[2:]

?

总结：

从时间复杂度来看 Python > Java > C++

从空间复杂度来看 Java > Python > C++