高精度运算的加减乘除算法详解

关键注释：

• 两次反转：运算前反转以获得正确的计算顺序，运算后反转以恢复阅读顺序。这是该方法的性能瓶颈。
• 字符与数字转换：通过 - '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;
}

优化点：避免了输入字符串的显式反转，但结果仍需一次反转。运算逻辑更直观地与'从个位开始'相匹配。

复杂度展示与分析

• 时间复杂度 O(N)：
  • 朴素版本：两次完整反转 O(N) + 一次逐位相加 O(N) = O(3N) ≈ O(N)。
  • 优化变体：一次逐位相加 O(N) + 一次结果反转 O(N) = O(2N) ≈ O(N)。
  • 分析：虽然都是线性复杂度，但常数因子较大。反转操作和字符/数字转换是主要开销。
• 空间复杂度 O(N)：需要额外的字符串存储结果。

性能痛点：

1. 反转开销：必须进行至少一次 O(N) 反转。
2. 存储低效：一个 char（通常 1 字节）仅存储一位数字（0-9），利用率低。
3. 转换开销：频繁的 ± '0' 操作。

二、减法算法

算法讲解/核心思想

本质：模拟列竖式减法，从低位到高位逐位相减，不够减时向高位借位。 核心挑战：

1. 判断大小关系（确保被减数≥减数）
2. 处理借位传递
3. 去除结果前导零

借位机制：当当前位不够减时，从左边高位借 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 变量记录是否向上一位借位，影响当前位的被减数。
• 大小判断：必须先确保被减数≥减数，否则结果为负。
• 补零对齐：确保两个数字位数相同，方便逐位计算。

复杂度分析

• 时间复杂度 O(N)：需要遍历所有 N 位数字，每次处理常数时间操作。
• 空间复杂度 O(N)：存储结果字符串。

性能瓶颈：

1. 两次字符串反转操作
2. 字符与数字的频繁转换
3. 前导零的去除需要额外遍历

三、乘法算法

算法讲解/核心思想

本质：模拟"竖式乘法"，将乘数的每一位与被乘数相乘，再将结果错位相加。

关键点：

1. 中间结果需要左移（补零）
2. 处理进位
3. 累加多个中间结果

详细步骤（以 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";
}

优化点：

1. 直接操作字符串：避免 vector 到 string 的转换
2. 原地更新：在结果字符串上直接修改
3. 预分配：一次分配足够空间

复杂度分析

• 时间复杂度 O(N²)：两层循环，N 为总位数。
• 空间复杂度 O(N+M)：存储中间结果。

性能分析：

• 朴素版本：每个数字位都要相乘，共 N×M 次乘法
• 无法避免 O(N²) 复杂度，但优化版本常数更小

四、除法算法

算法讲解/核心思想

本质：模拟"长除法"，逐位试商，从被除数高位开始，每次取出一部分与除数比较。

核心过程（以 1234 ÷ 12 为例）：

  102 ← 商
------
12)1234
-12 ← 12×1=12
---
 34
-24 ← 12×2=24
---
 10 ← 余数

试商方法：

1. 从被除数高位取与除数相同位数的数字
2. 估算商（通常用前两位/除数第一位）
3. 调整商（可能偏大需要减 1）

详细步骤（以 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};
}

关键注释：

• 试商策略：从 9 到 0 尝试，找到最大满足条件的商
• 当前部分：维护 current 表示正在处理的部分被除数
• 前导零处理：商和余数都需要去除前导零

复杂度分析

• 时间复杂度：
  • 低精度除法：O(N)，N 为被除数位数
  • 高精度除法：O(N×M×K)，N 是被除数位数，M 是除数位数，K 是试商次数（最多 10 次）
• 空间复杂度 O(N+M)：存储商和中间结果

性能瓶颈：

1. 高精度除法中的试商循环（最多 10 次尝试）
2. 每次试商需要做一次乘法和一次比较
3. 频繁的字符串操作

五、综合比较与总结

算法特性对比

教学建议

1. 先理解后优化：先用 String 实现理解原理，再用 Vector 优化提升效率
2. 分步调试：对于复杂算法（如高精度除法），用简单例子分步验证
3. 边界测试：特别注意 0、1、进位、借位等边界情况

常见陷阱

1. 前导零问题：结果可能有多余的 0，需要正确去除
2. 负数处理：减法可能产生负数，需要扩展支持
3. 溢出风险：中间计算可能超出 int 范围，需要用 long long
4. 空字符串：除零错误、空输入需要特殊处理

通过这四种基本运算的实现，可以完整掌握 String 正序存储的高精度计算方法，为后续学习更高效的 Vector 实现打下坚实基础。