二进制加法时如何进位？

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'

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

现在我陷入了困境。两个是 0，然后你必须将 1 带到下一侧，但我不知道如何在第二次递归调用中执行此操作。 Sum rest是正常的递归调用，然后递归调用进位，然后是0。功能必须保持设计，但递归调用需要固定。

Answer 1

您的溢出递归必须将 '1' 与 sum_rest 相加，而不是 b2[:-1]。溢出被转移到更高值的数字。

下面是一个稍微简短的实现：

def ab(b1, b2):
    if not (b1 and b2):  # b1 or b2 is empty
        return b1 + b2
    head = ab(b1[:-1], b2[:-1])
    if b1[-1] == '0':  # 0+1 or 0+0
        return head + b2[-1]
    if b2[-1] == '0':  # 1+0
        return head + '1'
    #      V    NOTE   V <<< push overflow 1 to head
    return ab(head, '1') + '0'

例如，考虑二进制文件 '011' 和 110。您将手动执行以下操作：

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

二进制加法时如何进位？

How to carry a digit when doing binary addition?

python

binary

recursion

addition