第42章数组模拟高精度计算

在 C 和 C++ 语言中，基本数据类型（如 int、long long）能表示的整数范围有限，例如 int 通常最大为 2147483647，当需要处理超出此范围的大整数（如几百位甚至几千位的整数）时，就需要借助数组来模拟高精度计算。数组模拟高精度计算的核心思想是用数组的每个元素存储大整数的一位数字，通过模拟人工计算的方式实现加、减、乘、除等运算。

GESP C++ 五级知识块 3：要求掌握 C++ 数组模拟高精度加法、减法、乘法和除法。本章全部围绕这四个运算展开，并强调进位、借位、前导零与边界处理。

42.1 高精度计算的基本概念

42.1.1 大整数的存储

由于大整数的位数远超基本数据类型的表示范围，因此需要用数组来存储：

存储方式：通常将大整数的每一位数字存储在数组的一个元素中，且为了方便计算（如进位、借位），低位数字存储在数组的低位索引处（即数组下标越小，对应大整数的位越靠右，也就是个位在 arr[0]）。

例如，大整数 12345 在数组中的存储形式为：arr[0]=5, arr[1]=4, arr[2]=3, arr[3]=2, arr[4]=1，数组长度为 5（表示 5 位数字）。

大整数 12345 逆序存入数组

输入与转换：大整数通常以字符串形式输入，需要将字符串中的每个字符转换为对应的数字后，按上述存储方式存入数组。

string s = "12345";
int arr[1000] = {0};
int len = s.size();
for (int i = 0; i < len; i++) {
    arr[i] = s[len - 1 - i] - '0'; // 逆序存储，个位在前
}

42.1.2 高精度计算的特点

运算规则：完全模拟人工竖式计算，包含进位（加法、乘法）、借位（减法）；
数组长度：运算结果位数可能大于原数，数组需预留多余空间；
符号处理：负数运算先处理符号，绝对值运算后再判定结果正负（GESP 五级以非负大整数为常见考查范围，符号处理作为拓展了解）。

42.2 高精度加法

42.2.1 算法步骤

初始化结果数组，长度取两数最大位数 + 1，预留进位；
从数组 0 下标（最低位）逐位相加，累加当前数字 + 进位；
取模 10 为当前位结果，除以 10 更新进位；
最高位处理剩余进位；
逆序转换数组为字符串，去除前导零。

42.2.2 完整代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string add(string a, string b) {
    int arrA[1000] = {0}, arrB[1000] = {0}, res[1001] = {0};
    int lenA = a.size(), lenB = b.size();
    int maxLen = max(lenA, lenB);
    // 逆序存入数组
    for (int i = 0; i < lenA; i++)
        arrA[i] = a[lenA - 1 - i] - '0';
    for (int i = 0; i < lenB; i++)
        arrB[i] = b[lenB - 1 - i] - '0';
    int carry = 0;
    for (int i = 0; i < maxLen; i++) {
        int sum = arrA[i] + arrB[i] + carry;
        res[i] = sum % 10;
        carry = sum / 10;
    }
    if (carry != 0) {
        res[maxLen] = carry;
        maxLen++;
    }
    // 转字符串
    string result;
    for (int i = maxLen - 1; i >= 0; i--)
        result += res[i] + '0';
    return result;
}

42.3 高精度减法

42.3.1 算法步骤

先比较两个大整数，保证被减数 ≥ 减数（若小于则交换并记录负号）；
逆序存入数组，从最低位逐位相减；
当前位不够则向高位借 1 当 10；
计算完成后删除结果前导零。

42.3.2 辅助比较函数 + 减法代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 判断 a >= b（按数值大小，而非字典序）
bool greaterOrEqual(string a, string b) {
    if (a.size() != b.size())
        return a.size() > b.size();
    return a >= b;
}

string subtract(string a, string b) {
    int arrA[1000] = {0}, arrB[1000] = {0}, res[1000] = {0};
    int lenA = a.size(), lenB = b.size();
    int maxLen = lenA;
    // 逆序存储
    for (int i = 0; i < lenA; i++)
        arrA[i] = a[lenA - 1 - i] - '0';
    for (int i = 0; i < lenB; i++)
        arrB[i] = b[lenB - 1 - i] - '0';
    // 逐位借位相减
    for (int i = 0; i < maxLen; i++) {
        if (arrA[i] < arrB[i]) {
            arrA[i] += 10;
            arrA[i + 1]--;
        }
        res[i] = arrA[i] - arrB[i];
    }
    // 去除前导零
    int resLen = maxLen;
    while (resLen > 1 && res[resLen - 1] == 0)
        resLen--;
    string result;
    for (int i = resLen - 1; i >= 0; i--)
        result += res[i] + '0';
    return result;
}

42.4 高精度乘法（大整数 × 大整数）

42.4.1 算法步骤（大整数 × 大整数）

逆序存储两个大整数 a[]、b[]；
对于任意 $i, j$ ，有 res[i + j] += a[i] * b[j]，即第 $i$ 位乘第 $j$ 位累加到结果的第 $i+j$ 位；
全部相乘后统一从低位到高位处理进位；
逆序生成结果字符串并去除前导零。

结果最大位数约为 lenA + lenB。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 大整数 × 大整数
string multiply(string a, string b) {
    int n = a.size(), m = b.size();
    vector<int> res(n + m, 0);
    // 逆序存入临时数组
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            res[i + j] += (a[n - 1 - i] - '0') * (b[m - 1 - j] - '0');
    // 统一进位
    int carry = 0;
    for (int i = 0; i < n + m; i++) {
        int cur = res[i] + carry;
        res[i] = cur % 10;
        carry = cur / 10;
    }
    // 转字符串并去除前导零
    string ans;
    int i = n + m - 1;
    while (i > 0 && res[i] == 0) i--; // 至少保留一位
    while (i >= 0) ans += res[i--] + '0';
    return ans;
}

42.4.2 大整数 × 小整数（简化版）

当乘数为普通 int 时，可逐位乘并累加进位，代码更简洁（见下）：

string multiplySmall(string a, int b) {
    if (b == 0) return "0";
    int arrA[1000] = {0}, res[1000] = {0};
    int lenA = a.size();
    for (int i = 0; i < lenA; i++)
        arrA[i] = a[lenA - 1 - i] - '0';
    int carry = 0, resLen = lenA;
    for (int i = 0; i < lenA; i++) {
        int product = arrA[i] * b + carry;
        res[i] = product % 10;
        carry = product / 10;
    }
    while (carry > 0) {
        res[resLen] = carry % 10;
        carry /= 10;
        resLen++;
    }
    string result;
    for (int i = resLen - 1; i >= 0; i--)
        result += res[i] + '0';
    return result;
}

42.5 高精度除法（大整数 ÷ 普通整数）

42.5.1 算法步骤

与加减乘不同，除法从最高位开始计算；
余数初始为 0，从最高位依次计算 余数 * 10 + 当前数字；
商当前位 = 余数 / 除数，更新余数 = 余数 % 除数；
去除商数组前导零，输出商和最终余数。

42.5.2 代码实现

#include <iostream>
#include <string>
#include <utility>
using namespace std;

// 返回 pair<商字符串, 余数>
pair<string, int> divide(string a, int b) {
    int arrA[1000] = {0};
    int lenA = a.size();
    for (int i = 0; i < lenA; i++)
        arrA[i] = a[lenA - 1 - i] - '0';
    int quotient[1000] = {0};
    int remainder = 0;
    // 从最高位遍历
    for (int i = lenA - 1; i >= 0; i--) {
        remainder = remainder * 10 + arrA[i];
        quotient[i] = remainder / b;
        remainder = remainder % b;
    }
    // 去掉前导零
    int qLen = lenA;
    while (qLen > 1 && quotient[qLen - 1] == 0)
        qLen--;
    string qStr;
    for (int i = qLen - 1; i >= 0; i--)
        qStr += quotient[i] + '0';
    return make_pair(qStr, remainder);
}

// 测试示例
int main() {
    auto ans = divide("12345", 7);
    cout << "商：" << ans.first << "，余数：" << ans.second << endl;
    return 0;
}

42.5.3 大整数 ÷ 大整数思路

多次高精度减法逼近商的每一位，依赖高精度减法、乘法辅助实现，代码复杂度更高，GESP 五级通常以"大整数 ÷ 普通整数"为考查重点。

42.6 高精度计算注意事项

数组容量：根据题目最大位数定义数组，避免下标越界；
前导零：减法、乘法、除法运算后必须清除多余前导零，仅数字 0 保留单个 0；
特殊值：乘数/除数为 0 单独特判，简化逻辑；
性能优化：超长数字可分段存储（每数组元素存 4 位数字）减少循环次数；
符号：涉及负数时先比较绝对值大小并标记结果符号。

42.7 选择题练习

用数组逆序存储大整数 806 时，arr[0]、arr[1]、arr[2] 的值依次是： A. 8, 0, 6 B. 6, 0, 8 C. 0, 8, 6 D. 6, 8, 0

查看答案
答案：B。逆序存储时个位在前，806 的个位是 6、十位是 0、百位是 8，故 arr[0]=6, arr[1]=0, arr[2]=8。
高精度加法中，处理完所有数位后若 carry != 0，应当： A. 忽略进位 B. 把进位加到结果最高位之前（即多出一个新高位） C. 报错 D. 把进位丢弃

查看答案
答案：B。例如 99 + 1 = 100，原两数都是 2 位，结果有 3 位，最后剩余的进位必须作为新的最高位写入结果。
两个长度分别为 $n$ 和 $m$ 的大整数相乘，结果的最大位数约为： A. $\max(n, m)$ B. $n + m$ C. $n \times m$ D. $\min(n, m)$

查看答案
答案：B。乘法结果位数不会超过两数位数之和，例如 $99 \times 9 = 891$ （2+1=3 位）， $999 \times 999 = 998001$ （3+3=6 位）。
高精度减法 substract("1000", "1") 去除前导零后结果应为： A. "0999" B. "999" C. "1001" D. "099"

查看答案
答案：B。1000 - 1 = 999，前导零需清除，保留 "999"。
高精度除法 divide("12345", 7) 的余数应为： A. 0 B. 1 C. 4 D. 5

查看答案
答案：C。 $12345 = 7 \times 1763 + 4$ ，故商为 1763，余数为 4。