Add Binary

Problem

Given two binary strings a and b, return their sum as a binary string.

Constraints

• 1 <= a.length, b.length <= 104
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

Solution

The problem Add Binary can be solved by implementing a full adder and applying it through string given. In order to increase the execution efficiency, I’ll be using bitwise operators instead of a modulo operator when calculating sum and carry for addition of digits.

Implementation

class Solution
{
  public:
    string addBinary(string a, string b)
    {
        string ret;
        int carry = 0;

        for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--)
        {
            if (i >= 0)
                carry += a[i];
            if (j >= 0)
                carry += b[j];

            ret += (carry & 1) + '0';
            carry = (carry & 2) >> 1;
        }

        if (carry)
            ret += '1';

        reverse(ret.begin(), ret.end());
        return ret;
    }
};