目录

大数加法

https://cdn.lsvm.xyz/2020/04/2020-04-add-two-big-numbers-00.png!on_blog

大数加法即能够对超长位数的数字进行相加,比如一个 100 位数和一个 80 位数的数字相加。

在这种情况下,数的大小已经超出了基本类型(int,long,double,float)能够表示的范围,直接加减只能得到错误的结果,想要得到正确的结果就需要使用其他数据结构存储这些数字,同时构建相应的相加函数,这里应该想到可以使用占用空间可选的字符串类型。

问题抽象

输入为 (M,N):

  • $M$: 字符串 string 存储的 10 进制整数 $M$
  • $N$: 字符串 string 存储的 10 进制整数 $N$

输出为 S:

  • $S$: 字符串 string 存储的 10 进制大数 $S$

运算过程为:

$$M+N=S$$

数学原理

[https://leslie-cloud.oss-cn-beijing.aliyuncs.com/2020/08/2020-04-add-two-big-numbers-01.gif

可以看到,从低位到高位,将同位数字相加得到当前位的结果 result[i],并保存它的进位信息 carry 用于高位的运算,carry 的初始值为 0 。

1
2
result[i] = (a[i] + b[i] + carry) % 10
carry = (a[i] + b[i]) // 10

循环至两个数结束,若其中一个数长度小于另外一个数,则该数当前位使用 0 进行计算。

代码实现

这里给出 C++ 的算法实现,使用了大量内置的 STL,如不能使用 STL 库可自行实现相关类型。

 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
/**
 * Created by Leslie
 * 2020-03-28
 */

#include "string"
#include "algorithm"

using namespace std;

/**
 * Add two big decimal numbers
 * @param a string of a big number
 * @param b string of a big number
 * @return string of the result
 */
string AddTwoNumbers(string a, string b) {
    int x, y, sum, carry = 0;
    string result;
    auto iter_a = a.rbegin(), iter_b = b.rbegin();

    while (iter_a != a.rend() || iter_b != b.rend()) {
        // 其中一个数长度小于另外一个数,则遍历该数不存在的高位时,用0替代
        x = iter_a != a.rend() ? *iter_a - '0' : 0;
        y = iter_b != b.rend() ? *iter_b - '0' : 0;
        
        sum = x + y + carry;
        carry = sum / 10;
        result += char(sum % 10 + '0');
		
        // 遍历到最后一位时,迭代器不再移动
        if (iter_a != a.rend()) {
            iter_a++;
        }
        if (iter_b != b.rend()) {
            iter_b++;
        }
    }

    // 最高位存在进位
    if (carry == 1) {
        result += char(carry + '0');
    }

    reverse(result.begin(), result.end());
    return result;
}

这里的 string 类型完全可以使用 char* 替代,可以尝试使用 C 进行实现。