5

Need to get sum of x and y without + operator.

I trid to sum two number using adder.If we xor x and y (x ^ y) , we will get summation without carry. From x & y we can get carry. To add this carry in summation , call add function again. but its not give answer. where is the error in my code.

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

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

Error:

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
Improve this question
1
  • 1
    What about add = int.__add__? Commented May 17, 2020 at 8:32

3 Answers 3

Reset to default
6

You also have to shift the carries:

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
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Well, I liked it too when I saw it. I was more lazy than elegant... ;)
I was lazy - I just tested it with 10,20 and 11,20 because dropping the carry seemed funny - should have tried some more or read it up.
Yep, 10 and 20 was just bad luck - I even did it by hand afterward to see how it managed to give the right answer anyway! A nice problem now would be to generate test cases that succeed with the wrong algorithm...
0

This explains only why you end in an endless loop. Your proposed addition algorithm is flawed, see Thierry Lathuille's answer for a correct addition as well.

You forgot half of the base case:

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))

prints

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

Debugging:

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
Improve this answer

1 Comment

@Asha see the edit - I added some output and the binary calculations
0

You missed two condition. If b == 0 then return a. Then also shift carry.

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))
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.