How to Add Binary String in C/C++?

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

For example,
a = “11”
b = “1”
Return “100”.

It looks easy however may not seem so: https://leetcode.com/problems/add-binary/

If the given binary string is limited, then we can first convert them to base 10, add them and convert the sum back to binary. The following just demonstrates the idea (it is not an accepted solution for this puzzle).

class Solution {
public:
    int convertToBase10(string a) {
        int r = 0;
        for (int i = 0; i < a.length(); i ++) {
            r = r * 2 + (a[i] - '0');
        }
        return r;
    }

    string convertToBase2(int x) {
        if (x == 0) {
            return "0";
        }
        string r = "";
        while (x) {
            r = (char)(48 + x % 2) + r;
            x /= 2;
        }
        return r;
    }

    string addBinary(string a, string b) {
        int aa = convertToBase10(a);
        int bb = convertToBase10(b);
        return convertToBase2(aa + bb);
    }
};

When converting to base 10, integers will overflow for large binary strings.

O(n)

The solution is to add digit by digit from the end of the both string, we need to carry the ‘1’s to the next iteration. The following adds the sum in place meaning that there is no extra space (local loop variables are not counted since they most-likely are stored using registers).

class Solution {
public:
    string addBinary(string a, string b) {
        // get the longer string
        string rr = a.length() >= b.length() ? a : b;
        string aa = rr == a ? b : a;
        int r = rr.length() - 1;
        int carry = 0;
        for (int i = aa.length() - 1; i >= 0; -- i) {
            // add aa[i] to rr[r]
            int x = aa[i] - '0';
            int y = rr[r] - '0';
            int result = x + y + carry;
            rr[r -- ] = (result % 2 + '0');
            carry = result / 2;
        }
        // carry over remaining.
        while (r >= 0 && carry) {
            int x = rr[r] - '0';
            int result = x + carry;
            rr[r -- ] = (result % 2 + '0');
            carry = result / 2;
        }
        if (carry) {
            rr = '1' + rr;
        }
        return rr;
    }
};

This can be further optimized to a much concise version (most voted answer on leetcode):

class Solution {
public:
    string addBinary(string a, string b) {
        string s = "";   
        int c = 0, i = a.size() - 1, j = b.size() - 1;
        while(i >= 0 || j >= 0 || c == 1)
        {
            c += i >= 0 ? a[i --] - '0' : 0;
            c += j >= 0 ? b[j --] - '0' : 0;
            s = char(c % 2 + '0') + s;
            c /= 2;
        }    
        return s;
    }
};

i and j are pointing to the end of the both string at the begining, they start to move backwards at each iteration. The space complexity is O(n) since we need to allocate another string to add the results digits by digits.

–EOF (The Ultimate Computing & Technology Blog) —