Python adding binary without using decimal form

Question

I'm trying to add two binary numbers together without converting the numbers to decimal form. This has been difficult because you must add the carries as well. What am I missing?

def sameSingleLengthAdd(bin1 , bin2):
    if len(bin1) > len(bin2):
        minus = len(bin1) - len(bin2)
        newBin2
        return addAll(bin1, newBin2)
    elif len(bin2) > len(bin1):
        minus1 = len(bin2)- len(bin1)
        newBin1 = '0'*minus1 + bin1
        return addAll(newBin1, bin2)


def singleAdd(int1, int2):
    addThem = int(int1) + int(int2)
    if addThem == 2:
        return '0'
    else:
        return '1'

def addAll(bin1, bin2):
    if len(bin1)== 0:
        return ''
    else:
        return addAll(bin1[:-1], bin2[-1]) + singleAdd(bin1[-1], bin2[-1])

def sameCarryLengthAdd(bin1 , bin2):
    if len(bin1) > len(bin2):
        minus = len(bin1) - len(bin2)
        newBin2
        return carries(bin1, newBin2)
    elif len(bin2) > len(bin1):
        minus1 = len(bin2)- len(bin1)
        newBin1 = '0'*minus1 + bin1
        return carries(newBin1, bin2)
    else: return carries(bin1, bin2)

def carries(bin1, bin2):
    addThem = int(bin1[-1]) + int(bin2[-1])
    if len(bin1) == 0:
        return ''
    elif addThem == 2:
        return carries(bin1[:-1], bin2[:-1]) + '10'
    else:
        return carries(bin1[:-1], bin2[:-1]) + '0'


def addBinary(bin1, bin2):
    carriedBin = sameCarryLengthAdd(bin1, bin2)
    otherNum = sameSingleLengthAdd(bin1, bin2)
    return sameSingleLengthAdd(carriedBin, otherNum )

"without converting the numbers to decimal form" - Python isn't going to convert the numbers to decimal to add them. In fact, when you give it decimal, it has to convert that to binary to work with it. — user2357112, Feb 22 '14 at 23:39
"What am I missing?" - well, I dunno. What's wrong? What actually happens when you run this, and how does it differ from what you expect? — user2357112, Feb 22 '14 at 23:40
i get a string index error for carries(bin1[:-1] , bin2[:-1]) — user3316195, Feb 22 '14 at 23:42
I think you'll probably find a lot of your bugs if you just go back and read what you wrote. For example, line 4, `newBin2`. What was that supposed to do? Did you get distracted from that function halfway through and forget to finish writing it? — user2357112, Feb 22 '14 at 23:43
Possible duplicate of http://stackoverflow.com/questions/1523465/binary-numbers-in-python — Dan Oberlam, Feb 22 '14 at 23:43
and addThem = int(bin1[-1]) + int(bin2[-1]) IndexError: string index out of range — user3316195, Feb 22 '14 at 23:44
I would say it was a duplicate as well but I cannot use bitwise operations — user3316195, Feb 22 '14 at 23:46
This is a lot of bugs. I count at least 4, and I haven't read very closely. I'll do my best to answer the question, but we're not a debugging service. — user2357112, Feb 22 '14 at 23:48

score 0 · Answer 1 · answered Feb 23 '14 at 00:04

Your code is broken in a lot of ways, from typos to fundamentally unworkable design. Rather than go through and point out every reason your program doesn't work, let's redesign it. Let's take a step back to grade school addition.

If you want to add the numbers 795 and 224:

  795
 +224
-----
=

you add digits from the last digit to the first:

  795
 +224
-----
=   9

and whenever the result doesn't fit in a single digit, you add a carry to the next sum:

  1
  795
 +224
-----
=  19

until you run out of digits to add:

 11
  795
 +224
-----
= 019

 11
  795
 +224
-----
=1019

To add numbers in binary, you do the same thing. You start at the end of each number, and for each position, you add the corresponding digits of each number and the carry. The sum you get determines the corresponding digit of the result and the carry used for the next sum. For example, a 3 would mean a result digit of 1 and a carry of 1 for the next position. If one of the numbers runs out of digits before the other, you pretend it has a zero there. You stop when both inputs have no more digits and you don't have a carry.

In pseudocode, this algorithm would be

carry = '0'
result = ''
for position from last to first:
    add carry and digits of each number in the current position
    determine carry and result digit from above sum
    add the new digit to the result

Python adding binary without using decimal form

1 Answers1