C++大数模板(推荐)

前言

内置整数类型能表示的范围由位数决定：long long通常是 64 位，能存到约 9.2×10^18。阶乘 21 就溢出了，更不用说密码学或组合计数里的几百位数字。所谓「大数模板」，就是用一个容器按位存储数字，自己实现加减乘除，把位数上限交给内存而不是类型宽度。

需要先澄清一点：C++ 标准库没有内置的任意精度整数类型。标题里的「模板」指一段可复用的代码模板（类模板），不是语言层面的某种特殊机制，也不是标准库组件。C++ 项目若不想手写，可以用成熟的多精度库，但那属于第三方依赖，API 以其官方文档为准。

本文给出一个基于std::vector<int>的无符号大整数类模板，支持任意进制存储、字符串互转、比较、加减乘。重点讲清进位与借位的边界、前导零的处理、以及竖式乘法的复杂度。代码以 C++17 为基准，逐行按标准语义推演，不依赖任何编译期扩展。

一、表示方式：为什么按位存

大整数有两种常见存法：

本文选第二种，并把「基」做成模板参数，默认十进制。数字按小端序存放：digits_[0]是个位，digits_[1]是十位，以此类推。小端序的好处是进位从下标 0 向高位传播，扩容只需push_back，不需要整体搬移。

类的不变量有两条：

1. 
   
2. digits_永不为空，至少含一个元素；
3. 
   
4. 最高位（digits_.back()）不为 0，除非整个数就是 0。
5. 
   

只要构造函数和每个运算都维护这两条，比较和输出就可以写得非常简单。前导零是大数实现里最常见的 bug 来源：10 - 10如果留下一个0没问题，但100 - 99若产生[1, 0, 0]就会在比较和输出时出错。

二、模板参数、构造与比较

模板参数Base限定在 2 到 36，这样每一位都能用0-9、a-z表示，字符串互转不需要额外的映射表。构造时从字符串读入，逐字符校验并反转：

// 适用于 C++17
explicit BigUInt(const std::string& text) {
if (text.empty()) {
digits_.push_back(0);
return;
}
for (char c : text) {
const int value = digit_value(c);
if (value < 0 || value >= Base) {
throw std::invalid_argument("digit out of range for base");
}
digits_.push_back(value);
}
std::reverse(digits_.begin(), digits_.end());
trim();
}

从unsigned long long构造则反复取余、整除。这一步的循环次数等于该数在目标进制下的位数，对 64 位输入最多几十次，代价可以忽略。

trim()负责去掉高位的零，并保证容器非空：

// 适用于 C++17
void trim() {
while (digits_.size() > 1 && digits_.back() == 0) {
digits_.pop_back();
}
if (digits_.empty()) {
digits_.push_back(0);
}
}

在「无前导零」的不变量下，两个非负数的比较可以分两步：位数多的更大；位数相同则从最高位向低位找第一个不同的位。这比逐位转换成数值再比要快，也不会有溢出问题。

// 适用于 C++17
int compare(const BigUInt& other) const {
if (digits_.size() != other.digits_.size()) {
return digits_.size() < other.digits_.size() ? -1 : 1;
}
for (std::size_t i = digits_.size(); i-- > 0;) {
if (digits_[i] != other.digits_[i]) {
return digits_[i] < other.digits_[i] ? -1 : 1;
}
}
return 0;
}

注意循环写成i-- > 0：当i为std::size_t（无符号）时，i >= 0永远为真，递减到 0 后再减会回绕成最大值。i-- > 0在i == 0时先用 0 比较、再递减，循环正确结束。

三、加减乘：竖式与进位

加法逐位相加，进位最多为 1（因为每位最大Base-1，两个相加再加进位不超过2*Base-1）。结果长度最多比操作数多一位。

减法要求被减数不小于减数，否则结果没有意义。逐位相减，不够就向高位借 1，借位同样是 0 或 1。实现里用前置条件检查避免「算出负数却当成无符号」的错误。

乘法用学校教的竖式：对乘数每一位，与被乘数每一位相乘，累加到结果的对应下标。两个n位数相乘，结果最多2n位，循环是 O(n²)。这是最直观的算法；位数上千时可以考虑 Karatsuba 或基于 FFT 的算法，但实现复杂度高得多，先保证正确性更重要。

// 适用于 C++17
BigUInt operator*(const BigUInt& rhs) const {
BigUInt result;
result.digits_.assign(digits_.size() + rhs.digits_.size(), 0);

for (std::size_t i = 0; i < digits_.size(); ++i) {
long long carry = 0;
for (std::size_t j = 0; j < rhs.digits_.size(); ++j) {
const long long cur = 1LL * digits_[i] * rhs.digits_[j]
+ result.digits_[i + j] + carry;
result.digits_[i + j] = static_cast<int>(cur % Base);
carry = cur / Base;
}
std::size_t k = i + rhs.digits_.size();
while (carry > 0) {
const long long cur = result.digits_[k] + carry;
result.digits_[k] = static_cast<int>(cur % Base);
carry = cur / Base;
++k;
}
}
result.trim();
return result;
}

这里用long long暂存中间结果。每位乘积最大(Base-1)²，加上结果位与进位，在Base ≤ 36时远小于long long的上限，不会溢出。如果想把基提高到10^9，就必须换用unsigned long long并重新核算上界。

四、完整实现

// 适用于 C++17
#include <algorithm>
#include <cstddef>
#include <ostream>
#include <stdexcept>
#include <string>
#include <vector>

template <int Base = 10>
class BigUInt {
static_assert(Base >= 2 && Base <= 36, "Base must be in [2, 36]");

public:
BigUInt() { digits_.push_back(0); }

explicit BigUInt(unsigned long long value) {
if (value == 0) {
digits_.push_back(0);
return;
}
while (value > 0) {
digits_.push_back(static_cast<int>(value % Base));
value /= Base;
}
}

explicit BigUInt(const std::string& text) {
if (text.empty()) {
digits_.push_back(0);
return;
}
for (char c : text) {
const int value = digit_value(c);
if (value < 0 || value >= Base) {
throw std::invalid_argument("digit out of range for base");
}
digits_.push_back(value);
}
std::reverse(digits_.begin(), digits_.end());
trim();
}

std::string str() const {
std::string out;
out.reserve(digits_.size());
for (std::size_t i = digits_.size(); i-- > 0;) {
out.push_back(digit_char(digits_[i]));
}
return out;
}

int compare(const BigUInt& other) const {
if (digits_.size() != other.digits_.size()) {
return digits_.size() < other.digits_.size() ? -1 : 1;
}
for (std::size_t i = digits_.size(); i-- > 0;) {
if (digits_[i] != other.digits_[i]) {
return digits_[i] < other.digits_[i] ? -1 : 1;
}
}
return 0;
}

BigUInt& operator+=(const BigUInt& rhs) {
const std::size_t n = std::max(digits_.size(), rhs.digits_.size());
digits_.resize(n, 0);
int carry = 0;
for (std::size_t i = 0; i < n; ++i) {
int cur = digits_[i] + carry;
if (i < rhs.digits_.size()) {
cur += rhs.digits_[i];
}
digits_[i] = cur % Base;
carry = cur / Base;
}
if (carry != 0) {
digits_.push_back(carry);
}
return *this;
}

BigUInt& operator-=(const BigUInt& rhs) {
if (compare(rhs) < 0) {
throw std::invalid_argument("negative result is not supported");
}
int borrow = 0;
for (std::size_t i = 0; i < digits_.size(); ++i) {
int cur = digits_[i] - borrow;
if (i < rhs.digits_.size()) {
cur -= rhs.digits_[i];
}
if (cur < 0) {
cur += Base;
borrow = 1;
} else {
borrow = 0;
}
digits_[i] = cur;
}
trim();
return *this;
}

BigUInt& operator*=(const BigUInt& rhs) {
*this = *this * rhs;
return *this;
}

friend BigUInt operator+(BigUInt lhs, const BigUInt& rhs) {
lhs += rhs;
return lhs;
}

friend BigUInt operator-(BigUInt lhs, const BigUInt& rhs) {
lhs -= rhs;
return lhs;
}

friend BigUInt operator*(const BigUInt& lhs, const BigUInt& rhs) {
BigUInt result;
result.digits_.assign(lhs.digits_.size() + rhs.digits_.size(), 0);

for (std::size_t i = 0; i < lhs.digits_.size(); ++i) {
long long carry = 0;
for (std::size_t j = 0; j < rhs.digits_.size(); ++j) {
const long long cur = 1LL * lhs.digits_[i] * rhs.digits_[j]
+ result.digits_[i + j] + carry;
result.digits_[i + j] = static_cast<int>(cur % Base);
carry = cur / Base;
}
std::size_t k = i + rhs.digits_.size();
while (carry > 0) {
const long long cur = result.digits_[k] + carry;
result.digits_[k] = static_cast<int>(cur % Base);
carry = cur / Base;
++k;
}
}
result.trim();
return result;
}

friend bool operator==(const BigUInt& a, const BigUInt& b) {
return a.compare(b) == 0;
}

friend bool operator!=(const BigUInt& a, const BigUInt& b) {
return a.compare(b) != 0;
}

friend bool operator<(const BigUInt& a, const BigUInt& b) {
return a.compare(b) < 0;
}

friend std::ostream& operator<<(std::ostream& os, const BigUInt& value) {
return os << value.str();
}

private:
static int digit_value(char c) {
if (c >= '0' && c <= '9') return c - '0';
if (c >= 'a' && c <= 'z') return c - 'a' + 10;
if (c >= 'A' && c <= 'Z') return c - 'A' + 10;
return -1;
}

static char digit_char(int digit) {
return digit < 10 ? static_cast<char>('0' + digit)
: static_cast<char>('a' + digit - 10);
}

void trim() {
while (digits_.size() > 1 && digits_.back() == 0) {
digits_.pop_back();
}
if (digits_.empty()) {
digits_.push_back(0);
}
}

std::vector<int> digits_; // 小端序，digits_[0] 是最低位
};

template <int Base>
BigUInt<Base> factorial(unsigned n) {
BigUInt<Base> result(1ULL);
for (unsigned i = 2; i <= n; ++i) {
result *= BigUInt<Base>(i);
}
return result;
}

使用示例：

// 适用于 C++17
#include <iostream>

int main() {
BigUInt<> a("12345678901234567890");
BigUInt<> b(987654321ULL);

std::cout << a + b << '\n';
std::cout << a * b << '\n';
std::cout << factorial<10>(30) << '\n';

BigUInt<> c("100000000000000000000");
c -= BigUInt<>("1");
std::cout << c << '\n'; // 99999999999999999999
return 0;
}

BigUInt<>使用默认的十进制。若改成BigUInt<16>，字符串输入输出就是十六进制表示，内部运算仍然一致。

常见坑点

1. 
   
2. ❌ 用int存中间乘积，Base稍大就溢出。
3. 
   

✅ 中间结果用long long，并核算(Base-1)² + Base的上界。

1. 
   
2. ❌ 减法不检查大小关系，直接逐位借位。
3. 
   

✅ 先compare，被减数小于减数时抛异常或改用有符号表示。

1. 
   
2. ❌ 忘记去掉高位的前导零，导致比较与输出错误。
3. 
   

✅ 每个可能产生新长度的运算后调用trim()，并保证容器非空。

1. 
   
2. ❌ 用for (std::size_t i = v.size() - 1; i >= 0; --i)倒序遍历。
3. 
   

✅ 无符号数会回绕；用i-- > 0或反向迭代器。

1. 
   
2. ❌ 乘法结果数组只分配n位，进位写到界外。
3. 
   

✅ 结果至少分配lhs.size() + rhs.size()位。

1. 
   
2. ❌ 把大数当有符号数用，却只实现了无符号运算。
3. 
   

✅ 本文的实现只支持非负整数；需要负数时单独维护符号位并重写比较与加减。

1. 
   
2. ❌ 认为operator*是 O(n)，在上万位时直接调用。
3. 
   

✅ 竖式乘法是 O(n²)；位数很大时应换 Karatsuba 等算法或成熟库。

总结

大数实现的难点不在算法思想，而在边界：空容器、前导零、无符号回溯、乘法结果长度、中间值溢出。把这几个不变量守住，一份几百行的类模板就能覆盖阶乘、斐波那契、组合数等常见需求。真到需要除法、取模或上千位乘法的场景，再考虑专用库会更划算。