# 67-Add binary
###### tags: `Easy`
* Question:https://leetcode.com/problems/add-binary/
* Hint:
1. 如何處理字串轉成數字運算?將a,b轉為數字，相加後再轉回bits，但題目給的string長度轉成int時會超過int max，所以這個方法不能用
2. 如何直接對字串進行處理?
從低位元加到高位元(*字串長度要從高到低)，一個位元逐一相加，字元做運算都要先轉int，而字元(ASCII code)轉到int要減48才會是字元的數值，故要減'0'(ASCII Code:48)
4. 如何處理進位?
有進位就放到carry(residual)

Soultion by 永凱:
一個一個算，一個一個進位

class Solution {
public:
    string addBinary(string a, string b) {
        int largerStringSize = a.size() > b.size() ? a.size() : b.size();
        int residual = 0;
        vector<char> charArray(largerStringSize + 1);
        for (int i = 1; i <= largerStringSize; i++){
            int a_int = a.size() >= i ? a[a.size()-i]-'0':0;
            int b_int = b.size() >= i ? b[b.size()-i]-'0':0;
            int sum = a_int + b_int + residual;
            residual = sum  / 2;
            char num = '0' + sum % 2;
            charArray[largerStringSize+1-i] = num;
        }
//為了加最後一次的residual
        if (residual > 0){
            charArray[0] = char (residual + '0');
        }
//取得字串  最後一位是否進位會影響字串的頭尾      
        std::string str(charArray.begin() + (1-residual), charArray.end());
        return str;
    }     
};

## Simple Solution

class Solution {
public:
    string addBinary(string a, string b) {
        string res;
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        while(i >= 0 || j >= 0){
            int sum = carry;
            if(i >= 0) sum += a[i--] - '0';
            if(j >= 0) sum += b[j--] - '0';
            carry = sum > 1 ? 1 : 0;
            res += to_string(sum % 2);
        }
        //最後一位加完的進位也要記得考慮
        if(carry) res += to_string(carry);
        reverse(res.begin(), res.end());
        return res;
    }
};