Phil Cho Phil Cho - 1 month ago 7
Python Question

Binary Addition using a carry

Im trying to add two binary numbers without converting the two numbers, S and T, into a base 10,using recursion and I'm having difficulty incorporating the carry into the code. Also, I'm not exactly sure what to do if one binary number is longer than the other.

def addB(S,T):
'''adds binary number without converting to base 10'''
def addBhelper(S,T,carry):
if S=='' and T=='':
return ''
if S[-1] + T[-1]+carry==0:
return addBhelper(S[:-1],T[:-1],0) + str((carry+int(S[-1]) + int(T[-1]))% 2)
if S[-1] + T[-1]+carry==1:
return addBhelper(S[:-1],T[:-1],1) + str((carry+int(S[-1]) + int(T[-1])) % 2)
if S[-1] + T[-1]+carry==2:
return addBhelper(S[:-1],T[:-1],2) + str((carry+int(S[-1]) + int(T[-1])) % 2)
if S[-1] + T[-1]+carry==3:
return addBhelper(S[:-1],T[:-1],2) + str((carry+int(S[-1]) + int(T[-1])) % 2)
return addBhelper(S,T,0)


---- updated to fix code formatting

Answer

Here's a cleaner version that uses some Python syntactic sugar:

def add(a,b,c=0):
    if a == '' and b == '':
        return str(c)
    a = a or '0'
    b = b or '0'
    n = int(a[-1]) + int(b[-1]) + c
    return add(a[:-1],b[:-1],n//2) + str(n%2)
  • Use default value of carry c=0 to get rid of the inner function
  • a = a or '0' sets a to '0' if it's ''
  • You forgot to convert string to integer before adding them
  • n//2 get the carry
Comments