python - 仅使用按位运算符的两个数字的总和？

Question

这个问题已经有答案了:

Is it possible to write a function adding two integers without control flow and strictly bitwise operations? (1 个回答)

已关闭 4 年前。

我的问题是，如何在不使用 bool、if-else 条件或逻辑运算符的情况下将两个数字相加？

我一直在尝试编写一个在Python中将两个数字相加的代码，但仅使用按位运算符；换句话说，没有循环、if-else 和算术运算符。

我也一直在查看此页面和其他编程站点，但此问题的所有解决方案都有 while 循环或 if-else 条件。我找到了一个假设的解决方案，它本来以为它是递归地完成的，但它产生了一个递归错误:超出了递归的最大深度。因为它没有基本情况

现在我问自己，是否可以做到这一点。那么另一个问题是，这可能吗？如果是的话，我该怎么做？

这是我失败的代码:

x=7
y=2
def Sum(x, y):
    suma=x^y
    carry=(x&y)<<1
    return Sum(suma, carry)
print(Sum(x, y))

Answer 1

您在评论中说输入不得大于 10^5。在这种情况下，有限数量的进位传播步骤足以消除进位项并产生最终的和:

def binop_add(x, y):
    sum, carry = x, y
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 1
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 2
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 3
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 4
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 5
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 6
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 7
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 8
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 9
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 10
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 11
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 12
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 13
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 14
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 15
    # assert carry == 0
    return sum

每轮sum, carry = (sum ^ carry), (sum & carry) << 1保留 sum + carry == x + y 的不变量。每轮结束后，carry必须至少多一个 0 位结束。

15轮后，carry必须以至少 15 个零位结束。对于 carry此时为非零，carry必须至少是 1 << 15 ，即 32768，高于可能值。此时，carry必须为 0，所以 sum + carry == sum == x + y ，我们返回sum .