C/C++高精度运算(大整数运算)详细讲解

简介

在进行高精度运算时，我们需要使用到很大的整数进行计算，如：1000的阶乘，1到1000的和等。而C/C++默认的整型数据类型一般只能存储到2^32-1或2^64-1这样的范围，需要我们使用数组或链表等结构来存储这类大数。本篇文章将详细介绍如何使用C/C++实现大整数和高精度运算。

实现方式

在C/C++中，大整数可以使用数组或链表来存储。我们通常使用数组来存储，每一位数字对应数组中的一个元素，最高位在数组的最前面。在进行高精度运算的过程中，需要注意进位和补零等情况。

加法

我们通常采用逐位相加的方法进行高精度加法。依次计算每一位的和，并且考虑到进位情况。

以下是C++代码示例：

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() || t; i++) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10); //将当前位数字存入结果数组中
        t /= 10; //更新进位状态
    }
    return c;
}

其中，vector是标准库中的动态数组容器，可变长数组，可以通过push_back方法在末尾添加元素。

减法

我们通常采用逐位相减的方法进行高精度减法。依次计算每一位的差，并且考虑借位情况。

以下是C++代码示例：

vector<int> sub(vector<int> a, vector<int> b) {
    vector<int> c;
    int t = 0; //借位
    for (int i = 0; i < a.size(); i++) {
        t = a[i] - t;
        if (i < b.size()) t -= b[i];
        c.push_back((t + 10) % 10); //将当前位数字存入结果数组中
        if (t < 0) t = 1; else t = 0; //更新借位状态
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back(); //删除前导零
    return c;
}

乘法

我们采用逐位相乘的方法进行高精度乘法。将一个数的每一位都分别与另一个数相乘，再将结果相加即可。

以下是C++代码示例：

vector<int> mul(vector<int> a, int b) {
    vector<int> c;
    int t = 0; //进位
    for (int i = 0; i < a.size() || t; i++) {
        if (i < a.size()) t += a[i] * b;
        c.push_back(t % 10); //将当前位数字存入结果数组中
        t /= 10; //更新进位状态
    }
    return c;
}

除法

我们采用逐位除法的方法进行高精度除法。将每一位的商都算出来，并且考虑到余数的情况。

以下是C++代码示例：

vector<int> div(vector<int> a, int b, int& r) {
    vector<int> c;
    r = 0; //余数
    for (int i = a.size() - 1; i >= 0; i--) {
        r = r * 10 + a[i];
        c.push_back(r / b); //将当前位商存入结果数组中
        r %= b; //更新余数状态
    }
    reverse(c.begin(), c.end()); //翻转数组
    while (c.size() > 1 && c.back() == 0) c.pop_back(); //删除前导零
    return c;
}

取余

取余运算与除法运算相似，只需要返回余数即可。

以下是C++代码示例：

int mod(vector<int> a, int b) {
    int r = 0; //余数
    for (int i = a.size() - 1; i >= 0; i--) {
        r = r * 10 + a[i];
        r %= b; //更新余数状态
    }
    return r;
}

示例

我们可以用高精度运算来计算1000的阶乘和1到1000的和。

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

vector<int> mul(vector<int> a, vector<int> b) { //高精度乘法
    vector<int> c(a.size() + b.size());
    for (int i = 0; i < a.size(); i++)
        for (int j = 0; j < b.size(); j++)
            c[i + j] += a[i] * b[j];
    for (int i = 0; i < c.size() - 1; i++) { //进位
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back(); //删除前导零
    return c;
}

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() || t; i++) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back(); //删除前导零
    return c;
}

int main() {
    vector<int> res(1, 1); //res初始为1
    for (int i = 1; i <= 1000; i++) { //计算阶乘
        vector<int> p;
        int t = i;
        while (t) { //将i转换为数组
            p.push_back(t % 10);
            t /= 10;
        }
        if (p.empty()) p.push_back(0); //防止空数组
        res = mul(res, p);
    }
    int sum = 0;
    for (int i = 1; i <= 1000; i++) { //计算和
        vector<int> p;
        int t = i;
        while (t) { //将i转换为数组
            p.push_back(t % 10);
            t /= 10;
        }
        if (p.empty()) p.push_back(0); //防止空数组
        res = add(res, p);
    }
    reverse(res.begin(), res.end()); //翻转数组
    for (int i = 0; i < 10; i++) { //输出前10位
        cout << res[i];
    }
    cout << endl;
    return 0;
}

总结

本篇文章介绍了C/C++实现高精度运算的方法，并给出了加法、减法、乘法、除法和取余的函数实现示例。我们可以利用高精度运算计算大数的阶乘、和等复杂运算。