二进制求和
给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。
https://leetcode.cn/problems/add-binary/description/
代码一,尝试使用笨办法,会造成溢出
class Solution {
public:string addBinary(string a, string b) {int len1 = a.length();int len2 = b.length();long long A=0;long long B=0;for(int i=len1-1;i>=0;i--){A +=(a[i] - '0') *pow(2,len1-1-i);}for(int j=len2-1;j>=0;j--){B +=(b[j] - '0')*pow(2,len2-1-j);}long long C=A+B;if(C==0){string c="0";return c;}string c;while(C!=0){int m = C%2; c+=(m+'0');C=C/2;}string reversed_c(c.rbegin(), c.rend());return reversed_c;}
};
注意,对于字符串的反转可以使用:
string reversed_c(c.rbegin(), c.rend());
按照这个思路,先对于ab字符串反转,然后按位相加,最后考虑进位问题,这个思路还是有点问题
看到一个大佬的题解
class Solution {
public:string addBinary(string a, string b) {if (b.size() > a.size()) {return addBinary(b, a); // 这里先确保第一个数不短于第二个数}int m = a.size(), n = b.size(), carry = 0;for (int i = 0; i < m; i++) {if (n - 1 - i < 0) {if (carry == 0) break;} else {carry += b[n - 1 - i] - '0';}carry += a[m - 1 - i] - '0';a[m - 1 - i] = '0' + (carry % 2);carry >>= 1;}return carry ? '1' + a : a;}
};
函数分析:
- 首先进行长度比较,如果
b
的长度大于a
的长度,就交换两个参数的位置,确保第一个参数(这里是a
)不短于第二个参数。这样做是为了在后续的循环中简化处理,因为在处理时是以较长的字符串为基准进行遍历。 - 然后确定两个字符串的长度
m
和n
,以及进位carry
初始值为 0。 - 接着进入循环,循环从长字符串
a
的最后一个字符开始向前遍历。- 如果当前索引对应的位置超出了短字符串
b
的范围,即n - 1 - i < 0
,此时如果进位carry
为 0,则说明没有更多的进位需要处理,可以直接跳出循环。 - 如果当前索引对应的位置在短字符串
b
的范围内,则将短字符串b
对应位置的字符值转换为数字(通过减去字符’0’)累加到进位carry
中。 - 同时,将长字符串
a
对应位置的字符值也转换为数字累加到进位carry
中。 - 然后更新长字符串
a
对应位置的字符为当前进位和的结果对 2 取余后再加上字符’0’,即得到该位置的新二进制值。 - 最后更新进位
carry
为其当前值右移一位,相当于除以 2,以准备下一位的计算。
- 如果当前索引对应的位置超出了短字符串
- 循环结束后,如果进位
carry
不为 0,则在结果字符串a
的前面添加一个字符’1’,表示最高位有进位;否则直接返回a
作为最终的结果字符串。
下面是一种常规思路,上面的思路看不懂可以看下面这个
class Solution {
public:string addBinary(string a, string b) {int al = a.size();int bl = b.size();while(al < bl) //让两个字符串等长,若不等长,在短的字符串前补零,否则之后的操作会超出索引{a = '0' + a;++ al;}while(al > bl){b = '0' + b;++ bl;}for(int j = a.size() - 1; j > 0; -- j) //从后到前遍历所有的位数,同位相加{a[j] = a[j] - '0' + b[j];if(a[j] >= '2') //若大于等于字符‘2’,需要进一{a[j] = (a[j] - '0') % 2 + '0';a[j-1] = a[j-1] + 1;}}a[0] = a[0] - '0' + b[0]; //将ab的第0位相加if(a[0] >= '2') //若大于等于2,需要进一{a[0] = (a[0] - '0') % 2 + '0';a = '1' + a;}return a;}
};
``