67.二进制求和题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/add-binary题目给你两个二进制字符串，返回它们and（以二进制表示）。输入是一个只包含数字1和0的非空字符串。示??例1：输入：a="11",b="1"输出："100"示例2：输入：a="1010",b="1011"输出："10101"提示：每个字符串仅由字符'0'或'1'组成。1<=a.length,b.length<=10^4除非它们是"0"，否则所有字符串都不包含前导零。解题思路：位运算题提示中有说明，如果字符串不为“0”，则不包含前导零。这里我们先用普通的加法来尝试解题。由于这个前提，在进行加法运算时，需要先对字符求补，然后逐位相加。该方法的具体步骤如下：首先对两个字符串进行补码，方便逐位相加。这里，可以在字符的添加中进行进位。这里使用进位变量来存储链表中逐位相加的结果。最后转为字符串返回。该方法的代码大致如下：defaddBinary(self,a:str,b:str)->str:whilelen(a)>len(b):b='0'+bwhilelen(a)=2:carry=1#每2进位，当前位置的元素为add_res-2ans[i]=str(add_res-2)else:carry=0ans[i]=str(add_res)#最后需要再次确认最终操作是否有进位return''.join(['1']+ans)ifcarryelse''.join(ans)这段代码使用普通的加法来解决问题。让我们尝试不加减法来解决这个问题，这涉及到位运算。这里又是按位与、异或运算。按位与运算：指参与运算的两个数对应的二进制与。运算规则是当对应的基位全部为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）具体代码实现为如下。代码实现类解决方案：defaddBinary(self,a:str,b:str)->str:#转换为整数值m,n=int(a,2),int(b,2)#循环中的n存储进位#当进位为0时，循环结束whilen:#异或计算无进位加法结果ans=m^n#计算进位#进位应该在高位，所以需要移到左进位=(m&n)<<1#重置m,n;此时m存结果，n存进位m=ansn=carry#m存结果，当n为0时表示无进位#循环结束，返回m的二进制形式#注意以二进制形式转换Prefix'0b'returnbin(m)[2:]实现结果总结先用普通加法解决问题，具体实现如下：因为需要逐位进行此外，有必要补充给定的字符；进行逐位加法（字符只包含0和1），每2进1，则需要定义进位变量保存进位；将逐位相加的结果放在一个列表中，然后转换成字符串返回。虽然题目中并没有提到不能使用加减法。但是如果有限制的话，可以考虑用位运算来模拟加法。这里涉及两个位运算：按位与和异或按位与运算：指运算中涉及的两个数对应的二进制与。运算规则是当对应的基位全部为1时，结果为1，否则为0。异或运算：也叫半加运算，因为它的算法等同于不带进位的二进制加法。关于使用位运算的实现方法：先进行异或运算，得到非进位加法结果后进行按位与运算，再根据按位与算法得到进位。循环计算，当进位为0时，即可得出结果。
