我是靠谱客的博主 潇洒小馒头,这篇文章主要介绍67. 二进制求和c++(四种方法),现在分享给大家,希望可以做个参考。

题目:给定两个二进制字符串,返回他们的和(用二进制表示)。输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = “11”, b = “1” 输出: “100”

示例 2:

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

思路:

1、首先让两个字符串等长,若不等长,在短的字符串前补零

2、然后从后到前遍历所有的位数,同位相加,记得加上进位,二进制数相加结果与异或结果相同,所以用异或代替

3、判断相加后的值,若大于等于2,下一位需要进一

4、最后一次加法(异或)结束后,判断有没有进位。即 最高位的进位单独处理

复制代码
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
class Solution { public: string addBinary(string a, string b) { int a_len = a.size(); int b_len = b.size(); if(a_len < b_len){ //保证b字符串较短 swap(a, b); swap(a_len, b_len); } if(a_len != b_len) //如果a b字符串长度不同,则把短的字符串用0补齐 b.insert(0, a_len- b_len, '0'); int carry = 0, cur = 0; string result; for(int i = a_len - 1; i >= 0; --i){ int ia = a[i] - '0'; int ib = b[i] - '0'; cur = ia ^ ib ^ carry; // 二进制数相加结果与异或结果相同 if(ia + ib + carry >= 2) carry = 1; //判断有无进位 else carry = 0; result.insert(0, 1, cur + '0'); //用insert加在字符串最前面,也可以用 += 加在后面,最后用reserve函数反转 } if(carry) // 最高位的进位单独处理 result.insert(0, 1, carry + '0'); return result; } };

下面这个是不用补0,用reverse()函数反转来实现的

复制代码
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
class Solution { public: string addBinary(string a, string b) { int a_size=a.size(),b_size=b.size(); if (a_size<b_size){ //保证b的长度为小的 swap(a,b); swap(a_size,b_size); } reverse(a.begin(),a.end()); //反转,方便我从下标0开始计算。而不补0了 reverse(b.begin(),b.end()); string answer=""; int carry=0,sum; for (int i=0;i<b_size;++i){ //处理两个字符串共同长的那部分字符 sum=a[i]-'0'+b[i]-'0'+carry; answer=answer+char(sum%2+'0'); carry=sum/2; } for (int i=b_size;i<a_size;++i){ //处理长一点字符串多出来的那部分字符 sum=carry+a[i]-'0'; answer=answer+char(sum%2+'0'); carry=sum/2; } if (carry==1) answer=answer+'1'; reverse(answer.begin(),answer.end()); return answer; } };

--------------2019.12.31更新---------------

看到自己的函数库里面有字符串的加法函数,想到这也是一个字符串加法呀,不过是二进制的。只要把代码中十进制的部分改成二进制就好了。十进制的见下面链接

简单常用的一些函数,个人的函数库 : https://blog.csdn.net/qq_43657442/article/details/97796395

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
string addStrings(string num1, string num2) { string str; int cur = 0, i = num1.size()-1, j = num2.size()-1; //从字符串的末尾(我们数字的末位)开始加,直到加到最高位加完 while (i >= 0 || j >= 0 || cur != 0) { //判断是否加完,其实根据||的计算方式,cur!=0只会在把两个字符串的元素遍历完才会判断。一般来讲只有两个字符串相等且加了有进位的才会判断到这儿 if (i >= 0) cur += num1[i--] - '0'; //判断字符串1是否所有元素加完 if (j >= 0) cur += num2[j--] - '0'; //判断字符串2是否所有元素加完 str += to_string (cur % 2); //取低位变成字符加到字符串中 cur /= 2; //判断有无进位 } reverse(str.begin(), str.end()); //把字符串倒置 return str; }

或者

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string addStrings(string num1, string num2) { string str; int cur = 0, i = num1.size()-1, j = num2.size()-1; int maxLength=i>j?i:j; while (maxLength>=0 || cur != 0) { if (i >= 0) cur += num1[i--] - '0'; if (j >= 0) cur += num2[j--] - '0'; str += to_string (cur % 2); cur /= 2; maxLength--; } reverse(str.begin(), str.end()); return str; }

其实那些数字2、数字10可以用一个变量来代替,该变量代表进行几进制的加法

最后

以上就是潇洒小馒头最近收集整理的关于67. 二进制求和c++(四种方法)的全部内容,更多相关67.内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(73)

评论列表共有 0 条评论

立即
投稿
返回
顶部