0. 题目

Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.

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

Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
Constraints:
Each string consists only of '0' or '1' characters.
1 <= a.length, b.length <= 10^4
Each string is either "0" or doesn't contain any leading zero.

1. c++版本

 string addBinary(string a, string b) {
        if (a.size() < b.size())
           swap(a, b);
        int i, j, curr, flag=0;
        string result;
        for(i=a.size()-1, j=b.size()-1; i>=0; ) {
            while(j>=0) {
                curr = (a[i] - '0') + (b[j] - '0') + flag;
                flag = curr/2;
                result = to_string(curr%2) + result;
                i--; j--;
            }
            if (i>=0) {
                curr = (a[i]-'0') + flag;
                flag = curr/2;
                result = to_string(curr%2) + result;
                i--;
            }
        }
        if (flag == 1)
           result = "1" + result;
        return result;
    }

优化版本，当处理完string b之后，如果flag为0，此时就可以直接将a的substr直接拼在result里面

class Solution {
public:
    string addBinary(string a, string b) {
        if (a.size() < b.size())
           swap(a, b);
        int i, j, curr, flag=0;
        string result;
        for(i=a.size()-1, j=b.size()-1; i>=0; ) {
            while(j>=0) {
                curr = (a[i] - '0') + (b[j] - '0') + flag;
                flag = curr/2;
                result = to_string(curr%2) + result;
                i--; j--;
            }
            if (i>=0) {
                if (flag == 0) {
                    result = a.substr(0, i+1) + result;
                    return result;
                    
                }
                else {
                    curr = (a[i]-'0') + flag;
                    flag = curr/2;
                    result = to_string(curr%2) + result;
                    i--;
                }
            }
        }
        if (flag == 1)
           result = "1" + result;
        return result;
    }
};

最短c++: https://leetcode.com/problems/add-binary/discuss/24475/Short-code-by-c%2B%2B

    string addBinary(string a, string b) {
        string result = "";
        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;
            result = to_string(c%2) + result;
            c = c/2;
        }
        return result;
    }

2. python版本

 if len(a) < len(b):
            a, b = b, a
        i = len(a)-1
        j = len(b)-1
        curr = flag = 0
        result = ''
        while (i>=0 and j>=0):
            curr = int(a[i]) + int(b[j]) + flag
            flag = curr/2
            result = str(curr%2) + result
            i = i - 1
            j = j - 1
        while i>=0:
            curr = int(a[i]) + flag;
            flag = curr/2
            result = str(curr%2) + result
            i = i - 1

        if flag == 1:
            result = "1" + result
        return result

优化版本, 这和python语言特性有关，可以先将string转化为list，然后再处理。虽然python没有i--操作，但是转化为list，之后会有pop操作，相当于list

   def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        curr = 0
        result = ''
        a = list(a)
        b = list(b)
        while a or b or curr:
            if a:
                curr += int(a.pop())
            if b:
                curr += int(b.pop())
            result = str(curr%2) + result
            curr = curr/2
        return result