前言

C++ 内置的整数类型有明确的上限：long long至少 64 位，能表示的最大无符号值约为 1.8×10¹⁹，也就是 20 位十进制数。计算阶乘、处理加密参数、做大数幂运算时，结果动辄几百上千位，内置类型完全不够用。大数相乘（big integer multiplication）就是用数组或字符串模拟手算竖式的过程。

初学时的典型误解有三个。第一是以为把每一位存进int数组就万事大吉，结果在进位时用int承接乘积，两个 9 位数相乘直接溢出。第二是以为「一位存一个十进制数字」是唯一做法，于是数组长度是结果位数的十倍，循环次数也成倍增加。第三是忽略符号与小数点，把「大整数」和「大实数」混为一谈，遇到负数或小数就无从下手。

本文从竖式乘法的进位规律讲起，说明为什么用 10⁹ 作为基数（limb），给出一个可直接使用的小端存储实现，最后讨论 Karatsuba、FFT 等更快的算法以及符号处理。代码以 C++17 为基准。

一、竖式乘法的结构

手算123 × 45的过程是：用 5 依次乘 123 的每一位，得到一个部分积；用 4 乘 123 的每一位，左移一位后相加。写成程序，就是双重循环：外层遍历乘数的每一位，内层遍历被乘数的每一位，把乘积累加到结果的对应位置。

设a有 n 位、b有 m 位，结果的第i + j位累加a[i] * b[j]。所有乘积累加完毕后再统一处理进位，这是最清晰的写法：先把「乘」和「进位」分开，避免在同一个循环里既算乘积又处理进位，逻辑纠缠在一起。

这里有一个关键的选择：基数取多大。如果一位存一个十进制数字，基数是 10，那么每次乘法的结果最大是 81，加上进位也不会溢出；但数组长度等于十进制位数，一个 1000 位的数需要 1000 个元素。如果基数取 10⁹，每个元素存 9 位十进制，数组长度缩短为约 1/9，而两个 10⁹ 以下的数相乘最大约 10¹⁸，用 64 位整数承接绰绰有余。

10⁹ 是一个恰到好处的选择：它小于 2³⁰，两个这样的数相乘小于 2⁶⁰，再加上进位也不超过 64 位；同时它又是 10 的幂，输出时可以按 9 位一组直接拼接，不需要做进制转换。用 2³² 作基数虽然更贴近机器字长，但输出时要反复除以 10，反而更麻烦。

二、存储方向与进位

大数在数组里通常采用小端存储：下标 0 存最低位。这样做的好处是「进位向高位走」对应「下标增大」，push_back就能扩展，不需要在头部插入。如果反过来用大端存储，每次进位都要往前挪，或者在头部insert，复杂度立刻退化。

进位的处理有两种风格。第一种是边乘边进位：内层循环里算出cur = result[i+j] + a[i]*b[j] + carry，立刻取模写回、更新 carry。第二种是先累加所有乘积，最后统一从低到高扫一遍做进位。第一种更省内存，因为result的每个元素始终小于基数；第二种写起来更直观，但中间值可能累积得很大，需要保证累加用的类型足够宽。

本文采用第一种。要注意carry在每轮内层循环结束后可能还有剩余，需要继续向更高位传播，直到 carry 为 0。传播时也要取模，因为高位的result可能已经有值。

清零与长度处理是另一个易错点。结果数组的长度应当是n + m，两个 n 位和 m 位的数相乘，结果最多 n+m 位。乘完之后高位可能是 0，必须从尾部去掉，否则输出会带前导零；如果结果本身就是 0，所有位都是 0，去掉之后数组为空，输出时需要特判成"0"。

三、完整实现

// 适用于 C++17
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

using Limbs = std::vector<std::uint32_t>; // 小端，每个元素存 9 位十进制

constexpr std::uint32_t kBase = 1000000000u;

Limbs from_string(const std::string& s) {
Limbs out;
for (int end = static_cast<int>(s.size()); end > 0; end -= 9) {
const int begin = std::max(0, end - 9);
out.push_back(static_cast<std::uint32_t>(
std::stoul(s.substr(static_cast<std::size_t>(begin),
static_cast<std::size_t>(end - begin)))));
}
return out;
}

Limbs multiply(const Limbs& a, const Limbs& b) {
if (a.empty() || b.empty()) {
return {};
}
std::vector<std::uint64_t> acc(a.size() + b.size(), 0);
for (std::size_t i = 0; i < a.size(); ++i) {
std::uint64_t carry = 0;
for (std::size_t j = 0; j < b.size(); ++j) {
const std::uint64_t cur = acc[i + j]
+ static_cast<std::uint64_t>(a[i]) * b[j]
+ carry;
acc[i + j] = cur % kBase;
carry = cur / kBase;
}
std::size_t k = i + b.size();
while (carry != 0) {
const std::uint64_t cur = acc[k] + carry;
acc[k] = cur % kBase;
carry = cur / kBase;
++k;
}
}
Limbs out(acc.begin(), acc.end());
while (!out.empty() && out.back() == 0) {
out.pop_back();
}
return out;
}

std::string to_string(const Limbs& v) {
if (v.empty()) {
return "0";
}
std::string s = std::to_string(v.back());
for (std::size_t i = v.size() - 1; i-- > 0;) {
const std::string part = std::to_string(v[i]);
s.append(9 - part.size(), '0'); // 非最高位补足 9 位
s += part;
}
return s;
}

int main() {
const std::string x = "123456789012345678901234567890";
const std::string y = "987654321098765432109876543210";
std::cout << to_string(multiply(from_string(x), from_string(y))) << '\n';
return 0;
}

几个地方值得核一遍。

from_string从字符串末尾开始，每次取最多 9 个字符转成unsigned long。std::stoul对 9 位十进制（最大 999999999）不会溢出 32 位无符号类型，转成std::uint32_t是安全的。如果分组长度写成 10，就会超出std::uint32_t的范围，必须改用std::stoull。

multiply里acc用std::uint64_t是为了容纳a[i] * b[j]（最大约 10¹⁸）加上已有值和进位。这三个数相加仍小于 2⁶⁴，不会溢出。若把acc声明成std::uint32_t，乘积会先被截断，结果完全错误。

内层循环结束后，进位写到i + b.size()这个位置。最坏情况下i取a.size() - 1，写入位置是a.size() + b.size() - 1，正好是acc的最后一个下标，不会越界。while里继续向高位传播时，最后一个位置的值是 0、进位最多为 1，写完就归零，因此不会越界到acc.end()。

to_string里的循环for (std::size_t i = v.size() - 1; i-- > 0;)是一个需要小心的写法：它从size()-2开始，一直处理到下标 0，靠的是「先用旧值判断、再自减」。如果写成i >= 0配合无符号数，就会死循环。9 - part.size()里part.size()最大是 9，不会下溢。

四、复杂度、符号与更快的方法

朴素竖式乘法的复杂度是 O(n·m)，n 和 m 是 limb 的个数，也就是十进制的约 1/9。两个一千位的数相乘，大约需要 111×111 次乘加，非常轻松；两个一百万位的数相乘，就要 10¹⁰ 次运算，这时必须换算法。

Karatsuba 算法把一次 n×n 的乘法拆成三次 n/2 规模的乘法，递推式 T(n) = 3T(n/2) + O(n)，解得 O(n^log₂3) ≈ O(n^1.585)。它在 n 达到几百位时开始有优势，代价是实现复杂、常数因子大、需要处理负数中间结果。再往上还有基于快速傅里叶变换的算法，复杂度接近 O(n log n)，但只有在数万位以上才划算。实际工程里如果真需要这种规模，直接用 GMP 之类的成熟库，不要自己写。

符号处理应当放在最外层：先判断两个操作数的符号，用绝对值做乘法，最后根据「同号为正、异号为负」补上符号。把一个符号位塞进 limb 数组里，会让每一处进位逻辑都要考虑正负，得不偿失。

小数则完全是另一套问题。定点小数可以记录小数点位置，乘完之后调整；浮点大数需要更复杂的表示。题目说「大数相乘」时，默认指的是整数，遇到小数要先和出题人确认。

常见坑点

坑点一：用 32 位整数承接乘积。

❌std::uint32_t cur = a[i] * b[j] + carry;两个接近 10⁹ 的数相乘约 10¹⁸，直接溢出。

✅ 用std::uint64_t承接中间结果，只在写回时截断到基数以内。

坑点二：基数选 10⁹，却用int存结果。

❌int acc[...]，int在常见平台上是 32 位有符号，最大约 2.1×10⁹，装不下乘积。

✅ 用std::uint64_t或至少std::uint32_t存 limb，累加用 64 位。

坑点三：忘记去掉高位的前导零。

❌ 两个 3 位数相乘得到 6 个 limb，实际结果只有 4 位，输出成了001234。

✅ 从尾部pop_back掉所有值为 0 的 limb，注意保留至少一个表示 0。

坑点四：结果为零时返回空数组，输出成空串。

❌to_string直接遍历空数组，得到空字符串。

✅ 空数组特判返回"0"，或者在乘法入口就处理零操作数。

坑点五：大端存储并在头部插入。

❌ 每次进位都out.insert(out.begin(), carry)，单次 O(n)，整体退化成 O(n²) 的额外开销。

✅ 小端存储，进位向尾部追加，最后输出时反向遍历。

坑点六：用std::stoi解析 9 位以上的分组。

❌std::stoi(s.substr(i, 18))，超出int范围，抛出std::out_of_range。

✅ 分组长度不超过 9，或用std::stoull并确认分组长度。

坑点七：把符号塞进 limb。

❌ 用负的 limb 表示负数，导致取模、进位、比较全部要改。

✅ limb 一律非负，符号单独用一个bool或int保存。

坑点八：把「大数相乘」当成「大数加法」处理。

❌ 只处理了同长度、无进位的简单情况，位数不同时下标越界。

✅ 结果数组开n + m，用i + j定位，双层循环覆盖所有组合。

总结

大数相乘的代码不长，错误几乎都集中在类型宽度和边界上：乘积用什么承接、进位往哪写、结果长度开多少、零怎么表示。把这四个问题在动手前想清楚，再用手算的小例子逐位对一遍中间数组，比写完再调试快得多。