二进制之和

问题描述

给定两个二进制字符串，返回它们的和（用十进制字符串表示）。输入为非空字符串且只包含数字 1 和 0，需要考虑大数问题。时间复杂度不得超过 $O(n^2)$ ，其中 $n$ 是二进制字符串的最大长度。

解题思路

本题要求将两个二进制字符串相加，以十进制字符串的形式输出，同时需要考虑大数问题，不能使用内置的数据类型直接转换，核心在于通过字符串来模拟大数的四则运算，我们分两步来解决：

  1. 二进制字符串相加：模拟二进制加法，得到两个二进制字符串的和，结果也是一个二进制字符串。
  2. 二进制转十进制字符串：将得到的二进制和转换为十进制字符串，模拟大数乘法和加法。

具体步骤：

  • 二进制加法：从最低位开始逐位相加，注意进位。
  • 大数乘法和加法：在将二进制转换为十进制时，无法使用内置类型直接计算，需要模拟大数乘法（乘以 2）和大数加法（加上当前位的值）。

代码实现

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

string solution(string binary1, string binary2)
{
    // 二进制字符串相加
    string sum_binary = "";
    int i = binary1.size() - 1, j = binary2.size() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry)
    {
        int bit1 = i >= 0 ? binary1[i--] - '0' : 0;
        int bit2 = j >= 0 ? binary2[j--] - '0' : 0;
        int sum = bit1 + bit2 + carry;
        sum_binary.push_back((sum % 2) + '0');
        carry = sum / 2;
    }
    reverse(sum_binary.begin(), sum_binary.end());

    // 二进制转换为十进制字符串
    string decimal = "0";
    for (char c : sum_binary)
    {
        // decimal = decimal * 2 + (c - '0')
        // 模拟大数乘法：decimal * 2
        int carry = 0;
        for (int i = decimal.size() - 1; i >= 0; --i)
        {
            int num = (decimal[i] - '0') * 2 + carry;
            decimal[i] = (num % 10) + '0';
            carry = num / 10;
        }
        if (carry)
            decimal = to_string(carry) + decimal;

        // 模拟大数加法：decimal + (c - '0')
        if (c == '1')
        {
            carry = 1;
            for (int i = decimal.size() - 1; i >= 0 && carry; --i)
            {
                int num = (decimal[i] - '0') + carry;
                decimal[i] = (num % 10) + '0';
                carry = num / 10;
            }
            if (carry)
                decimal = '1' + decimal;
        }
    }

    return decimal;
}

int main()
{
    cout << (solution("101", "110") == "11") << endl;
    cout << (solution("111111", "10100") == "83") << endl;
    cout << (solution("111010101001001011", "100010101001") == "242420") << endl;
    cout << (solution("111010101001011", "10010101001") == "31220") << endl;
    return 0;
}

代码解析

二进制字符串相加

  • 初始化：设置指针 i 和 j 分别指向两个二进制字符串的末尾，初始化进位 carry 为 0 。
  • 逐位相加：使用 while 循环，只要 i 和 j 未遍历完或者有进位，就继续循环。
    • 取当前位的数字，如果指针已越界，则视为 0 。
    • 计算当前位的和 sum = bit1 + bit2 + carry 。
    • 结果的当前位为 sum % 2 ，更新进位 carry = sum / 2 。
  • 反转结果：将得到的二进制和字符串反转，得到正确的顺序。

二进制转十进制字符串

  • 初始化：设置十进制结果字符串 decimal = "0" 。
  • 遍历二进制和字符串：对于每一位 c ，进行以下操作：
    • 大数乘法：将当前的 decimal 乘以 2 。
      • 从低位到高位模拟乘法，将每一位乘以 2 ，加上进位。
      • 更新当前位，计算新的进位。
      • 如果最高位有进位，需在最前面添加。
    • 大数加法：如果当前位为 1，则需要在乘积的基础上加 1 。
      • 从低位到高位模拟加法，处理进位。
      • 如果最高位有进位，需在最前面添加。

知识点总结

  • 模拟大数运算：当数值超过内置数据类型范围时，需要使用字符串模拟大数的加法和乘法。
  • 字符串反转：在手动构造从低位到高位的结果时，最后需要反转字符串得到正确的顺序。
  • 二进制与十进制转换：二进制转十进制的核心原理，即不断乘以 2 并累加当前位的值。

时间复杂度

  • 二进制相加：遍历长度为 $n$ 的二进制字符串，时间复杂度为 $O(n)$ 。
  • 二进制转十进制：外层循环遍历长度为 $n$ 的二进制字符串，内层大数乘法和加法的时间复杂度最高为 $O(n)$ ，总体时间复杂度不超过 $O(n^2)$ 。

空间复杂度

  • 使用额外的字符串来存储结果，空间复杂度为 $O(n)$ 。

总结

通过模拟二进制加法和大数运算，实现了二进制字符串的相加并将结果转换为十进制字符串。核心在于大数乘法和加法的模拟，确保了算法在处理大数时不溢出，时间复杂度不超过 $O(n^2)$ 。