Question：

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

For example,


a =

"11"



b =

"1"



Return

"100"

.

Anwser 1：

class Solution {
public:
    string addBinary(string a, string b) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        string sum = "";
        int alen = a.length() - 1;
        int blen = b.length() - 1;
        int carry = 0;
        while (alen >= 0 || blen >= 0 || carry > 0) {
            int v = carry;
            if (alen >= 0) v += a[alen] - '0';
            if (blen >= 0) v += b[blen] - '0';

            carry = v / 2;
            sum = string(1, ( '0' + (v&1) ) ) + sum; 
            alen--;
            blen--;
        }
        return sum;
    }
};

Anwser 2：

wrong for large and large binary string, such as a = "111111111111111111111111000000000000000000000000000000000000000000111111111"

class Solution {
public:
    int str2num(string str){
        int len = str.length();
        if(len <= 0) return 0;
        
        int sum = 0;
        int base = 2;
        int pow = 1;
        
        for(int i = 1; i <= len; i++){
            int val = str[len - i] - '0';
            if(i == 1){
                sum += val;
            } else {
                pow *= base;
                sum += val * pow;
            }
        }
        return sum;
    }
    
    string num2str(int num){
        if(num == 0 ) return "0";
        
        string str = "";
        
        int mod = num % 2;
        do{
            str = string(1, mod + '0') + str;
            num = num / 2;
            mod = num % 2;
        } while (num > 0);
        
        return str;
    }
    
    string addBinary(string a, string b) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return num2str( str2num(a) + str2num(b) );
    }
};

注意点：

1） 思路是将binary先转化成整数（int， long， ulong， long long等），然后相加（a + b），最后再将整数和转化回binary字符串

2） 对小数据，此方法可行（Judge Small is ok）； 但对大数据，此方法溢出（Judge Large is wrong）

3） 此算法，可以引申为大整数计算问题（大整数加、减、乘、除）