16二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。

示例 1:
输入: a = "11", b = "1"
输出: "100"

示例 2:
输入: a = "1010", b = "1011"
输出: "10101"

提示：
每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。

#内置函数
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return bin(int(a, 2) + int(b, 2))[2:]

非内置函数
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        r, p = '', 0
        d = len(b) - len(a)
        a = '0' * d + a
        b = '0' * -d + b
        for i, j in zip(a[::-1], b[::-1]):
            s = int(i) + int(j) + p
            r = str(s % 2) + r
            p = s // 2
        return '1' + r if p else r

#进位加法原理
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        if len(a) < len(b): 
            a, b = b, a
        n = len(a)
        b = '0'*(n - len(b)) + b    #补齐 b 不足的位为 0
        result = ''
        summ = 0    #进位值
        for i in range(n):
            a_1 = int(a[-i-1])
            b_1 = int(b[-i-1])
            result = str((a_1 + b_1 + summ) % 2) + result    #当前位数相加模 2 ，链接更小位数的值
            summ = (a_1 + b_1 + summ) // 2    #当前位数之和整除二，得到下一位运算的进位值
        
        if summ == 1:    #判断最高位是否需要进位
            result = '1' + result
        return result

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        add_dict = {
            #第一位和第二位代表来自a，b的两个字符，第三位代表是否有来自前一位加法的进位（即下方的extra）
            "100": '1',
            "101": '10',
            "010": '1',
            "011": '10',
            "000": '0',
            "001": '1',
            "110": '10',
            "111": '11',
            #第一位来自一个字符，第二位来自进位情况（a,b长度不同，其中一个字符串已经遍历完成，另一段没有完成）
            "10": "1",
            "11": "10",
            "00": "0",
            "01": "1",
        }
        #将字符串倒置，最小位就是第一位，从第一位开始往后做加法，如有进位，则用extra记录到后面一位的加法中
        a = a[::-1]
        b = b[::-1]
        sum = ""
        extra = "0"
        #从头遍历两串字符串
        for i in range(max(len(a), len(b))):
            #3种情况，ab均未遍历完成，a未完成b完成，a完成b未完成
            if i < len(a) and i < len(b):
                add = add_dict[a[i] + b[i]+extra]
            elif i < (len(a)):
                add = add_dict[a[i]+extra]
            else:
                add = add_dict[b[i]+extra]
            #处理加法结果add
            #3种结果，add='0'或'1'表示没有进位，add='10'表示有进位且此位的结果为0，add='11'表示有进位且此位的结果为1
            if add == "0" or add == "1":
                sum += add
                extra = "0"
            elif add == "10":
                sum += "0"
                extra = "1"
            else:
                sum += "1"
                extra = "1"
        #若遍历完成，仍有进位，则在结果末尾加1
        if extra == "1":
            sum += "1"
        #最后把结果倒置回来
        sum = sum[::-1]
        return sum

来源：力扣（LeetCode）