//注意函数是char *类型，需要返回一个指针
char* addBinary(char* a, char* b) {
    int lenA = strlen(a);
    int lenB = strlen(b);
    int len = lenA > lenB ? lenA : lenB;    //以位数较多的数为基准进行补位
    char *sum = (char*)calloc(len + 2, sizeof(char));
    sum[len + 1] = '\0';
    lenA--; lenB--;
    int c = 0;    //c表示余数
    while (lenA >= 0 || lenB >= 0) {
        c += lenA >= 0 ? a[lenA--] - '0' : 0;    //a[i] - '0'可以把a[i]转换为int类型
        c += lenB >= 0 ? b[lenB--] - '0' : 0;
        sum[len--] = c % 2 + '0';
        c /= 2;
    }
    if (!c) return sum + 1;    //eg. int * p则p+1代表指针向后移动size(int),*(p+1)代表取值，*p+1代表p所指的数+1 
    sum[0] = '1';
    return sum;
}

class Solution {  
public:  
    string addBinary(string a, string b) {  
        //二进制字符串相加  
        //思路：直接做加法，考虑合理进位  
      
        //两种判空方法都可以  
        if(a == "0" || a.empty())  
            return b;  
        if(b == "0" || b.length() == 0)  
            return a;  
      
        string result;  
        //i,j是a,b字符串的索引，字符数减1  
        int i = a.length() - 1;  
        int j = b.length() - 1;  
        /* strlen所求是字符串的字节数； length所求是字符串中的字符数,不包括字符串结尾的NULL!! 
        int sizeb = strlen(b); 
        */  
        //aa，bb分别表示实际a[i],b[i]位的值（a,b长度不一定相同）；rem和carry分别表示本位和进位  
        int aa, bb, rem, carry;  
        aa = bb = rem = carry = 0;  
      
        while((i >= 0) || (j >= 0))  
        {  
            //a[i] - '0'可以把a[i]转换为int类型; rem + ‘0’同理  
            //string 数组下标从零开始！！  
            aa = i < 0 ? 0 : a[i] - '0';  
            bb = j < 0 ? 0 : b[j] - '0';  
            rem = (aa + bb + carry)%2;  
            carry = (aa + bb + carry)/2;  
            result.push_back(rem + '0');  
            i--;  
            j--;  
        }  
      
        if(carry == 1)  
            result.push_back('1');  
          
        //result是按照逆序存储的，需要翻转过来  
        reverse(result.begin(), result.end());  
        return result;  
    }  
};