教学向高精度运算的加、减、乘、除算法详解

Ne0inhk

— 15 min read
教学向高精度运算的加、减、乘、除算法详解

文章原件下载（markdown文件）https://gitcode.com/yun-xxx/blogArticle

教学向高精度运算的加、减、乘、除算法详解

概述

高精度运算处理超出内置整数类型范围的大数计算，通过模拟手算实现。核心挑战在于平衡效率与代码复杂度，形成从教学到竞赛再到工业应用的渐进式技术路线。

String正序存储（教学向）

存储结构：字符串顺序存储，下标0对应最高位
运用场景：

  • 算法入门教学
  • 简单脚本工具
  • 输入输出密集的轻量级应用

时间复杂度（n为数字位数）：

  • 加减法：O(n)，需反转或从末尾遍历
  • 朴素乘法：O(n²)
  • 朴素除法：O(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>usingnamespace 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;}

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

复杂度展示与分析

  • 时间复杂度 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>usingnamespace std;// 比较两个字符串数字大小boollessThan(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 >= bif(lessThan(a, b))return"-"+subtract(b, a);// 步骤2: 反转字符串，让个位在下标0reverse(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. 前导零的去除需要额外遍历

三、乘法算法

算法讲解/核心思想

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

核心过程：

c

关键点：

  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>usingnamespace 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');}}// 如果商为空，说明结果为0if(quotient.empty()) quotient ="0";return{quotient, remainder};}
高精度÷高精度版本
// 比较两个字符串数字intcompare(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. 频繁的字符串操作

五、综合比较与总结

算法特性对比

运算核心难点时间复杂度关键优化点
加法​进位传递、最高位进位处理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分治算法

教学建议

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

常见陷阱

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

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

Read more

天马G前端的使用

天马G前端的使用

1 复古掌机的选择 最近搞了个手柄，正好有一个闲置的小米9，就想着看能不能装一个复古掌机出来。 其实市场上也有很多现成的复古掌机，目前主要是安卓和Linux两种。整体上看安卓的目前占优一点，因为除了大家都能玩的模拟器，安卓平台还能玩安卓的游戏。 项目Android 掌机Linux 掌机 (ArkOS / JELOS / Batocera)启动速度20~40 秒5 秒以内UI一致性❌ 多 app 无统一样式✅ 完整游戏平台风格PS2（AetherSX2）✅ 可玩（Snapdragon / Dimensity / Unisoc）❌ 官方 Linux 版 core 不成熟Switch（Yuzu）✅ 安卓有社区版 Yuzu❌ 完全无解PSP/NDS/GBA etc✅ 但调用 APK，界面割裂✅ 全集成 Core，UI统一云游戏 / Steam Link✅ 完全支持⚠

By Ne0inhk
【Linux网络系列】：JSON+HTTP，用C++手搓一个web计算器服务器！

【Linux网络系列】：JSON+HTTP，用C++手搓一个web计算器服务器！

🔥 本文专栏：Linux网络Linux实践系列 🌸作者主页：努力努力再努力wz 💪 今日博客励志语录：别害怕选错，人生最遗憾的从不是‘选错了’，而是‘我本可以’。每一次推倒重来的勇气，都是在给灵魂贴上更坚韧的勋章。 ★★★ 本文前置知识： 序列化与反序列化 引入 在之前的博客中，我详细介绍了序列化 与反序列化 的概念。对于使用 TCP 协议进行通信的双方，由于 TCP 是面向字节流的，在发送数据之前，我们通常需要定义一种结构化的数据来描述传输内容，并以此作为数据的容器。在 C++ 中，这种结构化数据通常表现为对象或结构体。然而，我们不能直接将结构体内存中对应的字节原样发送到另一端，因为直接传递内存字节会引发字节序 和结构体内存对齐 的问题。不同平台、不同编译器所遵循的内存对齐规则可能不同，这可能导致接收方在解析结构体字段时出现错误。 因此，我们需要借助序列化 。序列化 是指将结构化的数据按照预定的规则转换为连续的字节流。其主要目的是屏蔽平台差异，使得位于不同平台的进程能够以统一的方式解析该字节流。序列化通常分为两种形式：文本序列化 与二进制序列化 。 文

By Ne0inhk

企业出海必备！Hunyuan-MT-7B-WEBUI实战应用分享

企业出海必备！Hunyuan-MT-7B-WEBUI实战应用分享 在跨境电商、海外本地化、国际内容分发加速落地的今天，语言障碍早已不是“能不能翻”的问题，而是“翻得准不准、快不快、安不安全、用不用得顺手”的综合考验。某深圳智能硬件公司为进入拉美市场，需在两周内完成300+页产品说明书、用户协议、营销文案的西语本地化；某新疆出版社正推进维吾尔语古籍数字化工程，亟需稳定、可私有部署的民汉互译能力；还有大量中小企业，既不愿将敏感商业文档上传至公有云翻译API，又缺乏专职AI运维人员——这些真实场景，共同指向一个被长期忽视的痛点：专业级翻译能力，不该被部署门槛锁死在实验室里。 Hunyuan-MT-7B-WEBUI 正是为此而生。它不是又一个需要配环境、调参数、查报错的模型仓库，而是一套开箱即用的企业级翻译服务系统：镜像一键拉起，脚本一键加载，浏览器一键访问。你不需要知道什么是FlashAttention，也不必纠结CUDA版本兼容性，更无需写一行推理代码——只要你会复制粘贴，就能立刻开始高质量多语种翻译。 1. 为什么企业出海特别需要它？从语言覆盖到交付方式的三重突破 很多团队评估

By Ne0inhk

WebMCP：浏览器AI交互新范式_20260213114222

一、WebMCP是什么 1. 基本定义 WebMCP（Web Model Context Protocol）是Google与Microsoft在W3C框架下联合推动的浏览器原生Web API，Chrome 146已推出早期预览版本，核心目标是让网页主动将自身能力封装为结构化工具，供AI Agent直接调用，解决当前Agent操作网页的稳定性与效率问题。 2. 核心思想 把交互从UI层搬到语义层：不再依赖按钮点击、坐标定位或DOM解析，而是让网页直接暴露"提交请假"“搜索航班”“加入购物车"等业务动作，形成结构化工具契约，Agent按契约调用而非"猜UI”。 3. 关键特性 * 双轨API设计：声明式API（HTML表单属性）+ 命令式API（JavaScript注册），兼顾易用性与灵活性 * 浏览器内运行：纯客户端实现，网页本身就是"工具服务器"，天然继承用户登录态与权限上下文 * 结构化上下文：

By Ne0inhk