代码已经在 GITHUB 开源，👉点击直达👈。

〇、算法步骤

首先我们必须约定以下条件：

  • 参与运算的数 A 和 B 必须是非负整数。
  • 所有数均以数组的形式逆序存储。
  • 对于 $A_i$ 与 $B_i$ 分别为运算数 A 和 B 中对应第 i 位的数。
  • 一般 $…-t$ 或 $…+t$ 表示来自低位的借位货进位（低位向该位借了或进了 $t$）。
  • 一般 $…+10$ 表示向高地位借（该位向高位借了 $1$）。

数的存储示意图

为什么逆序存储运算数？

这是因为在运算中可能会产生进位，而在数组首端加上一个数是非常困难的（你需要将数组整体先向后移动一位，然后才能在数组首端加上一个新的数），但在数组末尾加上一个数字是非常容易的。所以，逆序存储大数是比较合适的选择。

同时，在实际运算中可能包含更加复杂的复合运算，故而对运算数都做相同的标准约束，更加统一且不易出错。

1. 加法

$$
C_i = A_i + B_i + t
\tag{1}
$$

  1. 计算当前为位 $C_i$ 的值。
  2. 计算进位 $t$ 的值。
  3. 循环步骤 1 和 步骤 2 直到 $A$ 或 $B$ 的最高位被计算（取决于 $A$ 和 $B$ 谁更长）。
  4. 计算最高位可能的进位 $t$（加法的和可能比加数更长）。

2. 减法

$$
C_i = \
\begin{cases}
A_i - B_i -t &, A_i - B_i \geq 0\\
A_i - B_i - t + 10 &, A_i - B_i < 0
\end{cases}
\tag{2}
$$

  1. 计算当前为位 $C_i$ 的值。
  2. 计算借位 $t$ 的值。
  3. 循环步骤 1 和 步骤 2 直到 $A$ 的最高位被计算（这里约定 $A \geq B$）。
  4. 去除高位可能的前缀 $0$（形如 $001$、$029$、… 是不被接受的）。

3. 乘法

这里算法实现思路与常规列式乘法计算方法有所不同。

这里的 b 等同于 B，但是不是大数（用常规手段存储，例如：int）

$$
C_i = (A_i * b + t) \text{ } mod \text{ } 10
\tag{3}
$$

  1. 计算当前位 $C_i$ 的值。
  2. 计算进位 $t$ 的值。
  3. 循环步骤 1 和 步骤 2 直到计算完成。
  4. 去除可能的前缀 0。

注意：这里不提供两个大数的乘法思路，但是二者算法大体上差不多，详细内容请看我在 GITHUB 的代码模板。

4. 除法

$$
C_i = (r * 10 + A_i) / b
\tag{4}
$$

  1. 计算当前位的子被除数：$r * 10 + A_i$。
  2. 计算当前位 $C_i$ 的值。
  3. 计算当前位的子余数 $r$。
  4. 重复步骤 1 至步骤 3 直到运算完成。
  5. 调整商的存储结构，确保逆序存储结果。
  6. 去除可能的前缀 0。

一、算法模板

1.1 加法

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
/**
 * @brief 非负大数运算 C = A + B
 * @param A 非负加数（逆序存储）
 * @param B 非负加数（逆序存储）
 * @return 运算结果（逆序存储）
 */
static vector<int> add(vector<int>& A, vector<int>& B) {
    vector<int> C;  // 运算结果

    // 加法计算
    int t = 0;      // 加法进位：来自低位
    for (int i = 0; i < A.size() || i < B.size(); i++) {    // 注意：要把两个数的所有位都计算完
        // 计算 A[i] + B[i] + t
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];

        C.push_back(t % 10);    // 保存本位的数值结果
        t /= 10;                // 计算向上的进位值
    }

    // 有可能 A 和 B 中的最高位之上还有进位值
    if (t) C.push_back(t);
    
    // 返回结果
    return C;
}

1.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
/**
 * @brief 判断 A >= B
 * @param A 非负整数（逆序存储）
 * @param B 非负整数（逆序存储）
 * @return A 是否大于等于 B
 */
static bool cmp(vector<int>& A, vector<int>& B) {
    // 位数检验
    if (A.size() != B.size()) {     // 当 A 和 B 位数不一样时
        return A.size() > B.size(); // 位数更长的数值更大
    }

    // 位数一致时：数值检验
    for (int i = A.size() - 1; i >= 0; i--) {   // 从高位到向低位遍历（注意 A 和 B 位数一致）
        if (A[i] != B[i]) {                     // 第一个同位数值不相同的位置出现
            return A[i] > B[i];                 // 该位上数值更大的数更大
        }
    }
    
    // 全部相等时（A = B）
    return true;
}

/**
 * @brief 计算 C = A - B（注意 A 必须大于等于 B，使用前必须检查）
 * @param A 非负整数（逆序存储）
 * @param B 非负整数（逆序存储）
 * @return 运算结果
 */
static vector<int> sub(vector<int>& A, vector<int>& B) {
    vector<int> C;  // 运算结果

    // 减法计算
    int t = 0;      // 减法借位：来自低位
    for (int i = A.size() - 1; i >= 0; i--) {
        // 计算 A[i] - B[i]
        t = A[i] - t;
        if (i < B.size()) t -= B[i];

        // 注意借位：
        //   - 减去低位借位 t（与下面代码中的 t 不是同一个东西）
        //   - 如果向高位借位要加上 10
        // 总和下来就是 (t + 10) % 10 得到本位的数值（这里处理比较巧妙，多理解）
        C.push_back((t + 10) % 10);

        // 如果小于 0 代表需要向高位借位
        t = (t < 0 ? 1 : 0);
    }

    // 去掉前缀 0（注意结果 C 为 0 的情况）
    while (C.size() > 1 && C.back() == 0) C.pop_back();

    // 返回结果
    return C;
}

1.3 乘法

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
/**
 * @brief 低配版大数乘法 C = A * b
 * @param A 非负整数（逆序存储）
 * @param b 非负整数
 * @return 积（逆序存储）
 */
static vector<int> mul(vector<int>& A, int b) {
    vector<int> C;  // 运算结果

    // 运算：(A[i] * b + t) % 10
    // 这里比较难理解（与平常的乘法列式计算方式有所不同）
    for (int i = 0, t = 0; i < A.size() || t; i++) {
        // C[i] = (A[i] * b + t) % 10
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);

        // 计算进位
        t /= 10;
    }

    // 去掉可能的前缀 0（当 b == 0 时就会出现前缀 0）
    while (C.size() > 1 && C.back() == 0) C.pop_back();

    // 返回结果
    return C;
}

1.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
28
29
/**
 * @brief 低配版除法 A / b = C ... r
 * @param A 被除数——非负整数（逆序存储）
 * @param b 除数——正整数
 * @param r 余数（out）
 * @return 商（逆序存储）
 */
static vector<int> div(vector<int>& A, int b, int& r) {
    vector<int> C;  // 运算结果

    // 运算（按照常规运算思维即可）
    r = 0;  // 余数初始化为 0
    for (int i = A.size() - 1; i >= 0; i--) {
        r = r * 10 + A[i];      // 计算当前位的子被除数
        C.push_back(r / b);     // 计算当前位的值 C[i]
        r %= b;                 // 计算当前位的子余数
    }

    // 修正存储方式
    // 计算完成后，存储的结果是“顺序存储”的，需要翻转
    reverse(C.begin(), C.end());// 注意：这里必须翻转

    // 去除前缀 0
    while (C.size() > 1 && C.back() == 0) C.pop_back();


    // 返回结果
    return C;
}

二、算法练习题

  1. AcWing 791. 高精度加法
  2. AcWing 792. 高精度减法
  3. AcWing 793. 高精度乘法
  4. AcWing 794. 高精度除法