Add Binary
Question：
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
Anwser 1：
[cpp]
class Solution {
public:
string addBinary(string a, string b) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
string sum = "";
int alen = a.length() - 1;
int blen = b.length() - 1;
int carry = 0;
while (alen >= 0 || blen >= 0 || carry > 0) {
int v = carry;
if (alen >= 0) v += a[alen] - '0';
if (blen >= 0) v += b[blen] - '0';
carry = v / 2;
sum = string(1, ( '0' + (v&1) ) ) + sum;
alen--;
blen--;
}
return sum;
}
};
Anwser 2： wrong for large and large binary string, such as a = "111111111111111111111111000000000000000000000000000000000000000000111111111"
[cpp]
class Solution {
public:
int str2num(string str){
int len = str.length();
if(len <= 0) return 0;
int sum = 0;
int base = 2;
int pow = 1;
for(int i = 1; i <= len; i++){
int val = str[len - i] - '0';
if(i == 1){
sum += val;
} else {
pow *= base;
sum += val * pow;
}
}
return sum;
}
string num2str(int num){
if(num == 0 ) return "0";
string str = "";
int mod = num % 2;
do{
str = string(1, mod + '0') + str;
num = num / 2;
mod = num % 2;
} while (num > 0);
return str;
}
string addBinary(string a, string b) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return num2str( str2num(a) + str2num(b) );
}
};
注意点：
1） 思路是将binary先转化成整数（int， long， ulong， long long等），然后相加（a + b），最后再将整数和转化回binary字符串
2） 对小数据，此方法可行（Judge Small is ok）； 但对大数据，此方法溢出（Judge Large is wrong）
3） 此算法，可以引申为大整数计算问题（大整数加、减、乘、除）
补充：软件开发 , C++ ,
