3
\$\begingroup\$

I tried to make a function able to compute the binary sum. Binary numbers are passed as list composed of 1 and 0, like [1,1,0,1], [0,0,1], etc. It seems to work. I tried to improve the code, but I don't think this is the best way to make it work. How can I improve this?

def check(value):
    if value%2 == 0: #check if the number can be divided by 2
        amount = int(value / 2) #if so, set the value to 0 and the amount as the number divided by 2
        value = 0
    elif value%2 != 0: #if not so, set the value to 0 and the amount as the previous even number divided by 2
        amount = int((value-1)/2)
        value = 1
    return value, amount #returns the 2 value.

def binary_sum(*args):
"""The program compute the binary sum of 2+ binary lists, like [1,1,1,1] + [0,0,0,1]"""
    i = -1 #control variable
    result = [] #list that will be filled by results' binary numbers
    value = 0 
    amount = 0 #amount carried over
    binaryLength = [] #list of all args length
    for x in args:  binaryLength.append(len(x)) #get the length of each args elements
    maxLength = max(binaryLength) #get the max length among args elements
    for x in args:
        if len(set(binaryLength)) != 1: #checks if all elements have the same length
            delta = maxLength - len(x) - 1 #if not so, it adds as many zeros as delta value indicates
            while (delta) >= 0:
                x[:0] = [0]
                delta -= 1
    while i >= -maxLength: #starts the sum from the end.
        for j in args: value += j[i] #get the sum of all the last list element( for each arg)
        value += amount 
        value, amount = check(value) #uses binary sum properties: it returns a value between 0 and 1, and the amount, an integer 
        result.insert(i, value) #inserts the value at the beginning of the list
        i-=1 # needed to iterate the process
        value = 0 #resets the value
    if amount != 0: #At the end, if there's amount it inserts it at the beginning of result list: 
        while amount not in [0,1]: #if is not equal to 0 or 1 converts the int amount in binary number 
            value = amount
            value, amount = check(value)
            result.insert(i, value)
            i-=1
        result.insert(i, amount) #if is equal to 1 inserts it at the start of the list.
    return result #returns the result as list.
\$\endgroup\$
0

3 Answers 3

3
\$\begingroup\$

You've got way too much code. You are not using the built-in tools Python provides to solve this problem, making your job much, much harder.


In your check(value) function, you are checking:

if value % 2 == 0:
    # ...
elif value % 2 != 0:
    # ...

If value % 2 == 0 is False, then value % 2 != 0 is guaranteed to be True. There is no need for the elif ...:; you could simply use an else: clause.

In both cases, you assign amount = int( ... / 2). Python has built-in integer division operator, //, so these statements could become simply amount = ... // 2. In the second case, because value is odd, you divide value - 1 by two. This "subtract 1" is unnecessary. Using integer division (or dividing and then casting to an integer) will truncate the result to an integer.

Afterwards, in the first case, when value % 2 is zero, you assign value = 0, where as in the second case, when value % 2 is one, you assign value = 1. You could simply assign value = value % 2.

def check(value):
    amount = value // 2
    value = value % 2
    return value, amount

Or slightly shorter:

def check(value):
    return value % 2, value // 2

Or even better, use the built-in function divmod(a,b) which does the same thing. But you will have to swap the variables you assign to, because divmod(a,b) returns the result of the division first, and the modulo remainder second:

amount, value = divmod(value, 2)

In your binary_sum(*args) function, you are given a variable number of lists, and you want to take one element from each list, then take the next element from each list, and then take the next element from each list, and so on. In Python, this is the zip() function. (Note: "zip" is short for "zipper", not zip-compression.)

for addends in zip(*args):
    # ...

Except we have a wrench in the works; you want to start from the end and work towards the front. That is hard. It is easier if each list is reversed(), so starting from the start is starting from what was the end. We can then zip() those reversed() lists together:

for addends in zip(*map(reversed, args)):
    # ...

Except we have another wrench in the works; the lists aren't all the same length, and zip stops when any of the lists runs out of items. You need to add 0's at the start, so they are the same length. Except we've reversed the lists, so we need to add 0's to the end. That's easy. We just need itertools.zip_longest(*args, fillvalue=0) to provide the extra 0's.

from itertools import zip_longest

for addends in zip_longest(*map(reversed, args), fillvalue=0):
    # ...

Now addends is first the 1's column digits, then the 2's column digits, then the 4's column digits, and so on. We can just sum the addends together, along with any carry from the previous column:

digits = []
carry = 0
for addends in zip_longest(*map(reversed, args), fillvalue=0):
    total = sum(addends) + carry
    carry, digit = divmod(total, 2)
    digits.append(digit)

And then, add the carry bits to end once you've run out of columns:

while carry > 0:
    carry, digit = divmod(carry, 2)
    digits.append(digit)

Finally, since we've generated the result in the wrong order, you'll have to reverse it again, so the most significant digit is first.

from itertools import zip_longest

def binary_sum(*args):
    digits = []

    carry = 0
    for addends in zip_longest(*map(reversed, args), fillvalue=0):
        total = sum(addends) + carry
        carry, digit = divmod(total, 2)
        digits.append(digit)

    while carry > 0:
        carry, digit = divmod(carry, 2)
        digits.append(digit)

    return digits[::-1]

A few tests:

>>> binary_sum([1,1,1,0])
[1, 1, 1, 0]
>>> binary_sum([1,1,1,0], [1,0])
[1, 0, 0, 0, 0]
>>> binary_sum([1,1,1,1], [1])
[1, 0, 0, 0, 0]
>>> binary_sum([1,1,1,1], [0,0,0,1])
[1, 0, 0, 0, 0]
>>> binary_sum([1,1,1,1], [1,0,0,0])
[1, 0, 1, 1, 1]
>>> binary_sum([1], [1], [1], [1], [1])
[1, 0, 1]
\$\endgroup\$
2
\$\begingroup\$

A binary sum (any sum, really) only needs four things:

  • The left operand
  • The right operand
  • A variable to store the carry value (bit)
  • A variable to store the output value

You can greatly simplify this problem by moving from right to left—after all, that is how numbers are traditionally summed in any number system (decimal, octal, hex, binary, anything).

Let's start with some of the problems in your code and then look at a better approach:

Variable naming

Some of your variable names don't make sense. For example:

  • value = 0 (what value?)
  • amount = 0 #amount carried over (why not call this carry?)
  • binaryLength = [] #list of all args length (I'm still not quite sure what this means)

There's also the issue of using x in your loops. Is it possible to understand what it represents? Sure. But you use too many xs, is, and js. It's all too much to keep track of. Consider renaming x to arg: for arg in args. There—it certainly reads better.

Functions and their length

Your binary_sum function is monstrous—it's too long and is doing lots of things at once. Years down the line, if you revisit your code, are you sure you will be able to follow what it's doing? I'm personally having trouble following along.

So where do you start? I suggest running through all of your comments and classifying them:

  • Good comments: state why you're doing something and don't explain what you're doing.

  • Bad comments: the code itself is difficult to understand; the comment is there to basically tell the reader what you're doing.

You have a lot of bad comments. Consider splitting binary_sum into different function calls, using informative names that tell the reader what those functions are doing. The outer for and while loops look like good candidates, at first glance.

A simpler approach

Let's take a step back and consider one issue at a time:

  1. We're given two input lists. Okay, but what if they're not of the same length? You seem to have already recognized this. At this point, you should consider writing a generic function that, given a list and a desired length, will pad that list with zeros at the front until the list is of the desired length (assuming the number isn't negative—does the problem state anything about this or two's complement?):
def padWithZeros(num, desiredLength):
   zerosNeeded = desiredLength - len(num)
   return [0] * zerosNeeded + num

If negative numbers do need to be accounted for, then it's just a matter of using [num[0]] * bitsNeeded instead of the hardcoded 0 in [0] * zerosNeeded.

  1. Okay, one problem down. Now let's get the numbers from the command line. Don't throw this into the binary_sum function. Instead, the binary_sum function should take two numbers to add. We'll pass along those numbers from main. Consider using the sys library.
import sys
...
def main():
   num1 = sys.argv[1]
   num2 = sys.argv[2]
   print("{} + {} = {}".format(num1, num2, binary_sum(num1, num2))

Edit: Oversight on my part. This doesn't work because the sys.argv tokens will ignore the list elements.

There. Short and sweet, and it's clear what we're doing. This will be the entry point for the program.

  1. Now let's get to the binary_sum method. We need to pad the shorter number:
def binary_sum(num1, num2):
   if len(num1) < len(num2):
      num1 = padWithZeros(num1, len(num2))
   elif len(num2) < len(num1):
      num2 = padWithZeros(num2, len(num1))

Edit: we can make this (and padWithZeros) even simpler by considering just the difference len(num1) - len(num2). If it's negative, then num1 is shorter than num2, so pad num1 with the negative of that difference. If it's positive, then num1 is longer than num2, so pad num2 with that difference.

What do we do next? Now that we have two lists of equal length, we can begin traversing them using a single iterator/index. Let's express an algorithm: Moving right to left, take the digit from num1 and add it to the digit from num2, plus the carry, and then determine what the corresponding result bit should be as well as what the new carry should be. Repeat until we process the leftmost bit.

We have these possibilities (the last bit is the carry in these computations):

1 + 1 + 1 = 3 (011) = 1 carry 1

1 + 1 + 0 = 2 (10) = 0 carry 1

1 + 0 + 0 = 1 (01) = 1 carry 0

1 + 0 + 1 = 2 (10) = 0 carry 1

0 + 0 + 0 = 0 (00) = 0 carry 0

0 + 0 + 1 = 1 (01) = 1 carry 0

There are two approaches:

  • Straightforward approach: Use a series of if/elif to evaluate the decimal results: 0, 1, 2, or 3.

  • Math trick: the result bit is by definition always the sum modulo 2. The carry bit is always the sum divided by 2.

Of course, you also have to decide if there's going to be any overflow/cutoff. If the carry bit at the very end is a 1, then you should either add a 01 to the front of the result (no overflow) or simply do nothing (overflow, result is inaccurate).

\$\endgroup\$
3
  • \$\begingroup\$ You missed the requirement that it must add two or more binary lists. \$\endgroup\$
    – AJNeufeld
    Jul 5, 2019 at 5:33
  • \$\begingroup\$ Where was that requirement stated? I didn't notice. \$\endgroup\$
    – AleksandrH
    Jul 5, 2019 at 11:07
  • \$\begingroup\$ The docstring of binary_sum \$\endgroup\$
    – AJNeufeld
    Jul 5, 2019 at 13:24
0
\$\begingroup\$

And here is an example of approaching it from the "other" side. Algorithm here would be:

Input: binary numbers: [1, 0], [1, 1, 1]

Output: Sum of inputs as binary number: [1, 0, 1]

Algorithm:

  1. Convert binary to base 10 digit, ex: [1, 1, 1] -> 7, [1, 0] -> 2
  2. Add them: 7 + 2 -> 9
  3. Convert to binary: [1, 0, 0, 1]

Implementation:

  def binary_sum(*numbers):
      stringify = lambda digits: ''.join(map(str, digits))  
      numbers = [stringify(n) for n in numbers] 

      to_base10 = lambda digits: int(digits, 2)
      to_base2 = lambda number: [int(d) for d in bin(number)[2:]] # bin(9) -> '0b1001', thus cut first two chars

      base10_sum = sum([to_base10(n) for n in numbers]) # 1 + 2 step
      return to_base2(base10_sum) # 3 step
\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.