---
# System prepended metadata

title: Leetcode 67. Add Binary (C語言)

---

# Leetcode 67. Add Binary (C語言)
- 題目
  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.
- 範例
  Input: a = "11", b = "1"
  Output: "100"

```c=
char * addBinary(char * a, char * b){
    int la=strlen(a),lb=strlen(b);
    int lc=la>lb? la:lb;
    char* c=(char*)malloc((lc+1));
    c[lc]='\0';
    int i,carry=0;
    for(i=0;i<lc;i++){
        if(la)carry+=a[--la]-'0';
        if(lb)carry+=b[--lb]-'0';
        c[lc-1-i]=(carry&1)+'0';
        carry>>=1;        
    }
    if(carry==1){
        c=(char*)realloc(c,lc+2);
        for(i=lc;i>=0;i--){
            c[i+1]=c[i];
        }
        c[0]='1';
    }
    return c;
}
```
思路:以carry為主來批次計算
```
    carry   110
    a        11
+   b         1
----------------
            100
```
la,lb為string a,b的個別長度,lc即c之長度(取a,b大者)
c就動態宣告lc+1格,其中char bit=1,sizeof(char)可省,且要留多一格放\0(結尾字元)
當中carry&1與carry>>=1什麼意思?
carry&1即把carry與1在二進制下做and運算(皆為1才=1,其他=0)，
以範例跑第一輪計算時carry=a最右bit+b最右bit=2 
即carry=2(十進位)=10(二進位)
```
carry        10
&             1      //1&0=0
-----------------
c[lc-1-i]=    0

carry        10 
>>                  //即向右平移
----------------
              1
```
如果for跑完carry還=1代表還要進位，但是宣告的格子數不夠了就要realloc更大的空間。
(也可以一開始就宣告多一格，但是如果沒有進位會造成空間浪費，這是時間與空間的選擇)