# 67. Add Binary

## 1.問題

* 給兩個字串, 回傳他們的總和

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNbfaAKz0WhJWb-rltV%2F-LNc1bRV_IkMgA8qxSOv%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-30%20%E4%B8%8A%E5%8D%889.14.08.png?alt=media\&token=9999693c-6317-43e3-8dcb-0c93df499e2b)

## 2.想法

* 提問: 確定是在第一個元素還是最末個元素+ 1
* function header, parameter
* test input
* 說明想法&#x20;
  * 由於字串的索引是由左到右, 但是bit的排列是由右到左, 因此需要先對input string做reverse, 得到結果後再做一次reverse
* 測試計算複雜度

## 3.程式碼

```
class Solution {
public:
    string addBinary(string a, string b) {
        int index = 0, carry = 0, sum = 0, i =0;
        string res = "";
        
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        
        while(index < a.length() && index < b.length()) {
            sum = int(a[index] - '0') + int(b[index] - '0') + carry;
            res.push_back(char((sum % 2) + '0'));
            carry = sum / 2;
            ++index;
        }
        
        if (index < a.length()) {
            for (i = index; i < a.length(); i++) {
                sum = int(a[i] - '0') + carry;
                res.push_back(char((sum % 2) + '0'));
                carry = sum / 2;
            }
        }
        
        if (index < b.length()) {
            for (i = index; i < b.length(); i++) {
                sum = int(b[i] - '0') + carry;
                res.push_back(char((sum % 2) + '0'));
                carry = sum / 2;
            }
        }
        
        if (carry) {
            res.push_back(char(carry + '0'));
        }
        
        reverse(res.begin(), res.end());
        
        return res;
    }
};
```
