
用 std::string 存大数,别碰 long long
超过 10¹⁸ 的整数,long long 就溢出了,C++ 标准库也没有内置大整数类型。硬塞进整型变量只会丢数据或触发未定义行为。必须换存储方式——字符串是最直接、最可控的选择。
常见错误现象:stoll("123456789012345678901234567890") 直接抛 std::out_of_range;或者用 unsigned long long 强转,结果是取模后的垃圾值。
- 所有输入先读成
std::string,后续逐位处理 - 去掉前导零,但保留单个
"0"(空字符串和全零要特殊判断) - 符号单独存为
bool is_negative,别混在字符串里做运算 - 加减法优先对齐低位(即反转字符串后从下标 0 开始算),比对齐高位更少出错
operator+ 和 operator- 模拟时怎么对齐位数
手动模拟竖式加减,核心是“右对齐+进位/借位”。很多人写反了顺序,把最高位当第一位去加,结果一串错。
使用场景:两个非负大整数相加/相减(符号逻辑另处理)
立即学习“C++免费学习笔记(深入)”;
- 先反转两个
std::string,让低位在前:reverse(a.begin(), a.end()) - 按索引从 0 到
max(a.size(), b.size())遍历,超出长度的按 0 补位 - 加法进位用
carry = (digit_a + digit_b + carry) / 10,当前位是% 10 - 减法借位要提前判断是否够减,不够就向高位借 10,且需标记该位已借过(避免重复借)
- 运算完再反转回来,再去除前导零
乘法为什么不能简单套两层 for 模拟竖式
能套,但容易漏掉进位叠加和结果数组初始化大小问题。最常见的 bug 是结果数组开太小,导致高位被截断。
参数差异:a * b 的位数最多是 a.size() + b.size(),不是 max(a.size(), b.size())
- 结果用
std::vector<int></int>存中间乘积,长度设为a.size() + b.size() - 双层循环:外层遍历
a每一位,内层遍历b每一位,位置映射为i + j(因为 10ⁱ × 10ʲ = 10ⁱ⁺ʲ) - 每次
res[i+j] += (a[i]-'0') * (b[j]-'0'),之后统一处理进位(从低位到高位) - 最后转字符串时跳过前导零,但若全零要返回
"0"
除法模拟最容易卡在“试商”和边界上
没有现成的“大数除法 API”,只能用减法逼近或二分试商。暴力减法在除数远小于被除数时极慢(比如 "1000000000000000000" / "3" 要减三亿次)。
性能影响:试商范围必须压缩。正确做法是取被除数的前若干位(至少和除数等长),转成 long long 做一次估算,再校正。
- 先特判除数为
"0"(抛异常或返回错误) - 比较被除数和除数大小用字符串长度+字典序,别转整数
- 试商时,取被除数最长前缀
s满足s.length() == divisor.length() || s.length() == divisor.length()+1 - 把
s和divisor转成long long算初商(注意别超限),再用这个初商去乘除数、和原前缀比较并调整 - 每轮减完更新被除数字符串,继续下一位——这步的字符串擦除和拼接要小心,建议用
substr++=控制
真正麻烦的是各种边界:除数比被除数长、结果为 0、有前导零、负号组合。这些不写满测试用例根本压不住。










