二进制求和

问题描述

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

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

提示：

每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 “0” ，就都不含前导零。

来源：力扣（LeetCode）

示例

示例 1：

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

示例 2：

输入: a = "1010", b = "1011"
输出: "10101"

思路

刚开始想法直接将输入转为10进制，再进行累加然后将结果转化为2进制输出，结果发现题目要求1 <= a.length, b.length <= 10^4。最后还是直接用数组来操作，首先将字符串a和字符串b进行对齐操作，然后对二进制数相加并进行判断，用carry来保存是否有进位，最高位有进位的话在字符串头部插入1。

代码

if (a == "0" && b == "0")
{
    return "0";
}  
string result = "";
string shortString, longString;
if (a.length() == b.length())
{
    shortString = a;
    longString = b;
}
else{
    shortString = (a.length() < b.length() ? a : b);
    longString = (a.length() > b.length() ? a : b);
}
int length = (a.length() > b.length() ? a.length() : b.length()); 
int shortlength = (a.length() < b.length() ? a.length() : b.length());
for (int i = shortlength; i < length; i++)
{
    shortString.insert(0, 1, '0');
}

int carry = 0;
for (int i = length - 1; i >= 0; i--)
{
    if (shortString[i] == '1' && longString[i] == '1')
    {
        if (carry == 1){
            result.insert(0, 1, '1');
        }
        else{
            result.insert(0, 1, '0');
        }
        carry = 1;
    }
    else if(shortString[i] == '1' || longString[i] == '1'){
        if (carry == 1){
            result.insert(0, 1, '0');
            carry = 1;
        }
        else{
            result.insert(0, 1, '1');
            carry = 0;
        }
    }
    else{
        if (carry == 1){
            result.insert(0, 1, '1');
        }
        else{
            result.insert(0, 1, '0');
        }
        carry = 0;
    }
}
if (carry == 1)
{
    result.insert(0, 1, '1');
}
return result;

// binary to decimal
int toDecimal(string s) {
    int decimal = 0;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '1')
        {
            decimal += pow(2, (s.length() - 1 - i));
        }
    }
    return decimal;
}

// decimal to binary
string toBinary(int n) {
    string binary = "";
    int remainder;
    while(n >= 1){
        remainder = n % 2; 
        n = n / 2;
        if (remainder == 0){
            binary.insert(0, 1, '0');
        }
        else{
            binary.insert(0, 1, '1');   
        }
    }
    return binary;
}