jmcnuggsmagic13 - 1 month ago 44
Python Question

# How to carry a digit when doing binary addition?

Code:

``````def add_bitwise(b1, b2):
if b1 == '':
return b2
elif b2 == '':
return b1
else:
if b1[-1] == '0' and b2[-1] == '0':
return sum_rest + '0'
elif b1[-1] == '1' and b2[-1] == '0':
return sum_rest + '1'
elif b1[-1] == '0' and b2[-1] == '1':
return sum_rest + '1'
elif b1[-1] == '1' and b2[-1] == '1':
return sum_rest + add_bitwise(b2[:-1],'1') + '0'
``````

So I have to make this function that takes two binary numbers and adds them. This has to be done using recursion and cannot convert the numbers to decimal, add and then convert back to binary. So my base cases say that if one binary number is empty return the other and vice a versa. Then for my recursive call if two zeroes are added it returns 0 and the recursive call. If a 0 and a 1 are added it adds one and a recursive call.

Now here's where I'm stuck. Two ones makes 0 and then you have to carry a 1 to the next side but I can't figure out how to do this within the second recursive call. Sum rest is the normal recursive call, then follows the recursive call to carry the digit, and then the 0. The function must stay as designed but the recursive call needs to be fixed.

Your overflow recursions must sum up `'1'` against `sum_rest`, not `b2[:-1]`. Overflow is carried over to the higher-valued digits.

Here's a slightly shorter implementation:

``````def ab(b1, b2):
if not (b1 and b2):  # b1 or b2 is empty
return b1 + b2
if b1[-1] == '0':  # 0+1 or 0+0
For example, consider the binaries `'011'` and `110`. You'd do the following operations by hand:
• `0 + 1 => 1`, keep 1, no overflow
• `1 + 1 => 10`, keep 0, overflow
• `0 + 1 + 1 => 10`, keep 0, overflow
• `/ + / + 1 => 1`, keep 1, no overflow