给别人做网站别人经营违法,广州软件开发公司排名,移动网站建设流程,wordpress卡密系统源码主题二进制求和
题目要求: 给你两个二进制字符串 a 和 b #xff0c;以二进制字符串的形式返回它们的和。 这道题其实有几种解法.我们先来介绍简单的方法. 我们可以将两个字符串的二进制转成十进制,获取对应值相加之后,我们可以不断对2取余,获取尾数拼接即可.也就是像我们平常求一…二进制求和
题目要求: 给你两个二进制字符串 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 的位数是 nb 的位数为 m这个算法的渐进时间复杂度为 O(nm)。但是这里非常简单的实现基于 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 x1 y0 如果采用xy 这里会错过进位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 ((xcarry));sb.append(sum);}while (bLength 0){int y b.charAt(--bLength)-0;int sum (y ^ carry);carry ((ycarry));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 x1 y0 如果采用xy 这里会错过进位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 ((xcarry));sb.append(sum);}while (bLength 0){int y b.charAt(--bLength)-0;int sum (y ^ carry);carry ((ycarry));sb.append(sum);}if(carry 0) sb.append(carry);return sb.reverse().toString();}
}结果为:
