LeetCode67(二进制求和[位运算,大数运算])

二进制求和

题目要求:
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

这道题其实有几种解法.我们先来介绍简单的方法.
我们可以将两个字符串的二进制转成十进制,获取对应值相加之后,我们可以不断对2取余,获取尾数拼接即可.也就是像我们平常求一个十进制的二进制数,可以递归调用,同样也可以迭代.官方题解当中给我们介绍了一种Java自带的API解法,如下所示

class Solution {public String addBinary(String a, String b) {return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));}
}

但是这种解法具有局限性,官方提到:
如果 a 的位数是 n，b 的位数为 m，这个算法的渐进时间复杂度为 O(n+m)。但是这里非常简单的实现基于 Python 和 Java 本身的高精度功能，在其他的语言中可能并不适用，并且在 Java 中：

• 如果字符串超过 33 位，不能转化为 Integer
• 如果字符串超过 65 位，不能转化为 Long
• 如果字符串超过 500000001 位，不能转化为 BigInteger

所以我们需要一个更加健全的解法
对于这两个字符串,我们可以对最末端,不断相加,若有进位,保留进位相加.一步步拼接字符串.由于是二进制的运算,我们很容易联系到位运算.

对于位运算来讲,十进制的相加我们可以模拟成(a b 相加)
无进位时: sum = a ^ b
有进位时: sum = a ^ b + (a & b) << 1

例如: a = 3 b = 1 时
我们将其转换为二进制
a: 11
b: 01
我们先进行异或运算可以求的没有进位的位相加的结果,这里我们可以得到
temp = 10;
其次我们来求得需要进位的位置,需要进位其实就是上下两端都等于1时,所以我们可以用&运算来实现我们的需求
求得 carry = 01;左移一位得到 carry = 10;
重复上述过程,直至(a & b) == 0即没有进位为止
temp ^ carry = 00;
temp & carry = 10;
左移相加得到 100;满足相加的结果.

而这里我们只需要对当前与进位数相加后,计算此时进位的值,循环往复即可,所以公式得到
sum = x ^ y ^ carry;
carry = (x & y) [这里是有点问题的,我们后面再讨论]

所以我们初步的解题步骤为

我们需要比较两个字符串长度最小值选取为第一次循环的终止条件,然后从字符串的最后面开始遍历,不断对最后一位进行异或运算.代码为

		int size = Math.min(aLength,bLength);int carry = 0;StringBuilder sb = new StringBuilder();for(int i = 0;i < size;i++){int x = a.charAt(--aLength)-'0';int y = b.charAt(--bLength)-'0';int sum = (x ^ y ^ carry);carry = ( x & y) ; sb.append(sum);}

这段代码其实是有一点问题的,我们思考下面这种情形.
当x = 1 , y = 0 ,carry = 1时
我们的 carry 计算公式为 = x & y
这样将会错过进位的运算.
那会有人提出三个数做异或运算呗,像那个sum一样
注意:
我们sum求值概念为三数求值相加后余下来的值,所以我们对三个数做异或运算就可以满足此特性.
但是此时进位处和其不太一样
我们需要只要出现两个1,我们的进位就应该是1.
那我们先来思考x与y的取值有几种情形
x = 1 y = 0
x = 0 y = 1
x = 0 y = 0
x = 1 y = 1
我们讨论的情况当carry = 1时.属于x,y中最多只有一个数出现为1时,我们需要进位 置1.也就是我们进行xy的异或运算后再进行对carry的&运算.

而对于carry = 0而且x与y都等于1时,我们不需要carry进行对应的运算.
所以我们列出改进后的代码

		for(int i = 0;i < size;i++){int x = a.charAt(--aLength)-'0';int y = b.charAt(--bLength)-'0';int sum = (x ^ y ^ carry);//carry == 1 x==1 y==0 如果采用x&y 这里会错过进位if(carry == 1 && x!=1 && y!=1){carry = (x^y) & carry ;}else if(carry == 0) carry = ( x & y) ;sb.append(sum);}

此时我们已经完成了较短的字符串的二进制运算
而对于剩下的那个我们仍需要进行字符串的拼接,但我们需要注意的是
可能在第一次循环过后最后相加的那个结点处,我们产生了进位,所以我们依旧需要对进位进行处理.

		while (aLength > 0){int x = a.charAt(--aLength)-'0';int sum = (x ^ carry);carry = ((x&carry));sb.append(sum);}while (bLength > 0){int y = b.charAt(--bLength)-'0';int sum = (y ^ carry);carry = ((y&carry));sb.append(sum);}

看样子好像已经挺完善啦,其实我们还是漏了一点.也就是当两个字符串都遍历完后.如果此时最高位产生了进位,我们是需要扩展原来的长度,即再加一位来存放最高处的进位.
所以完整代码为

class Solution {public String addBinary(String a, String b) {int aLength = a.length();int bLength = b.length();if(aLength < 1) return b;if(bLength < 1) return a;int carry = 0;int size = Math.min(aLength,bLength);StringBuilder sb = new StringBuilder();for(int i = 0;i < size;i++){int x = a.charAt(--aLength)-'0';int y = b.charAt(--bLength)-'0';int sum = (x ^ y ^ carry);//carry == 1 x==1 y==0 如果采用x&y 这里会错过进位if(carry == 1 && x!=1 && y!=1){carry = (x^y) & carry ;}else if(carry == 0) carry = ( x & y) ;sb.append(sum);}while (aLength > 0){int x = a.charAt(--aLength)-'0';int sum = (x ^ carry);carry = ((x&carry));sb.append(sum);}while (bLength > 0){int y = b.charAt(--bLength)-'0';int sum = (y ^ carry);carry = ((y&carry));sb.append(sum);}if(carry > 0) sb.append(carry);return sb.reverse().toString();}
}

结果为: