Efficient solution for adding Binary Strings

Question

Problem: Given two binary strings, return their sum (also a binary string).

For example, add_binary_strings('11', '1') should return '100'.

Implementation 1:

def addBinary(a, b):
    """
    :type a: str
    :type b: str
    :rtype: str
    """
    a = a[::-1]
    b = b[::-1]
    carry = '0'
    result = ''

    # Pad the strings to make their size equal
    if len(a) < len(b):
        for i in range(len(a), len(b)):
            a += '0'
    elif len(a) > len(b):
        for i in range(len(b), len(a)):
            b += '0'

    n = len(a)
    carry = 0
    s = ''
    for i in range(n):
        l, m, c = int(a[i]), int(b[i]), carry
        s += str(l^m^c) # sum is XOR of three bits
        carry = (l&m) | (m&c) | (c&l) # carry is pairwise AND of three bits

    if carry == 1:
        s += str(carry)

    return s[::-1]

Implementation 2

def addBinary(self, a, b):
    """
    :type a: str
    :type b: str
    :rtype: str
    """
    a = a[::-1]
    b = b[::-1]
    m = min(len(a), len(b))
    carry = '0'
    result = ''

    for i in range(m):
        r, carry = add_digit(a[i], b[i], carry=carry)
        result += r

    larger, shorter = a, b
    if len(a) < len(b):
        larger, shorter = b, a

    for i in range(len(shorter), len(larger)):
        if carry != '0':
            r, carry = add_digit(larger[i], carry)
            result += r
        else:
            result += larger[i]

    if carry != '0':
        result += carry

    return result[::-1]

def add_digit(digit1, digit2, carry=None):
    if carry is None:
        carry = '0'

    d1, d2, c = int(digit1), int(digit2), int(carry)
    s = d1 + d2 + c
    return str(s%2), str(s//2)

According to an online judge, the performance for the first implementation is better in terms of time. However, I find the first implementation to be a bit too verbose because I always have to make both the strings of the same size.

What is the time complexity of creating a new string of length n? I would like to know what are the corresponding space and time complexities for these implementations and how can I improve on the code.
What are the tradeoffs between the implementations and when should I not use a particular one of them? For example, I should use the 2nd implementation in favour of the 1st when the size of input strings will differ considerably on the general.

Appending to a string is very inefficiant in Python. And frankly i think that something like bin(int(a, 2) + int(b, 2))[2:] will be faster, more readable and more pythonic. — Klaus D.
– Klaus D., Commented Sep 26, 2017 at 4:59
What is the purpose of using the strings here? They just won't be efficient. Or you just want to see the fastest way to sum binary numbers? — Grigory
– Grigory, Commented Sep 26, 2017 at 8:50
@Grigoriy I agree with you about the inefficiency of strings here. However, the input is constrained to be of the type string and so should be the return value. — Kshitij Saraogi
– Kshitij Saraogi, Commented Sep 26, 2017 at 10:28
@KshitijSaraogi if the input and output are strings it doesn't mean that you must work with strings to do calculations ;) So i still can't understand why you want to do this using strings here. Maybe there are some extra details about your task, that we need to know?) — Grigory
– Grigory, Commented Sep 26, 2017 at 11:33

Adrian Mole · Accepted Answer · 2020-05-09 16:53:57Z

3

If problem is defined as:

Given two binary strings, return their sum (also a binary string). For example, add_binary_strings('11', '1') should return '100'.

Then you just need to do:

def add_binary_strings(a, b):
    return '{:b}'.format(int(a,2) + int(b,2))
print(add_binary_strings('11', '1'))

This solution should be faster than the one you found.

edited May 9, 2020 at 16:53

Adrian Mole

52.1k193 gold badges61 silver badges101 bronze badges

answered Sep 26, 2017 at 4:52

Grigory

6771 gold badge4 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Kshitij Saraogi Over a year ago

Agreed ! This is definitely faster than either of my solution. But I don't want the fastest solution. I want to make my solutions more efficient. ;)

SeF · Accepted Answer · 2020-04-27 16:52:43Z

0

I would modify your solution to:

def addBinary(a, b):

    max_len = max(len(a), len(b))

    a = a.zfill(max_len)
    b = b.zfill(max_len)
    c = ''
    reminder = 0

    for i in range(max_len-1, -1, -1):
        c = str((int(a[i]) + int(b[i]) + reminder) % 2) + c
        reminder = 1 if int(a[i]) + int(b[i])+ reminder > 1 else 0

    c = str(reminder) + c

    return c

this would save some inversions compared yo your solutions, which would save a bit of time (ouch!). You can omit the last assignment to c if you do not want to increase the length of the output, though you may overflow!

answered Apr 27, 2020 at 16:52

SeF

4,2993 gold badges32 silver badges44 bronze badges

Collectives™ on Stack Overflow

Efficient solution for adding Binary Strings

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related