# 【LeetCode】 67. Add Binary

## Description
> 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`.

> 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`或`0`。

> 限制：
> * 每個字串只包含`0`或`1`的字元。
> * `1 <= a.length`, `b.length <= 10^4`
> * 每個字串除了`"0"`以外，不會有零在最前面的情況。

## Example:

Example 1:

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


Example 2:

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

## Solution

* 由限制條件第二點來看，可以知道這是一題大數運算的題目。
* 只是從一般的大數加法改為二進制，其他概念都一模一樣。
* 從最低位元相加，加完之後如果大於一，就減二並進位，一路加到最高位元。
* 要注意輸入是`string`，因此取單個位元是`char`而不是`int`。
* 最後要注意最高位元的進位會出現錯誤，要先插入一個`0`在最前面才可以正常執行。

### Code

class Solution {
public:
    string addBinary(string a, string b) {
        if(a.length() < b.length()) 
            return addBinary(b, a);
        
        for(int i = 0; i < a.length(); i++)
        {
            if(i < b.length())
                a[a.length() - i - 1] += b[b.length() - i - 1] - '0';
            
            if(i == a.length() - 1)
                if(a[0] > '1')
                    a.insert(a.begin(), '0');
            while(a[a.length() - i - 1] > '1')
            {
                a[a.length() - i - 1] -= 2;
                a[a.length() - i - 2] += 1;
            }
        }
        return a;
    }
};

###### tags: `LeetCode` `C++`