每日算法之四十六：Add Binary（二进制字符创相加）

二进制字符创相加，通过进位的方式逐位考虑。也可以把相加的过程抽象成一个函数。

Given two binary strings, return their sum (also a binary string).

For example,

a = "11"

b = "1"

Return "100".

方法一：

class Solution {
public:
        string addBinary(string a, string b) {
        int a_len=a.length();
        int b_len=b.length();
        if(a_len==0)
            return b;
        if(b_len==0)
            return a;
        string result="";
        int max=(a_len>b_len?a_len:b_len);
        int j=a_len-1;
        int k=b_len-1;
        int sum=0;
        for(int i=0;i<max;i++,j--,k--)
        {
            if(j>=0)
            {
                sum+=a[j]-'0';
            }
            if(k>=0)
                sum+=b[k]-'0';
            result=(char)((sum&1)+'0')+result;
            sum=sum>>1;
        }
        if(sum>0)
            result='1'+result;
        return result;
        }
};

方法二：

// add a and b and carry, return a + b + carry.
// carry will be updated when add char.
char add_char(char a, char b, char &c)
{
    if (a == b && a == '1')
    {
        char ret = c;
        c = '1';
        return ret;
    }
    else if (a == b && a == '0')
    {
        char ret = c;
        c = '0';
        return ret;
    }
    else
    {
        if (c == '1')
        {
            return '0';
        }
        else
        {
            return '1';
        }
    }
}
 
// Given two binary strings, return their sum (also a binary string).
// For example,
// a = "11"
// b = "1"
// Return "100".
string add_binary(string a, string b) 
{
    // Init result with the longest string.
    string result = a.size() > b.size() ? a : b;
    // Init carry with '0'.
    char carry = '0';
    
    const char *pa = a.data() + a.size() - 1;
    const char *pb = b.data() + b.size() - 1;
    string::iterator pc = result.begin() + result.size() - 1;
    
    while (pa != a.data() - 1 || pb != b.data() - 1)
    {
        if (pa == a.data() - 1)
        {
            *pc-- = add_char('0', *pb--, carry);
        }
        else if (pb == b.data() - 1)
        {
            *pc-- = add_char(*pa--, '0', carry);
        }
        else
        {
            *pc-- = add_char(*pa--, *pb--, carry);
        }
    }
    
    if (carry == '1')
    {
        return "1" + result;
    }
    
    return result;
}