67. Add Binary.md

67. Add Binary

思路

题目要求实现多位二进制加法器。可以先考虑先实现一个一位二进制加法器，然后再运用这个一位二进制加法串接成多位的二进制加法，注意不要忘了处理进位。
注意学习如何将char型的vector转成string: string str(vc.begin(), vc.end())

C++

class Solution {
private:
    int bit_add(const int a, const int b, int &cin){ // 一位加法器，cin是进位
        int tmp = a + b + cin;
        cin = tmp / 2;
        return tmp % 2;
    }
public:
    string addBinary(string a, string b){
        vector<char>res;
        int high1  = a.size() - 1, high2 = b.size() - 1, cin = 0, sum;
        while(high1 >= 0 && high2 >= 0){
            sum = bit_add(a[high1--] - '0', b[high2--] - '0', cin);
            res.push_back(sum + '0');
        }
        while(high1 >= 0){
            sum = bit_add(a[high1--] - '0', 0, cin);
            res.push_back(sum + '0');
        }
        while(high2 >= 0){
            sum = bit_add(b[high2--] - '0', 0, cin);
            res.push_back(sum + '0');
        }
        if(cin == 1) res.push_back('1');
        reverse(res.begin(), res.end());
        return string(res.begin(), res.end());
    }
};