题目

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

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

示例 1:

输入: a = “11”, b = “1”
输出: “100”

示例 2:

输入: a = “1010”, b = “1011”
输出: “10101”

提示：

每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 “0” ，就都不含前导零。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/add-binary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题虽然是简单，但是有不少东西可以学到。

常规且稳妥的做法还是模拟加法，就和第2题两数相加思路一样，不过多介绍了，见代码一。

需要注意的是「官解」中讲的，对于Java和python在字符串不是很长的情况下可以先转数字，然后直接相加，或者利用「位运算」。

两个数进行异或即「x^y」可以看做是不进位的加法，而两数做位与运算并左移一位即「x&y<<1」则可以得到每位的进位，将二者相加等同于原数相加。

这种解法只有python可以通过，因为python的数可以无限大，见代码二，字符串过长时java转数会很麻烦。

代码

代码一

  1. class Solution {
  2.     public String addBinary(String a, String b) {
  3.         int m = a.length();
  4.         int n = b.length();
  5.         int p = m - 1;
  6.         int q = n - 1;
  7.         int carry = 0;
  8.         StringBuilder sb = new StringBuilder();
  9.         while (p >= 0 || q >= 0) {
  10.             int f = p >= 0 ? a.charAt(p) - '0' : 0;
  11.             int g = q >= 0 ? b.charAt(q) - '0' : 0;
  12.             sb.append((f + g + carry) % 2);
  13.             carry = (f + g + carry) / 2;
  14.             p--;
  15.             q--;
  16.         }
  17.         if (carry == 1) {
  18.             sb.append('1');
  19.         }
  20.         return sb.reverse().toString();
  21.     }
  22. }

代码二

  1. class Solution:
  2.     def addBinary(self, a, b) -> str:
  3.         x, y = int(a, 2), int(b, 2)
  4.         while y:
  5.             answer = x ^ y
  6.             carry = (x & y) << 1
  7.             x, y = answer, carry
  8.         return bin(x)[2:]