python中不带+运算符的求和

Question

需要在不使用+运算符的情况下获得x和y的和

我用加法器求两个数的和。如果我们对x和y进行异或运算（x ^ y），我们将得到不带进位的和。从x & y我们可以得到进位。要添加此进位求和，请再次调用add函数。但它并没有给出答案。我的代码中的错误在哪里

def add(a,b):
    if a == 0:
        return b
    return add(a^b, a&b)

x = 10
y = 20
print(add(10, 20))

错误：

File "main.py", line 4, in add

return add(a^b, a&b)                                                                                                                          File "main.py", line 4, in add                                        

return add(a^b, a&b)                                                                                                                          File "main.py", line 4, in add                                        

return add(a^b, a&b)                                                                                                                          File "main.py", line 4, in add                                        

return add(a^b, a&b)                                                                                                                          File "main.py", line 4, in add                                        

return add(a^b, a&b)                                                                                                                          File "main.py", line 4, in add                                        

return add(a^b, a&b)                                                                                                                          File "main.py", line 4, in add                                        

return add(a^b, a&b)                                                                                                                          File "main.py", line 4, in add                                        

return add(a^b, a&b)                                                                                                                          File "main.py", line 4, in add                                        

return add(a^b, a&b)                                                                                                                          File "main.py", line 2, in add                                        

if a == 0:                                                                                                                                  RuntimeError: maximum recursion depth exceeded in comparison

Answer 1

您还必须改变进位：

def add(a,b):
    if a == 0:
        return b
    if b == 0:
        return a
    return add(a^b, (a&b) << 1)

x = 3
y = 2
print(add(x, y))
# 5

Answer 2

这只解释了为什么你会以一个无休止的循环结束。您提出的加法算法有缺陷，请参见Thierry Lathuille的答案以了解正确的加法

---

您忘记了基本案例的一半：

def add(a,b):
    if a == 0 or b==0:   # if either one is zero
        return a or b         # return the non-zero one (or 0 if both are 0)
    return add(a^b, a&b)

x = 10
y = 20
print(add(10, 20))

印刷品

30     # this only works for some numbers, you algo is not correct, try add(3,2)

---

调试：

def add(a,b):
    print(f"a  {bin(a):>10}")
    print(f"b  {bin(b):>10}")
    if a == 0 or b==0:
        return a or b
    return add(a^b, a&b)

a      0b1010
b     0b10100
      -        # manually added the xor/and
xor     11110        # to show what happens:
and     00000        # b is 0       

a     0b11110
b         0b0        # now it terminates as b is 0

Answer 3

你错过了两个条件。如果b==0，则返回a。然后再移位进位

def add(a,b):
    if a == 0:
        return b
    if b == 0:
        return a
    return add(a^b, a&b << 1)

x = 10
y = 20
print(add(10, 20))