CODEWITHSUNDEEP
pythonbinaryaddition
Phil Cho
Phil Cho

Reputation: 121

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

Upvotes: 0

Views: 1081

Answers (2)

Fabricator
Fabricator

Reputation: 12772

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

Upvotes: 1

2ps
2ps

Reputation: 15926

Let’s start with the first part, which is making sure the two strings are the same length. Since they're numbers, all you have to do is '0' pad the shorter number

max_len = max(len(S), len(T))
# the more simple to understand way
while len(S) < max_len: S = '0' + S
while len(T) < max_len: T = '0' + T
# or you can use this python trickery
S = ('0' * (max_len - len(S))) + S
T = ('0' * (max_len - len(T))) + T

For the carries, your carries should be as follows:

For sum = 0, carry = 0
For sum = 1, carry = 0
For sum = 2, carry = 1
For sum = 3, carry = 1

Hope that helps,

Upvotes: 0

Related Questions