Add Binary

Posted by Bill on March 11, 2023

Add Binary

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

1
2
3
4
5
6
7
8
 Example 1:

 Input: a = "11", b = "1"
 Output: "100"
 Example 2:

 Input: a = "1010", b = "1011"
 Output: "10101"

C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
string addBinary(string a, string b) {
    int carry = 0;
    auto a_iter = a.rbegin();
    auto b_iter = b.rbegin();
    stack<char> myStack;
    while (a_iter != a.rend() || b_iter != b.rend() || carry != 0) {
        int val = 0;
        if (a_iter != a.rend() && b_iter != b.rend()) {
            val = (*a_iter - '0') + (*b_iter - '0') + carry;
        } else if (a_iter != a.rend() && b_iter == b.rend()) {
            val = (*a_iter - '0')  + carry;
        } else if (a_iter == a.rend() && b_iter != b.rend()) {
            val = (*b_iter - '0')  + carry;
        } else {
            val = carry;
        }
        carry = val / 2;
        myStack.push(val % 2 + '0');
        if (a_iter != a.rend()) {
            a_iter++;
        }
        if (b_iter != b.rend()) {
            b_iter++;
        }
    }
    string ret;
    while (!myStack.empty()) {
        ret.push_back(myStack.top());
        myStack.pop();
    }
    return ret;
}