67 Add Binary

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

For example, a ="11" b ="1" Return"100".

Notes:

• Pointer for non-copy, but allows us to denote max and min.

• Start from the end of the string, and iterate forward. Maintain a carry bit to, to effectively produce a 9 bit adder.

• Reverse string, since we started from the other end.

• Time: O(n + n/2), O(1) space.

string addBinary(string &a, string &b) {
    string *bot, *top;
    if (a.length() > b.length()) {
        top = &a;
        bot = &b;
    }
    else {
        top = &b;
        bot = &a;
    }

    int iter_top = top->length() - 1;
    int iter_bot = bot->length() - 1;

    char carry = '0';
    string final;
    final.reserve(top->length());

    while (iter_bot >= 0) {
        if (top->at(iter_top) == '1' && bot->at(iter_bot) == '1') {
            if (carry == '1') {
                carry = '1';
                final += '1';
            }
            else {
                carry = '1';
                final += '0';
            }
        }
        else if (top->at(iter_top) == '0' && bot->at(iter_bot) == '1' ||
            top->at(iter_top) == '1' && bot->at(iter_bot) == '0') {
            if (carry == '1') {
                carry = '1';
                final += '0';
            }
            else {
                carry = '0';
                final += '1';
            }
        }
        else if (top->at(iter_top) == '0' && bot->at(iter_bot) == '0') {
            if (carry == '1') {
                carry = '0';
                final += '1';
            }
            else {
                carry = '0';
                final += '0';
            }
        }
        iter_bot--; iter_top--;
    }

    while (iter_top >= 0) {
        if (carry == '1' && top->at(iter_top) == '1') {
            carry = '1';
            final += '0';
        }
        else if (carry == '0' && top->at(iter_top) == '1') {
            carry = '0';
            final += '1';
        }
        else if (carry == '0' && top->at(iter_top) == '0') {
            carry = '0';
            final += '0';
        }
        else if (carry == '1' && top->at(iter_top) == '0') {
            carry = '0';
            final += '1';
        }
        iter_top--;
    }

    if (carry == '1') final += '1';
    reverse(final.begin(), final.end());
    return final;
}