题目描述

二进制加法
给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
输入为 非空 字符串且只包含数字 1 和 0。
提示：

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

示例 1:

  1. 输入: a = "11", b = "10"
  2. 输出: "101"

示例 2:

  1. 输入: a = "1010", b = "1011"
  2. 输出: "10101"

解题思路

实际就是计算机组成部分ALU加法器的实现
对于两个串a与b
a1a2……an
b1b2……bn
每一位的结果就是由：上一位产生的进位，ai，bi共同决定的

carryi
上一位进位		 1 1 1 1 0 0 0 0
ai 1 1 0 0 1 1 0 0
bi 1 0 1 0 1 0 1 0
resi 结果位 1 0 0 1 0 1 1 0
carryi+1
产生的进位		 1 1 1 0 1 0 0 0

结果位的逻辑表达式 resi = ai^bi^carryi（^为异或）
产生进位逻辑表达式 carryi+1=(ai|bi)&(ai|carryi)&(bi|carryi) （&为与，|为或）

实现代码

  1. public String addBinary(String a, String b) {
  2.   int max = Math.max(a.length(), b.length());
  3.   //        int[] carry = new int[max+1];
  4.   String result = "";
  5.   int carry = 0;
  6.   for(int i = 0; i< max; i++){
  7.     int m = i<a.length()?Integer.parseInt(String.valueOf(a.charAt(a.length()-1-i))):0;
  8.     int n = i<b.length()?Integer.parseInt(String.valueOf(b.charAt(b.length()-1-i))):0;
  9.     result = String.valueOf(m^n^carry).concat(result);
  10.     carry = (m|n)&(m|carry)&(n|carry);
  12.   }
  13.   // 最后一个进位
  14.   if(carry==1){
  15.     result = "1".concat(result);
  16.   }
  17.   return result;
  18. }

时间及空间复杂度分析

时间复杂度为为O(max{a,b})，空间复杂度为O(1)

拓展思路

位运算
没想到。。位运算还能这样用
image.png
我们可以设计这样的算法来计算：
把 a 和 b 转换成整型数字 x 和 y，在接下来的过程中，xx 保存结果，yy 保存进位。
当进位不为 0 时
计算当前 x 和 y 的无进位相加结果：answer = x ^ y
计算当前 x 和 y 的进位：carry = (x & y) << 1
完成本次循环，更新 x = answer，y = carry
返回 xx 的二进制形式
为什么这个方法是可行的呢？在第一轮计算中，answer 的最后一位是 x 和 y 相加之后的结果，carry 的倒数第二位是 x 和 y 最后一位相加的进位。接着每一轮中，由于 carry 是由 x 和 y 按位与并且左移得到的，那么最后会补零，所以在下面计算的过程中后面的数位不受影响，而每一轮都可以得到一个低 i 位的答案和它向低 i + 1 位的进位，也就模拟了加法的过程。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/JFETK5/solution/er-jin-zhi-jia-fa-by-leetcode-solution-fa6t/
来源：力扣（LeetCode）