高精度算法详解：大整数加减乘除实现与原理

高精度算法详解

当数值超出标准整型范围（如 long long）时，我们需要使用高精度算法。本质上，这是用代码模拟小学列竖式计算的过程。

一、核心思路

所有高精度运算都遵循一个基本模式：

1. 读入：使用字符串接收数字。
2. 存储：将每一位数字逆序存入数组（下标 0 存个位），方便从低位开始计算。
3. 运算：按位模拟加减乘除逻辑。
4. 输出：逆序打印数组内容。

二、高精度加法

题目背景

处理两个超大整数的相加，例如 A + B。

实现细节

模拟竖式加法，从最低位开始逐位相加，并处理进位。

#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int a[N], b[N], c[N];
int la, lb, lc;

void add(int a[], int b[], int c[]) {
    for (int i = 0; i < lc; i++) {
        c[i] += a[i] + b[i];      // 对应位相加
        c[i + 1] += c[i] / 10;    // 处理进位
        c[i] %= 10;               // 保留当前位
        if (c[lc]) lc++;          // 更新长度
    }
}

int main() {
    string x, y;
    cin >> x >> y;
    la = x.size();
    lb = y.size();
    lc = max(la, lb);
    
    // 逆序存储
    for (int i = 0; i < la; i++) a[la - i - 1] = x[i] - '0';
    for (int i = 0; i < lb; i++) b[lb - i - 1] = y[i] - '0';
    
    add(a, b, c);
    for (int i = lc - 1; i >= 0; i--) cout << c[i];
    return 0;
}

注意：这里逆序存储是为了让数组下标 0 对应个位，这样进位可以直接加到 i+1 位置，符合自然计算习惯。

三、高精度减法

题目背景

计算 A - B，需确保被减数大于等于减数。

实现细节

1. 比较大小：先比较位数，位数相同则按字典序比较。
2. 借位处理：若某一位不够减，向高位借 1 当 10。
3. 前导零：结果可能产生前导零，需去除。

#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int a[N], b[N], c[N];
string x, y;
int la, lb, lc;

bool cmp(string& x, string& y) {
    if (x.size() != y.size()) return x.size() < y.size();
    return x < y;
}

void sub(int c[], int a[], int b[]) {
    for (int i = 0; i < lc; i++) {
        c[i] += a[i] - b[i];
        if (c[i] < 0) {
            c[i + 1] -= 1;  // 向高位借位
            c[i] += 10;
        }
    }
    while (lc > 1 && c[lc - 1] == 0) lc--; // 去除前导零
}

int main() {
    cin >> x >> y;
    if (cmp(x, y)) {
        swap(x, y);
        cout << '-';
    }
    la = x.size();
    lb = y.size();
    lc = max(la, lb);
    
    for (int i = 0; i < la; i++) a[la - i - 1] = x[i] - '0';
    for (int i = 0; i < lb; i++) b[lb - i - 1] = y[i] - '0';
    
    sub(c, a, b);
    for (int i = lc - 1; i >= 0; i--) cout << c[i];
    return 0;
}

四、高精度乘法

题目背景

计算 A * B，通常涉及一个大整数乘以另一个大整数。

实现细节

采用'无进位相乘再统一进位'的策略，类似竖式乘法中每一行错位累加的过程。

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N], b[N], c[N];
string x, y;
int la, lb, lc;

void mul(int c[], int a[], int b[]) {
    // 无进位相乘，然后相加
    for (int i = 0; i < la; i++) {
        for (int j = 0; j < lb; j++)
            c[i + j] += a[i] * b[j];
    }
    
    // 统一处理进位
    for (int i = 0; i < lc; i++) {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    
    while (lc > 1 && c[lc - 1] == 0) lc--;
}

int main() {
    cin >> x >> y;
    la = x.size();
    lb = y.size();
    lc = la + lb;
    
    for (int i = 0; i < la; i++) a[la - i - 1] = x[i] - '0';
    for (int i = 0; i < lb; i++) b[lb - i - 1] = y[i] - '0';
    
    mul(c, a, b);
    for (int i = lc - 1; i >= 0; i--) cout << c[i];
    return 0;
}

五、高精度除法

题目背景

此处特指「高精度除以低精度」，即大整数除以普通整数。

实现细节

模拟手算除法，从高位到低位逐位试商。

#include<iostream>
using namespace std;

const int N = 1e6 + 10;
typedef long long LL;
int a[N], b, c[N];
string x;
int la;

void div(int c[], int a[], int b) {
    LL t = 0;
    for (int i = la - 1; i >= 0; i--) {
        t = t * 10 + a[i];      // 当前被除数
        c[i] = t / b;           // 记录商
        t %= b;                 // 余数留给下一位
    }
    while (la > 1 && c[la - 1] == 0) la--; // 去除前导零
}

int main() {
    cin >> x >> b;
    la = x.size();
    for (int i = 0; i < la; i++) a[la - i - 1] = x[i] - '0';
    
    div(c, a, b);
    for (int i = la - 1; i >= 0; i--) cout << c[i];
    return 0;
}

总结

高精度算法的核心在于将大数拆解为数组元素，通过模拟人工计算流程来突破数据类型限制。关键点包括：

• 存储方式：逆序存储便于进位和借位操作。
• 边界处理：务必检查前导零和空值情况。
• 复杂度：通常为 O(N)，N 为数字位数。

掌握这些模板后，面对大数运算问题即可从容应对。