C/C++高精度算术运算的实现方案

七月

发布时间：2026-10-15| 4人浏览过

原创

当常规数据类型无法满足运算需求时，采用数组模拟竖式的算法是实现大整数加减乘除的有效方案。

C/C++高精度运算原理

C/C++中的基本数据类型（如 int 或 long long）存储范围有限，难以计算如 1000!（约2568位）这样的大数值。高精度算法的核心思路是使用一个数组来存储这个大数，其中每一位（或几位）对应一个数组元素，存储顺序通常为低位到高位。

这种“压位”策略不仅能提高存储空间利用率，还能显著减少运算次数，提升效率。以下将详细说明实现高精度加法、减法、乘法和除法的关键步骤与代码。

参数定义与初始化

第1步：定义压位进制与辅助宏

目的：配置用于存储数字的数组类型及其进制基数。在 32/64 位系统下，通常每 9 位十进制数字存入一个 uint64_t，以平衡内存占用和运算速度。

代码逻辑：使用 #define NUM_DIGIT 9 定义压位数，并据此动态计算进制 _hex（例如 10^9）以及底层存储类型 _NUM_T。

// 基础参数配置
#define NUM_DIGIT 9 // 每个数组元素存储的十进制位数 (1~9)
// 根据 NUM_DIGIT 自动选择最合适的整形
#if NUM_DIGIT <= 2
    #define _NUM_T int8_t
#elif NUM_DIGIT <= 4
    #define _NUM_T int16_t
#else
    #define _NUM_T int64_t
#endif
static const size_t _hex = (size_t)pow(10, NUM_DIGIT); // 进制值，如 10^9

第2步：实现输入转换与比较函数

目的：将字符串或普通整数转换为内部高精度数组格式，并提供大小比较接口以供后续运算调用。

实现要点：从字符串末尾向前读取，每次截取 NUM_DIGIT 位放入数组；比较时先比长度，再逐位比较数值。

// 字符串转高精度数组 (低位存高地址索引，高位存低索引) - 简化版伪代码逻辑示意
void initByStr(_NUM_T* arr, const char* str) {
    size_t len = strlen(str);
    for (int i = 0; i < len; i += NUM_DIGIT) {
        // 从后往前切片读取填入数组...
    }
}

核心运算算法实现

第3步：实现高精度加法

目的：模拟竖式加法，从低位开始逐位相加，处理进位。

操作说明：遍历较短数的所有位进行累加，若产生进位则向下一位累加，并检查最终是否有进位需扩容。

size_t add(_NUM_T* a, size_t lenA, const _NUM_T* b, size_t lenB) {
    size_t i;
    uint64_t carry = 0;
    size_t n = max(lenA, lenB);
    
    for (i = 0; i < n || carry; i++) {
        uint64_t sum = carry + a[i] + (i < lenB ? b[i] : 0);
        a[i] = sum % _hex;
        carry = sum / _hex;
    }
    return i;
}

第4步：实现高精度减法

目的：模拟竖式减法。注意：本实现假设被减数大于等于减数，否则结果将为负值（需外部预处理）。

操作说明：逐位相减，若当前位结果为负，则向高位借位（即加上 _hex）并标记上一位需要减去 1。

size_t sub(_NUM_T* a, size_t lenA, const _NUM_T* b, size_t lenB) {
    size_t i;
    for (i = 0; i < lenB; i++) {
        if (a[i] >= b[i]) {
            a[i] -= b[i];
        } else {
            a[i] += _hex;
            a[i+1]--; // 向高位借位
            a[i] -= b[i];
        }
    }
    // 处理剩余位的借位传播... 
    return trimZeroes(a); // 去除前导零返回实际长度
}

第5步：实现高精度乘法

目的：模拟竖式乘法。复杂度约为 O(N*M)，适合大多数场景。

操作说明：双重循环，外层遍历乘数 a，内层遍历被乘数 b，结果累积到临时数组 c。注意处理同位次的进位传递。

size_t mul(const _NUM_T* a, size_t lenA, const _NUM_T* b, size_t lenB, _NUM_T* c) {
    memset(c, 0, sizeof(_NUM_T) * (lenA + lenB));
    for (size_t i = 0; i < lenA; i++) {
        uint64_t carry = 0;
        for (size_t j = 0; j < lenB || carry; j++) {
            uint64_t cur = c[i+j] + carry + (j<lenB ? (uint64_t)a[i]*b[j] : 0);
            c[i+j] = cur % _hex;
            carry = cur / _hex;
        }
    }
    return trimZeroes(c);
}

第6步：实现高精度除法

目的：模拟竖式除法，求出商和余数。这是最复杂的运算，通常涉及试商和反复减法。

操作说明：从高位到低位对齐除数与被除数，估算商的位数和大小，利用减法进行迭代扣除，直到被除数小于除数。

size_t div(const _NUM_T* A, size_t lenA, const _NUM_T* B, size_t lenB, _NUM_T* C, _NUM_T* R) {
    memcpy(R, A, sizeof(_NUM_T) * lenA); // 余数初始化为被除数
    memset(C, 0, sizeof(_NUM_T) * lenA); 
    size_t shift = lenA - lenB;
    
    while(shift >= 0) {
        // 执行一次带位移的除法逻辑，更新商 C 和余数 R
        // ... 具体试商逻辑省略，参考完整版高精度除法库代码
    }
    return trimZeroes(C);
}