只有位运算符的两个数字总共？ [重复]

Question

这个问题在这里已有答案：

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

我的问题是，如何在不使用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。