剑指 Offer II 002 二进制加法

题目： 给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = “11”, b = “10”
输出: “101”

示例 2:

输入: a = “1010”, b = “1011”
输出: “10101”

思路：

两个二进制数相加，创建进位变量为carry，初始化为0，表示没有进位
i和j分别从a和b字符串的最后一位开始遍历，while循环中，当a或者b没有遍历完，或者还有进位时继续
digitA和digitB分别用来存放当前遍历到的a和b的数值，由于a和b不一定是等长的，
因此这样写可以对前边不够的位置补0的操作，最后sum相加得到当前位的值，
carry用来判断是不是有定位，所以直接除2
如果当前的sum没有定位直接复制存到result数组中，如果有定位，那么减去2再存放
最后转换为字符串存放到result，由于这么存的是正向的，而我是反向计算的
因此最后反转字符串得到结果

class Solution {
public:
	string track(string& a,string& b) {
		string result;
		int carry = 0;
		int i = a.size() - 1;
		int j = b.size() - 1;
		while (i >= 0 || j >= 0 || carry == 1) {
			int digitA = i >= 0 ? a[i] - '0' : 0;
			int digitB = j >= 0 ? b[j] - '0' : 0;
			int sum = digitA + digitB + carry;
			carry = sum / 2;//这里如果有进位那就是1，没有就是0
			sum = sum >= 2 ? sum - 2 : sum;
			result += to_string(sum);
			i--;
			j--;
		}
		reverse(result.begin(), result.end());
		return result;
	}
};

int main() {
	string a = "11";
	string b = "10";
	Solution ss;
	cout << ss.track(a,b) << endl;

	//cout << typeid (a[0] - '0').name() << endl;//int类型
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31