C++ 二进制求和

题目：

给你两个二进制字符串，返回它们的和（用二进制表示）。

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

示例 1:

输入: a = "11", b = "1"
输出: "100"

个人解法：

这题比之前的加一问题略复杂一点，但是本质上还是进位问题。我自己的思路是从末位开始往前进行二进制求和，然后逐一往前比较。这里需要一个临时变量temp，代表我下一位是否需要向上一位进一.然后将数字放入到一个字符串中。由于采用的是从后往前放的形式，所以这个字符串是反的。最后我们可以使用一个字符串反转得到需要的结果。

另外一个问题是要考虑两个字符串的长度，a长于b，a等于b，以及b长于a等等。所以其中使用了很多的while语句做判断。

算法不算很好但是能解这个问题。

代码以及结果如下：

class Solution {
public:
    string addBinary(string a, string b) {
        string s; 
        int i,j,k;  
        int temp=0;  
        int length=0; 
        int length1=a.length(); 
        int length2=b.length();
        while(length1>0&&length2>0)
        {
            if(a[length1-1]=='0'&&b[length2-1]=='0'&&temp==0)
            {
                temp=0;
                s.push_back('0');
                length++;
                length1--;
                length2--;
            }
            else if((a[length1-1]=='0'&&b[length2-1]=='0'&&temp==1)||(a[length1-1]=='0'&&b[length2-1]=='1'&&temp==0)||(a[length1-1]=='1'&&b[length2-1]=='0'&&temp==0))
            {
                temp=0;
                s.push_back('1');
                length++;
                length1--;
                length2--;
            }
            else if((a[length1-1]=='0'&&b[length2-1]=='1'&&temp==1)||(a[length1-1]=='1'&&b[length2-1]=='0'&&temp==1)||(a[length1-1]=='1'&&b[length2-1]=='1'&&temp==0))
            {
                //cout<<"sum=2"<<endl;
                temp=1;
                s.push_back('0');
                length++;
                length1--;
                length2--;
            }
            else 
            {
                cout<<"sum=3"<<endl;
                temp=1;
                s.push_back('1');
                length++;
                length1--;
                length2--;
            }
        }
        while(!length1>0&&length2>0)
        {
            if(b[length2-1]=='0'&&temp==0)
            {
                temp=0;
                s.push_back('0');
                length++;
                length2--;
            }
            else if((b[length2-1]=='1'&&temp==0)||(b[length2-1]=='0'&&temp==1))
            {
                temp=0;
                s.push_back('1');
                length++;
                length2--;
            }
            else 
            {
                if(length2==1)
                {

                    s.push_back('0');
                    s.push_back('1');
                    temp=0;
                    length++;
                    length2--;
                }
                else
                {
                    temp=1;
                    s.push_back('0');
                    length++;
                    length2--;
                }
            }
        }
        while(length1>0&&!length2>0)
        {
            //cout<<"length1>0&&!length2>0"<<endl;
            if(a[length1-1]=='0'&&temp==0)
            {
                temp=0;
                s.push_back('0');
                length++;
                length1--;
            }
            else if((a[length1-1]=='0'&&temp==1)||(a[length1-1]=='1'&&temp==0))
            {
                temp=0;
                s.push_back('1');
                length++;
                length1--;
            }
            else 
            {
                //cout<<"length1>0&&!length2>0"<<endl;
                if(length1==1)
                {

                    s.push_back('0');
                    s.push_back('1');
                    temp=0;
                    length++;
                    length1--;
                }
                else
                {
                    temp=1;
                    s.push_back('0');
                    length++;
                    length1--;
                }
                
            }
        }
        while(!length1>0&&!length2>0)
        {
            if(temp==1)
            {
                s.push_back('1');
                break;
            }
            else
                break;
        }
        int len=s.length();
        cout<<"s.length: "<<len<<endl;
        string num;
        for(i=0;i<len;i++)
        {
            if(s[len-i-1]=='0')
            {
                num.push_back('0');
            }
            else
                num.push_back('1');
        }
        return num;
        
    }
};

标准解法

借鉴「列竖式」的方法，末尾对齐，逐位相加。在十进制的计算中「逢十进一」，二进制中我们需要「逢二进一」。

具体的，我们可以取n=max{∣a∣,∣b∣}，循环 n 次，从最低位开始遍历。我们使用一个变量carry 表示上一个位置的进位，初始值为 0。记当前位置对其的两个位为$a_i$和$b_i$.则每一位的答案为(carry+$a_i$+$b_i$)mode 2。下一位的进位为$(\frac{a_i+b_i+carry}{2})$。重复上述步骤，直到数字 a 和 b 的每一位计算完毕。最后如果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;
    }
};

这里的先进行反转然后在执行与运算确实是个不错的想法。代码确实很简洁。

标准解法二

先转化成数字的十进制然后相加然后再转化回去，但是有点太麻烦了没必要。

参考：
https://leetcode-cn.com/problems/add-binary/solution/er-jin-zhi-qiu-he-by-leetcode-solution/

最后

以上就是忧郁犀牛为你收集整理的C++ 二进制求和的全部内容，希望文章能够帮你解决C++ 二进制求和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。