Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
二进制数相加，并且保存在string中，要注意的是如何将string和int之间互相转换，并且每位相加时，会有进位的可能，会影响之后相加的结果。而且两个输入string的长度也可能会不同。这时我们需要新建一个string，它的长度是两条输入string中的较大的那个，并且把较短的那个输入string通过在开头加字符‘0’来补的较大的那个长度。这时候我们逐个从两个string的末尾开始取出字符，然后转为数字，想加，如果大于等于2，则标记进位标志carry，并且给新string加入一个字符‘0’。代码如下：
解法一：
class Solution {
public:
string addBinary(string a, string b) {
string res;
int na = a.size();
int nb = b.size();
int n = max(na, nb);
bool carry = false;
if (na > nb) {
for (int i = ; i < na - nb; ++i) b.insert(b.begin(), '');
}
else if (na < nb) {
for (int i = ; i < nb - na; ++i) a.insert(a.begin(), '');
}
for (int i = n - ; i >= ; --i) {
int tmp = ;
if (carry) tmp = (a[i] - '') + (b[i] - '') + ;
else tmp = (a[i] - '') + (b[i] - '');
if (tmp == ) {
res.insert(res.begin(), '');
carry = false;
}
else if (tmp == ) {
res.insert(res.begin(), '');
carry = false;
}
else if (tmp == ) {
res.insert(res.begin(), '');
carry = true;
}
else if (tmp == ) {
res.insert(res.begin(), '');
carry = true;
}
}
if (carry) res.insert(res.begin(), '');
return res;
}
};
下面这种写法又巧妙又简洁，用了两个指针分别指向a和b的末尾，然后每次取出一个字符，转为数字，若无法取出字符则按0处理，然后定义进位carry，初始化为0，将三者加起来，对2取余即为当前位的数字，对2取商即为当前进位的值，记得最后还要判断下carry，如果为1的话，要在结果最前面加上一个1，参见代码如下：
解法二：
class Solution {
public:
string addBinary(string a, string b) {
string res = "";
int m = a.size() - , n = b.size() - , carry = ;
while (m >= || n >= ) {
int p = m >= ? a[m--] - '' : ;
int q = n >= ? b[n--] - '' : ;
int sum = p + q + carry;
res = to_string(sum % ) + res;
carry = sum / ;
}
return carry == ? "" + res : res;
}
};
参考资料：