高精度四则运算详解：从原理到实现（C/C++ 双语言版）

📦 数据表示：如何存一个“大数”？

✅ 核心思想

用 数组或字符串 存储十进制每一位。

例如：数字 12345 可表示为：

• 字符串 "12345"（高位在前）
• 数组 [1,2,3,4,5]（高位在前）
• 或反向数组 [5,4,3,2,1]（低位在前，便于进位处理）

本文统一采用：字符串输入，内部用 vector 低位在前存储

为什么低位在前？因为加法/乘法从个位开始，进位自然流向高位，数组索引递增更方便。

---

➕ 一、高精度加法

🔍 原理回顾

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

  999
+   1
-----
 1000

✨ 关键步骤

1. 从右往左遍历两个数
2. 当前位和 = a[i] + b[j] + 进位
3. 结果位 = 和 % 10，新进位 = 和 / 10
4. 循环直到所有位和进位处理完

💻 C++ 实现（推荐）

#include <vector>
#include <string>
#include <algorithm>

std::string add(const std::string& a, const std::string& b) {
    if (a == "0") return b;
    if (b == "0") return a;

    std::vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

    std::vector<int> C;
    int carry = 0;
    for (int i = 0; i < A.size() || i < B.size() || carry; i++) {
        if (i < A.size()) carry += A[i];
        if (i < B.size()) carry += B[i];
        C.push_back(carry % 10);
        carry /= 10;
    }

    std::string res;
    for (int i = C.size() - 1; i >= 0; i--) res += char(C[i] + '0');
    return res;
}

💻 C 语言实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void reverse(char* s) {
    int n = strlen(s);
    for (int i = 0; i < n / 2; i++) {
        char t = s[i]; s[i] = s[n - 1 - i]; s[n - 1 - i] = t;
    }
}

char* add(char* a, char* b) {
    if (strcmp(a, "0") == 0) return strdup(b);
    if (strcmp(b, "0") == 0) return strdup(a);

    int lenA = strlen(a), lenB = strlen(b);
    int maxn = lenA > lenB ? lenA : lenB;
    int* A = (int*)calloc(maxn + 1, sizeof(int));
    int* B = (int*)calloc(maxn + 1, sizeof(int));

    // 转为低位在前
    for (int i = 0; i < lenA; i++) A[i] = a[lenA - 1 - i] - '0';
    for (int i = 0; i < lenB; i++) B[i] = b[lenB - 1 - i] - '0';

    int* C = (int*)calloc(maxn + 2, sizeof(int));
    int carry = 0, size = 0;
    for (int i = 0; i < maxn + 1 || carry; i++) {
        if (i < lenA) carry += A[i];
        if (i < lenB) carry += B[i];
        C[i] = carry % 10;
        carry /= 10;
        size = i + 1;
    }

    char* res = (char*)malloc(size + 1);
    for (int i = 0; i < size; i++) res[i] = C[size - 1 - i] + '0';
    res[size] = '\0';

    free(A); free(B); free(C);
    return res;
}

---

➖ 二、高精度减法（仅非负结果）

假设 a ≥ b，否则需先比较大小并处理符号（本文暂不展开负数）

🔍 原理

模拟竖式减法，借位处理。

  1000
-    1
------
   999

✨ 关键步骤

1. 从个位开始，若 a[i] < b[i]，向高位借 1（即 +10）
2. 高位减 1（可能连锁借位）
3. 去除前导零

💻 C++ 实现

// 假设 a >= b
std::string subtract(std::string a, std::string b) {
    std::vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

    std::vector<int> C;
    for (int i = 0; i < A.size(); i++) {
        if (i < B.size()) A[i] -= B[i];
        if (A[i] < 0) {
            A[i] += 10;
            A[i + 1]--;
        }
        C.push_back(A[i]);
    }

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

    std::string res;
    for (int i = C.size() - 1; i >= 0; i--) res += char(C[i] + '0');
    return res;
}

注意：实际使用前应先写 compare(a, b) 判断大小。

---

✖️ 三、高精度乘法

🔍 原理（核心！）

利用 位权叠加：a[i] * b[j] 的结果应加到 结果的第 (i+j) 位（低位在前）。

例如：个位 × 十位 → 百位（10⁰ × 10¹ = 10¹ → 索引 1）

✨ 关键步骤

1. 初始化结果数组 res 长度为 len(a) + len(b)
2. 双重循环：对每一对数字相乘，累加到 res[i+j]
3. 统一处理进位
4. 去除前导零

💻 C++ 实现

std::string multiply(const std::string& a, const std::string& b) {
    if (a == "0" || b == "0") return "0";

    std::vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

    std::vector<int> C(a.size() + b.size(), 0);
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            C[i + j] += A[i] * B[j];
        }
    }

    // 处理进位
    int carry = 0;
    for (int i = 0; i < C.size(); i++) {
        C[i] += carry;
        carry = C[i] / 10;
        C[i] %= 10;
    }

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

    std::string res;
    for (int i = C.size() - 1; i >= 0; i--) res += char(C[i] + '0');
    return res;
}

💡 为什么高效？

• 避免了多次调用高精度加法
• 时间复杂度 O(nm)，空间 O(n+m)

---

➗ 四、高精度除法（大数 ÷ 小整数）

完整的大数 ÷ 大数较复杂（需试商），本文先介绍 大数 ÷ int，这是最常见需求。

🔍 原理

模拟长除法，从高位开始：

12345 ÷ 3:
1 ÷ 3 = 0 余 1
12 ÷ 3 = 4 余 0
03 ÷ 3 = 1 余 0
04 ÷ 3 = 1 余 1
15 ÷ 3 = 5 余 0
→ 结果 4115

✨ 关键步骤

1. 从高位到低位遍历被除数
2. 当前余数 ×10 + 当前位 → 新被除数
3. 商 = 新被除数 / 除数，余数更新
4. 注意前导零处理

💻 C++ 实现

// 返回 {商, 余数}
std::pair<std::string, int> divide(const std::string& a, int b) {
    std::string quotient;
    long long remainder = 0;
    bool leading = true;

    for (char c : a) {
        remainder = remainder * 10 + (c - '0');
        if (remainder >= b) {
            quotient += char(remainder / b + '0');
            remainder %= b;
            leading = false;
        } else {
            if (!leading) quotient += '0'; // 中间零要保留
        }
    }

    if (quotient.empty()) quotient = "0";
    return {quotient, (int)remainder};
}

完整大数除法 需要实现 compare、subtract、multiply_small 等辅助函数，篇幅所限暂略。

---

🧩 辅助工具：比较大小

// 比较 a 和 b（字符串形式）
bool greaterOrEqual(const std::string& a, const std::string& b) {
    if (a.size() != b.size()) return a.size() > b.size();
    return a >= b; // 字典序比较（因长度相同）
}

---

📊 总结：四则运算对比

运算	时间复杂度	核心技巧
加法	O(max(n,m))	进位处理
减法	O(max(n,m))	借位处理
乘法	O(nm)	位权叠加（i+j 定位）
除法（÷int）	O(n)	模拟长除法

---

🚀 使用建议

1. 优先用 C++：vector、string 自动管理内存，代码简洁安全
2. C 语言慎用：需手动 malloc/free，易内存泄漏
3. 竞赛中：通常只需实现加、乘（减法可转为加负数，除法较少见）
4. 工程中：直接用 GMP 库（GNU Multiple Precision Arithmetic Library）

---

🔚 结语

高精度运算是算法学习的“基本功”。它不依赖高级数据结构，却深刻体现了 “用简单操作组合解决复杂问题” 的编程思想。亲手实现一遍，你会对计算机如何处理数字有更深理解。

记住：所有复杂的计算，最终都归结为对 0~9 这十个数字的操作。

希望这篇博客能帮你打通高精度运算的任督二脉！如有疑问，欢迎讨论。

---

附：完整可运行 C++ 示例（加法+乘法）

#include <bits/stdc++.h>
using namespace std;

string add(string a, string b) { /* ... */ }
string multiply(string a, string b) { /* ... */ }

int main() {
    string a, b;
    cin >> a >> b;
    cout << "Sum: " << add(a, b) << endl;
    cout << "Product: " << multiply(a, b) << endl;
    return 0;
}

💡 提示：在 OJ 提交时，记得去掉调试输出，使用 ios::sync_with_stdio(0); cin.tie(0); 加速 IO。