概述
高精度运算处理超出内置整数类型范围的大数计算，通过模拟手算实现。核心挑战在于平衡效率与代码复杂度，形成从教学到竞赛再到工业应用的渐进式技术路线。
C++算法
高精度运算的加减乘除算法详解
基于字符串存储的高精度算术运算算法，包括加法、减法、乘法和除法。内容涵盖算法核心思想、详细计算步骤示例、C++ 代码模板（含朴素版与优化版）以及复杂度分析。文章还总结了常见陷阱与教学建议，旨在帮助读者理解大数处理原理并掌握相关实现技巧。
基于字符串存储的高精度算术运算算法，包括加法、减法、乘法和除法。内容涵盖算法核心思想、详细计算步骤示例、C++ 代码模板（含朴素版与优化版）以及复杂度分析。文章还总结了常见陷阱与教学建议，旨在帮助读者理解大数处理原理并掌握相关实现技巧。
高精度运算处理超出内置整数类型范围的大数计算，通过模拟手算实现。核心挑战在于平衡效率与代码复杂度，形成从教学到竞赛再到工业应用的渐进式技术路线。
存储结构：字符串顺序存储，下标 0 对应最高位 运用场景：
时间复杂度（n 为数字位数）：
空间复杂度：O(n)，每个字符存储一位十进制数，空间利用率仅 log₁₀(256)≈40%
关键特性：
本质：完全模拟人类列竖式计算的过程，将数字视为字符串，高位在左（下标 0）。 核心矛盾：人类计算从低位开始，但字符串存储是高位在前，因此运算时需要'对齐个位'，这通常通过反转字符串或从末尾遍历来实现。 比喻：就像两个队伍从头（高位）到尾（低位）排列，但计算时需要让尾巴（个位）先碰头，处理起来需要额外步骤。
123 + 89 为例）步骤 1: 原始存储 (高位在左) a = "123" (百位 1, 十位 2, 个位 3) b = "89" (十位 8, 个位 9)
步骤 2: 反转对齐个位（关键操作）a_rev = "321" (下标 0 为个位) b_rev = "98" (下标 0 为个位)
步骤 3: 逐位相加，处理进位 (从下标 0 开始)
位 0: 3 + 9 = 12 → 写 2，进位 1
位 1: 2 + 8 + 1(进位) = 11 → 写 1，进位 1
位 2: 1 + 0 + 1(进位) = 2 → 写 2，进位 0
位 3: (无) → 结束
结果（反转后）："212"
步骤 4: 反转回高位在前
最终结果："212"
#include <algorithm>
#include <string>
using namespace std;
string add(string a, string b) {
// 步骤 1：反转字符串，使得下标 0 对应个位
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
string result;
int carry = 0; // 进位
// 步骤 2：逐位相加
for (int i = 0; i < a.size() || i < b.size(); ++i) {
int digit_sum = carry; // 当前位和初始化为进位值
if (i < a.size()) digit_sum += a[i] - '0'; // 加上 a 的当前位
if (i < b.size()) digit_sum += b[i] - '0'; // 加上 b 的当前位
result.push_back(digit_sum % 10 + '0'); // 取个位作为结果位
carry = digit_sum / 10; // 计算新的进位
}
// 步骤 3：处理最后的进位
if (carry) result.push_back(carry + '0');
// 步骤 4：反转回高位在前
reverse(result.begin(), result.end());
return result;
}
关键注释：
- '0' 和 + '0' 实现，增加了常数开销。string add_opt(string a, string b) {
int i = a.size() - 1, j = b.size() - 1; // 从个位（字符串末尾）开始
string result;
int carry = 0;
while (i >= 0 || j >= 0 || carry) {
int digit_sum = carry;
if (i >= 0) digit_sum += a[i--] - '0';
if (j >= 0) digit_sum += b[j--] - '0';
result.push_back(digit_sum % 10 + '0');
carry = digit_sum / 10;
}
// 此时 result 是低位在前，需要反转
reverse(result.begin(), result.end());
return result;
}
优化点：避免了输入字符串的显式反转，但结果仍需一次反转。运算逻辑更直观地与'从个位开始'相匹配。
性能痛点：
char（通常 1 字节）仅存储一位数字（0-9），利用率低。± '0' 操作。本质：模拟列竖式减法，从低位到高位逐位相减，不够减时向高位借位。 核心挑战：
借位机制：当当前位不够减时，从左边高位借 1 当 10，高位相应减 1。
1234 - 567 为例）步骤 1: 对齐数字（右对齐）
被减数：1234
减数：0567 (前面补 0 对齐)
步骤 2: 从个位开始逐位相减（下标从右向左）
位 3(千位): 1 - 0 = 1
位 2(百位): 2 - 5 → 不够减，向前借位 (2-1) 借位后变成 1, 1 - 5 仍不够，继续向前借位
最终：12 - 5 = 7，标记有借位
位 1(十位): 3 被借位后变成 2, 2 - 6 → 不够减
向前借位：12 - 6 = 6
位 0(个位): 4 被借位后变成 3, 3 - 7 → 不够减
向前借位：13 - 7 = 6
步骤 3: 处理结果
初步结果：[7, 6, 6, 6] (从高位到低位)
去除前导零：767
验证：1234 - 567 = 667
#include <algorithm>
#include <string>
using namespace std;
// 比较两个字符串数字大小
bool lessThan(string a, string b) {
if (a.size() != b.size()) return a.size() < b.size();
return a < b;
}
// 减法：假设 a >= b
string subtract(string a, string b) {
// 步骤 1: 确保 a >= b
if (lessThan(a, b)) return "-" + subtract(b, a);
// 步骤 2: 反转字符串，让个位在下标 0
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
// 步骤 3: 补零使长度相等
while (b.size() < a.size()) b.push_back('0');
string result;
int borrow = 0; // 借位标志
// 步骤 4: 逐位相减
for (int i = 0; i < a.size(); i++) {
int digit_a = a[i] - '0' - borrow; // 先减去借位
int digit_b = b[i] - '0';
if (digit_a < digit_b) {
digit_a += 10; // 向前借位
borrow = 1; // 标记已借位
} else {
borrow = 0;
}
result.push_back((digit_a - digit_b) + '0');
}
// 步骤 5: 去除结果前导零
reverse(result.begin(), result.end());
while (result.size() > 1 && result[0] == '0') {
result.erase(result.begin());
}
return result;
}
关键注释：
borrow 变量记录是否向上一位借位，影响当前位的被减数。性能瓶颈：
本质：模拟"竖式乘法"，将乘数的每一位与被乘数相乘，再将结果错位相加。
关键点：
123 × 45 为例）步骤 1: 分解乘数（45）为 40 + 5
部分积 1: 123 × 5 = 615
部分积 2: 123 × 4 = 492，左移一位 → 4920
步骤 2: 对齐相加
615
+4920
-----
5535
步骤 3: 详细位运算过程：
个位：3×5=15 → 写 5，进位 1
十位：2×5=10 + 进位 1 = 11 → 写 1，进位 1
百位：1×5=5 + 进位 1 = 6 → 写 6
结果：615
同理计算 123×4=492，左移后为 4920
最终相加：615+4920=5535
#include <vector>
#include <algorithm>
using namespace std;
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
int n1 = num1.size(), n2 = num2.size();
vector<int> result(n1 + n2, 0); // 最大长度为 n1+n2
// 步骤 1: 逐位相乘
for (int i = n1 - 1; i >= 0; i--) {
for (int j = n2 - 1; j >= 0; j--) {
int mul = (num1[i] - '0') * (num2[j] - '0');
int p1 = i + j; // 高位位置
int p2 = i + j + 1; // 低位位置
// 当前位加上乘积
int sum = mul + result[p2];
result[p2] = sum % 10; // 当前位
result[p1] += sum / 10; // 进位到高位
}
}
// 步骤 2: 转换为字符串，去除前导零
string res_str;
for (int num : result) {
if (!(res_str.empty() && num == 0)) { // 跳过前导零
res_str.push_back(num + '0');
}
}
return res_str.empty() ? "0" : res_str;
}
关键注释：
vector<int> 存储中间结果，长度最多为 n1+n2。num1[i] 和 num2[j] 的乘积应放在结果的 i+j+1 位置（个位）。string multiply_opt(string a, string b) {
if (a == "0" || b == "0") return "0";
int m = a.size(), n = b.size();
string res(m + n, '0'); // 预分配结果字符串
for (int i = m - 1; i >= 0; i--) {
int carry = 0;
for (int j = n - 1; j >= 0; j--) {
int tmp = (res[i + j + 1] - '0') + // 已有值
(a[i] - '0') * (b[j] - '0') + // 新乘积
carry;
res[i + j + 1] = tmp % 10 + '0'; // 更新当前位
carry = tmp / 10; // 计算进位
}
res[i] += carry; // 处理每一行的最高进位
}
// 去除前导零
size_t start = res.find_first_not_of('0');
return start != string::npos ? res.substr(start) : "0";
}
优化点：
性能分析：
本质：模拟"长除法"，逐位试商，从被除数高位开始，每次取出一部分与除数比较。
核心过程（以 1234 ÷ 12 为例）：
102 ← 商
------
12)1234
-12 ← 12×1=12
---
34
-24 ← 12×2=24
---
10 ← 余数
试商方法：
1234 ÷ 12 为例）步骤 1: 取被除数前两位"12"，与除数"12"比较
12 ÷ 12 = 1，余数 0
商第一位：1
步骤 2: 将下一位"3"落下，组成"03"（实际为 3）
3 < 12，商第二位：0
步骤 3: 将下一位"4"落下，组成"34"
34 ÷ 12 = 2（试商），12×2=24 ≤ 34
34 - 24 = 10
商第三位：2
步骤 4: 最终结果
商：102，余数：10
// 除法：返回商和余数
pair<string, int> divide(string dividend, int divisor) {
string quotient; // 商
int remainder = 0; // 余数
for (int i = 0; i < dividend.size(); i++) {
// 将当前位加入余数
remainder = remainder * 10 + (dividend[i] - '0');
// 计算当前位的商
int q = remainder / divisor;
remainder %= divisor;
// 添加到商中（跳过前导零）
if (!(quotient.empty() && q == 0)) {
quotient.push_back(q + '0');
}
}
// 如果商为空，说明结果为 0
if (quotient.empty()) quotient = "0";
return {quotient, remainder};
}
// 比较两个字符串数字
int compare(string a, string b) {
if (a.size() != b.size()) return a.size() > b.size() ? 1 : -1;
return a.compare(b); // 相同长度直接比较
}
// 高精度减法（辅助函数）
string subtract_for_div(string a, string b) {
// 反转处理减法
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
while (b.size() < a.size()) b.push_back('0');
string res;
int borrow = 0;
for (int i = 0; i < a.size(); i++) {
int digit_a = a[i] - '0' - borrow;
int digit_b = b[i] - '0';
if (digit_a < digit_b) {
digit_a += 10;
borrow = 1;
} else {
borrow = 0;
}
res.push_back((digit_a - digit_b) + '0');
}
reverse(res.begin(), res.end());
// 去除前导零
while (res.size() > 1 && res[0] == '0') res.erase(res.begin());
return res;
}
// 高精度除法
pair<string, string> divide(string a, string b) {
if (compare(a, b) < 0) return {"0", a}; // a < b
string quotient; // 商
string current; // 当前被除部分
for (int i = 0; i < a.size(); i++) {
current.push_back(a[i]);
// 去除 current 的前导零（至少保留一位）
while (current.size() > 1 && current[0] == '0') {
current.erase(current.begin());
}
// 试商：从 9 到 0 尝试
int digit = 0;
for (int d = 9; d >= 0; d--) {
string temp = multiply(to_string(d), b); // 需要乘法函数
if (compare(temp, current) <= 0) {
digit = d;
current = subtract_for_div(current, temp);
break;
}
}
quotient.push_back(digit + '0');
}
// 去除商的前导零
while (quotient.size() > 1 && quotient[0] == '0') {
quotient.erase(quotient.begin());
}
// 去除余数的前导零
while (current.size() > 1 && current[0] == '0') {
current.erase(current.begin());
}
return {quotient, current};
}
关键注释：
current 表示正在处理的部分被除数性能瓶颈：
| 运算 | 核心难点 | 时间复杂度 | 关键优化点 |
|---|---|---|---|
| 加法 | 进位传递、最高位进位处理 | O(N) | 1. 统一进位变量 2. 避免反转操作 3. 预先分配结果空间 |
| 减法 | 借位传递、大小判断 | O(N) | 1. 避免反转 2. 批量借位处理 3. 延迟借位传播 |
| 乘法 | 错位相加、进位处理 | O(N²) | 1. Karatsuba 算法 (O(N^1.585)) 2. 压位存储 (减少循环次数) 3. FFT 优化 (O(N log N)) |
| 除法 | 试商策略、精度控制 | O(N²)~O(N³) | 1. 牛顿迭代法 (O(N²)) 2. 预处理倒数 3. Burnikel-Ziegler 分治算法 |
通过这四种基本运算的实现，可以完整掌握 String 正序存储的高精度计算方法，为后续学习更高效的 Vector 实现打下坚实基础。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online