二进制求和
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = "11", b = "1"
输出："100"示例 2：
输入：a = "1010", b = "1011"
输出："10101"题目分析 考虑一个最朴素的方法：先将
a
和
b
转化成十进制数，求和后再转化为二进制数。利用 Python 和 Java 自带的高精度运算，我们可以很简单地写出这个程序：
class Solution:
def addBinary(self, a, b) -> str:
return '{0:b}'.format(int(a, 2) + int(b, 2))如果
a
的位数是
n
，
b
的位数为
m
，这个算法的渐进时间复杂度为
O(n+m)
。但是这里非常简单的实现基于 Python 和 Java 本身的高精度功能，在其他的语言中可能并不适用，并且在 Java 中：
如果字符串超过
33
位，不能转化为Integer 如果字符串超过
65
位，不能转化为Long 如果字符串超过
500000001
位，不能转化为BigInteger 因此，为了适用于长度较大的字符串计算，我们应该使用更加健壮的算法。
方法一：模拟 思路和算法
我们可以借鉴「列竖式」的方法，末尾对齐，逐位相加。在十进制的计算中「逢十进一」，二进制中我们需要「逢二进一」。
具体的，我们可以取
n = \max\{ |a|, |b| \}
，循环
n
次，从最低位开始遍历。我们使用一个变量
\rm carry
表示上一个位置的进位，初始值为
0
。记当前位置对其的两个位为
a_i
和
b_i
，则每一位的答案为
({\rm carry} + a_i + b_i) \bmod{2}
，下一位的进位为
\lfloor \frac{{\rm carry} + a_i + b_i}{2} \rfloor
。重复上述步骤，直到数字
a
和
b
的每一位计算完毕。最后如果
\rm carry
的最高位不为
0
，则将最高位添加到计算结果的末尾。
注意，为了让各个位置对齐，你可以先反转这个代表二进制数字的字符串，然后低下标对应低位，高下标对应高位。当然你也可以直接把
a
和
b
中短的那一个补
0
直到和长的那个一样长，然后从高位向低位遍历，对应位置的答案按照顺序存入答案字符串内，最终将答案串反转。这里的代码给出第一种的实现。代码
class Solution {
public:
string addBinary(string a, string b) {
string ans;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int n = max(a.size(), b.size()), carry = 0;
for (size_t i = 0; i < n; ++i) {
carry += i < a.size() ? (a.at(i) == '1') : 0;
carry += i < b.size() ? (b.at(i) == '1') : 0;
ans.push_back((carry % 2) ? '1' : '0');
carry /= 2;
}
if (carry) {
ans.push_back('1');
}
reverse(ans.begin(), ans.end());
return ans;
}
};复杂度分析
假设
n = \max\{ |a|, |b| \}
。
时间复杂度：
O(n)
，这里的时间复杂度来源于顺序遍历
a
和
b
。 空间复杂度：
O(1)
，除去答案所占用的空间，这里使用了常数个临时变量。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2023-12-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读