python - 二进制加法时如何进位？

Question

代码:

def add_bitwise(b1, b2):
    '''Adds two binary numbers.'''
    if b1 == '':
        return b2
    elif b2 == '':
        return b1
    else:
        sum_rest = add_bitwise(b1[:-1],b2[:-1])
        if b1[-1] == '0' and b2[-1] == '0':
            return sum_rest + '0'
        elif b1[-1] == '1' and b2[-1] == '0':
            return sum_rest + '1'
        elif b1[-1] == '0' and b2[-1] == '1':
            return sum_rest + '1'
        elif b1[-1] == '1' and b2[-1] == '1':
            return sum_rest + add_bitwise(b2[:-1],'1') + '0'    

所以我必须使这个函数接受两个二进制数并将它们相加。这必须使用递归来完成，并且不能将数字转换为十进制、相加然后转换回二进制。所以我的基本情况是，如果一个二进制数为空，则返回另一个，反之亦然。然后，对于我的递归调用，如果添加两个零，它将返回 0 和递归调用。如果添加 0 和 1，则会添加 1 和递归调用。

现在我被困住了。两个 1 等于 0，然后你必须将 1 带到下一侧，但我不知道如何在第二个递归调用中执行此操作。 Sum rest 是正常的递归调用，然后在递归调用后面携带数字，然后是 0。函数必须保持设计不变，但需要修复递归调用。

Answer 1

溢出会转移到结果的高位数字，而不仅仅是一个数字。溢出递归必须对整个 sum_rest 求和 '1'，而不是 b2[:-1]。

这是一个稍微简短的实现:

def bin_add(bin1: str, bin2: str) -> str:
    # bin1 or bin2 is empty, just use the non-empty one
    if not bin1 or not bin2:
        return bin1 + bin2   # '' + '1' or '1' + '' => '1'
    # split computation into the
    # "current/lowest digit" and "higher digits"
    head = bin_add(bin1[:-1], bin2[:-1])
    # simple case: no overflow at the current digit
    if bin1[-1] == '0':  # 0+1 or 0+0
        return head + bin2[-1]
    if bin2[-1] == '0':  # 1+0
        return head + '1'
    # overflow: add '1' to higher digits
    return bin_add(head, '1') + '0'

例如，考虑二进制文件 '011' 和 '110'。人们可以手动执行以下操作:

• 0 + 1 => 1，保留1，不溢出
• 1 + 1 => 10，保留 0，溢出
• 0 + 1 + 1 => 10，保留 0，溢出
• /+/+ 1 => 1，保留1，不溢出