题目描述
二进制加法：给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
输入为 非空 字符串且只包含数字 1 和 0。
提示：
- 每个字符串仅由字符 '0' 或 '1' 组成。
- 1 <= a.length, b.length <= 10^4
- 字符串如果不是 "0" ，就都不含前导零。
代码&思路
直接运算
class Solution:
def addBinary(self, a, b) -> str:
return '{0:b}'.format(int(a, 2) + int(b, 2))
算法复杂度：O(a.length + b.length)
位运算
二进制加法可以拆分为按位相加（相同为0，不同为1），逐个进位（当前位有进位，前一位加1）的运算。所以可以分解为多次循环求解。
每次循环：
ans^CF（异或运算）取得无进位数ans；
ans&CF（与运算）取得进位CF，左移得到进位；
直到进位CF等于0，也就是无进位，运算结束。
class Solution:
def addBinary(a, b):
CF = 1
x, y = int(a, 2), int(b, 2)
while CF：:
ans = x ^ y
CF = (x & y) << 1
x, y = ans, CF
return bin(ans)[2:]
算法复杂度：O(max {x.length, y.length} )