当前位置：首页 > news >正文

C++高精度加减乘除算法详解

news 2026/5/1 12:42:23

前言：在C++中，常规数据类型（int、long long）存在取值范围限制，其中long long的最大值仅约9e18，当需要处理数百位、数千位的超大整数（如加密运算、大数据分析、竞赛真题中的大数计算）时，就需要借助高精度算法。高精度算法的核心思想是用数组/容器模拟大整数的每一位，复刻手工竖式计算逻辑，手动处理进位、借位，彻底突破数据类型的位数限制。本文将从核心原理、代码实现、测试案例、避坑技巧四个维度，详细讲解高精度加减乘除四大基础运算，代码可直接复制使用，新手也能快速上手。

一、高精度算法核心预备知识

1.1 核心存储规则

高精度数的存储遵循「低位在前、高位在后」的原则，原因是手工计算时，进位、借位均从低位开始，此存储方式可避免频繁移动数组元素，简化运算逻辑。

示例：数字 123456 存储为 vector<int> nums = {6,5,4,3,2,1}，其中下标0对应个位（6），下标1对应十位（5），依次类推，下标5对应十万位（1）。

1.2 通用辅助函数

为简化代码，先实现两个通用辅助函数，后续所有运算均会复用，避免重复编码：

#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; // 辅助函数1：字符串转高精度数组（低位在前） vector<int> strToBig(string s) { vector<int> res; // 从字符串末尾（高位）遍历，存入数组（低位在前） for (int i = s.size() - 1; i >= 0; i--) { res.push_back(s[i] - '0'); // 字符转数字 } return res; } // 辅助函数2：高精度数组转字符串（高位在前，用于输出） string bigToStr(vector<int> num) { string res; // 跳过高位前导零（避免输出 000123 这类结果） int i = num.size() - 1; while (i >= 0 && num[i] == 0) i--; // 若全为零，直接返回 "0" if (i < 0) return "0"; // 从高位到低位拼接字符串 while (i >= 0) { res += (char)(num[i] + '0'); i--; } return res; }

二、高精度加法（A + B）

2.1 算法原理（模拟手工加法）

从低位（数组下标0）开始，逐位将A、B对应位的数字相加，同时加上上一位的进位；
当前位结果 = （A[i] + B[i] + 进位）% 10；
新的进位 = （A[i] + B[i] + 进位）/ 10；
遍历完A、B所有位后，若仍有进位（进位≠0），需将进位添加到结果的最高位。

2.2 完整代码实现

// 高精度加法：A + B，返回结果（低位在前） vector<int> add(vector<int>& A, vector<int>& B) { vector<int> res; int carry = 0; // 进位，初始为0 int i = 0; // 遍历所有位，直到A、B遍历完且进位为0 while (i < A.size() || i < B.size() || carry > 0) { // 累加当前位数字（若下标超出范围，视为0） if (i < A.size()) carry += A[i]; if (i < B.size()) carry += B[i]; // 存入当前位结果 res.push_back(carry % 10); // 更新进位 carry /= 10; i++; } return res; } // 测试函数（可直接运行） int main() { string a, b; cin >> a >> b; vector<int> A = strToBig(a); vector<int> B = strToBig(b); vector<int> C = add(A, B); cout << "A + B = " << bigToStr(C) << endl; return 0; }

2.3 测试案例与避坑提示

测试案例1：输入 99999999999999999999 1 → 输出 100000000000000000000

测试案例2：输入 123456789 987654321 → 输出 1111111110

避坑提示：无需提前判断A、B大小，加法对两个数的顺序无要求，直接累加即可。

三、高精度减法（A - B）

3.1 算法原理（模拟手工减法）

减法需先判断A、B大小：若A ≥ B，直接计算A - B；若A < B，计算B - A，结果前加负号。核心运算逻辑：

从低位开始，逐位用A[i]减去B[i]，同时减去上一位的借位；
若当前位差为负（A[i] - 借位 < B[i]），则向高位借位（借位=1），当前位差 += 10；
若当前位差非负，借位重置为0；
遍历结束后，去除结果中的高位前导零（如 1000 - 999 = 1，需去掉前面的三个0）。

3.2 完整代码实现

// 辅助函数3：判断A是否大于等于B（A、B均为低位在前） bool geq(vector<int>& A, vector<int>& B) { // 长度不同，长度长的数更大 if (A.size() != B.size()) return A.size() > B.size(); // 长度相同，从高位到低位逐位比较 for (int i = A.size() - 1; i >= 0; i--) { if (A[i] != B[i]) return A[i] > B[i]; } return true; // 两数相等 } // 高精度减法：A - B（保证A ≥ B），返回结果（低位在前） vector<int> sub(vector<int>& A, vector<int>& B) { vector<int> res; int borrow = 0; // 借位，初始为0 int i = 0; // 遍历A的所有位（A ≥ B，A的长度≥B） while (i < A.size()) { // 当前位差值 = A[i] - 借位 - B[i]（B下标超出范围视为0） int diff = A[i] - borrow; if (i < B.size()) diff -= B[i]; // 处理借位 if (diff < 0) { diff += 10; borrow = 1; } else { borrow = 0; } // 存入当前位结果 res.push_back(diff); i++; } // 去除高位前导零（保留至少1位，避免结果为0时为空） while (res.size() > 1 && res.back() == 0) { res.pop_back(); } return res; } // 测试函数（可直接运行） int main() { string a, b; cin >> a >> b; vector<int> A = strToBig(a); vector<int> B = strToBig(b); if (geq(A, B)) { vector<int> C = sub(A, B); cout << "A - B = " << bigToStr(C) << endl; } else { vector&lt;int&gt; C = sub(B, A); cout << "A - B = -" << bigToStr(C) << endl; } return 0; }

3.3 测试案例与避坑提示

测试案例1：输入 100000000000000000000 1 → 输出 99999999999999999999

测试案例2：输入 123 456 → 输出 -333

避坑提示：必须先判断A、B大小，否则会出现负数结果异常；去除前导零时，需保留至少1位（避免 0 - 0 输出空字符串）。

四、高精度乘法（分两种场景）

高精度乘法分为「大数 × 小整数」（小整数≤1e9）和「大数 × 大数」，两种场景实现逻辑不同，分别讲解（优先掌握第一种，竞赛中更常用）。

4.1 场景1：大数 × 小整数（A × b，b为int/long long）

4.1.1 算法原理

从低位开始，逐位用大数A的每一位 × 小整数b，同时加上上一位的进位；
当前位结果 = （A[i] × b + 进位）% 10；
新的进位 = （A[i] × b + 进位）/ 10；
遍历完A所有位后，若仍有进位，逐位添加到结果的最高位。

4.1.2 代码实现

// 高精度乘法：大数A × 小整数b，返回结果（低位在前） vector<int> mulBigSmall(vector<int>& A, long long b) { vector<int> res; long long carry = 0; // 进位用long long，避免溢出 int i = 0; // 遍历所有位，直到A遍历完且进位为0 while (i < A.size() || carry > 0) { if (i < A.size()) carry += (long long)A[i] * b; res.push_back(carry % 10); carry /= 10; i++; } // 去除前导零（避免 b=0 时输出 000...0） while (res.size() > 1 && res.back() == 0) { res.pop_back(); } return res; } // 测试函数 int main() { string a; long long b; cin >> a >> b; vector<int&gt; A = strToBig(a); vector&lt;int&gt; C = mulBigSmall(A, b); cout << "A × b = " << bigToStr(C) << endl; return 0; }

4.2 场景2：大数 × 大数（A × B）

4.2.1 算法原理

核心规律：大数A的第i位（低位在前，i从0开始）与大数B的第j位相乘，结果一定落在乘积的第i+j位。逻辑如下：

初始化结果数组res，长度为A.size() + B.size()（最大可能长度），初始值全为0；
双层遍历A、B，将A[i] × B[j]的结果累加到res[i+j]；
遍历res，处理进位：res[i] = （res[i] + 进位）% 10，进位 = （res[i] + 进位）/ 10；
去除res的高位前导零。

4.2.2 代码实现

// 高精度乘法：大数A × 大数B，返回结果（低位在前） vector<int> mulBigBig(vector<int>& A, vector<int>& B) { vector<int> res(A.size() + B.size(), 0); // 初始化结果数组 // 双层遍历，累加每一位的乘积 for (int i = 0; i < A.size(); i++) { for (int j = 0; j < B.size(); j++) { res[i + j] += A[i] * B[j]; } } // 处理进位 int carry = 0; for (int i = 0; i < res.size(); i++) { res[i] += carry; carry = res[i] / 10; res[i] %= 10; } // 去除高位前导零 while (res.size() > 1 && res.back() == 0) { res.pop_back(); } return res; } // 测试函数 int main() { string a, b; cin >> a >> b; vector<int> A = strToBig(a); vector<int> B = strToBig(b); vector<int&gt; C = mulBigBig(A, B); cout << "A × B = " << bigToStr(C) << endl; return 0; }

4.3 测试案例与避坑提示

测试案例1（大数×小整数）：输入 123456789 123 → 输出 15185185047

测试案例2（大数×大数）：输入 1234 5678 → 输出 7006652

避坑提示：大数×小整数时，进位需用long long，避免A[i]×b溢出；大数×大数时，结果数组初始长度需足够（A.size()+B.size()）。

五、高精度除法（分两种场景）

与乘法对应，高精度除法分为「大数 ÷ 小整数」和「大数 ÷ 大数」，重点掌握第一种（竞赛高频），第二种逻辑较复杂，仅做基础实现。

5.1 场景1：大数 ÷ 小整数（A ÷ b，b为int/long long，返回商+余数）

5.1.1 算法原理

手工竖式除法的逆过程，从高位开始逐位计算，核心逻辑：

从高位（数组末尾）开始，用当前余数 × 10 + A[i]，得到当前被除数；
当前位商 = 当前被除数 ÷ b；
更新余数 = 当前被除数 % b；
遍历结束后，商数组需反转（因从高位开始存储），再去除前导零。

5.1.2 代码实现

// 高精度除法：大数A ÷ 小整数b，返回商（低位在前），余数通过引用返回 vector<int> divBigSmall(vector<int>& A, long long b, long long& remainder) { vector<int> quotient; // 商，先从高位存储，最后反转 remainder = 0; // 余数初始为0 // 从高位（数组末尾）开始遍历 for (int i = A.size() - 1; i >= 0; i--) { remainder = remainder * 10 + A[i]; quotient.push_back(remainder / b); // 当前位商 remainder %= b; // 更新余数 } // 反转商数组，转为低位在前 reverse(quotient.begin(), quotient.end()); // 去除前导零 while (quotient.size() > 1 && quotient.back() == 0) { quotient.pop_back(); } return quotient; } // 测试函数 int main() { string a; long long b, remainder; cin >> a >> b; if (b == 0) { cout << "错误：除数不能为0" << endl; return 0; } vector<int> A = strToBig(a); vector<int> C = divBigSmall(A, b, remainder); cout << "A ÷ b = " << bigToStr(C) << endl; cout << "余数 = " << remainder << endl; return 0; }

5.2 场景2：大数 ÷ 大数（A ÷ B，返回商+余数）

5.2.1 算法原理（简化版）

核心思路：用减法模拟除法（求A里包含多少个B），通过高精度减法逐次减去B，直到A < B，减去的次数即为商，剩余的A即为余数。（效率较低，适合初学者理解，进阶可学习二分优化）

5.2.2 代码实现

// 辅助函数4：高精度加法（复用前面的add函数，用于商的累加） // 辅助函数5：高精度减法（复用前面的sub、geq函数） // 高精度除法：大数A ÷ 大数B，返回商（低位在前），余数通过引用返回 vector<int> divBigBig(vector<int>& A, vector<int>& B, vector<int>& remainder) { vector<int> quotient = {0}; // 商初始为0（低位在前） remainder = A; // 余数初始为A // 当余数 >= B时，继续减B，商加1 while (geq(remainder, B)) { remainder = sub(remainder, B); quotient = add(quotient, {1}); // 商加1 } return quotient; } // 测试函数 int main() { string a, b; cin >> a >> b; vector<int> A = strToBig(a); vector<int> B = strToBig(b); // 判断除数是否为0 if (bigToStr(B) == "0") { cout << "错误：除数不能为0" << endl; return 0; } vector<int> quotient, remainder; quotient = divBigBig(A, B, remainder); cout << "A ÷ B = " << bigToStr(quotient) << endl; cout << "余数 = " << bigToStr(remainder) << endl; return 0; }