67. 二进制求和c++(四种方法)

110 阅读 0 评论 73 点赞

我是靠谱客的博主潇洒小馒头，这篇文章主要介绍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; 
    }