Sum of two binary strings (Add Binary)

Given two binary strings, return their sum (also a binary string).
INPUT: a = “11”, b = “1”
OUTPUT: “100”

Thoughts:
Think about how we do binary addition. We first align the two numbers to the right (or padding 0 to the left for small number). Here, we convert b into “01”. Then we do additions from right to left, digit by digit. We also need to take care of carries. We can actually separate these two process: we do addition first, without thinking about carries; we then only do carries. In the end we add up those two results together. As in the example, we first do the summation of a = “11” and b = “01” and we get “10”; we then do the carries, we get “01”, as the carries will be applied to the next left digit, we shift it to left for one bit, i.e., we have “010”. We know need to calculate “10” + “010”, how we can do that? Well, we just recursively go through the process described before. When do we stop? What is the base case? When there’s no carries anymore! At that time, we just return whatever the sum is. We can mimic this process using string manipulations.

Code (Java):

public class Solution {
    public String addBinary(String a, String b) {
        if(b.indexOf('1') == -1)
            return a.indexOf('1') == -1 ? a : a.substring(a.indexOf('1'));
        int diff = Math.abs(a.length() - b.length());
        if(a.length() > b.length()) {
            for(int i = 0; i < diff; ++i)
                b = '0' + b;
        } else {
            for(int i = 0; i < diff; ++i)
                a = '0' + a;
        }
        
        String sum = new String();
        String carry = "0";
        for(int i = a.length() - 1; i >= 0; --i) {
            if( (a.charAt(i) == '1' && b.charAt(i) == '1') ||
                (a.charAt(i) == '0' && b.charAt(i) == '0'))
                sum = '0' + sum;
            else
                sum = '1' + sum;
            if (a.charAt(i) == '1' && b.charAt(i) == '1')
                carry = '1' + carry;
            else
                carry = '0' + carry;
        }
        return addBinary(sum, carry);
    }
}

Code (C++):

class Solution {
public:
    string addBinary(string a, string b) {
        if(b.find_first_of('1') == string::npos)
            return a.find_first_of('1') == string::npos ? 
                    a : a.substr(a.find_first_of('1'));
        int diff = abs((int)a.size() - (int)b.size());
        if(a.size() > b.size()) {
            for(int i = 0; i < diff; ++i)
                b = '0' + b;
        } else {
            for(int i = 0; i < diff; ++i)
                a = '0' + a;
        }
        
        string sum;
        string carry = "0";
        for(int i = a.size() - 1; i >= 0; --i) {
            if( (a.at(i) == '1' && b.at(i) == '1') ||
                (a.at(i) == '0' && b.at(i) == '0'))
                sum = '0' + sum;
            else
                sum = '1' + sum;
            if (a.at(i) == '1' && b.at(i) == '1')
                carry = '1' + carry;
            else
                carry = '0' + carry;
        }
        return addBinary(sum, carry);
        
    }
};
Advertisements

4 Comments (+add yours?)

  1. Gui
    Jul 20, 2012 @ 04:23:29

    In you Java code, at line 10 and 12, that says b = ‘0’ + b. I think there is a flaw, you know, in Java, String object can not be modify directly in this way. Right?

    Reply

    • Runhe Tian
      Jul 20, 2012 @ 11:52:31

      Notice that I don’t modify b in any way. Java evaluate the expression ‘0’+b into a constant string then assign the reference of that string to b.

      Reply

  2. Ali
    Oct 16, 2012 @ 02:29:42

    But you aren’t stopping the loop right ? like checking if theres no carry then breaking the recursion

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: