C++大数模板(推荐)

前言内置整数类型能表示的范围由位数决定long long通常是 64 位能存到约 9.2×10^18。阶乘 21 就溢出了更不用说密码学或组合计数里的几百位数字。所谓「大数模板」就是用一个容器按位存储数字自己实现加减乘除把位数上限交给内存而不是类型宽度。需要先澄清一点C 标准库没有内置的任意精度整数类型。标题里的「模板」指一段可复用的代码模板类模板不是语言层面的某种特殊机制也不是标准库组件。C 项目若不想手写可以用成熟的多精度库但那属于第三方依赖API 以其官方文档为准。本文给出一个基于std::vectorint的无符号大整数类模板支持任意进制存储、字符串互转、比较、加减乘。重点讲清进位与借位的边界、前导零的处理、以及竖式乘法的复杂度。代码以 C17 为基准逐行按标准语义推演不依赖任何编译期扩展。一、表示方式为什么按位存大整数有两种常见存法方案优点缺点std::string存十进制字符实现直观输入输出方便每位只利用 4 bit运算时要频繁字符与数值互转std::vectorint存「位」运算直接进制可调需要自己处理进位、前导零、输出转换以 10^9 为基的vectoruint32_t空间利用率高乘法循环少进位与溢出分析更复杂本文选第二种并把「基」做成模板参数默认十进制。数字按小端序存放digits_[0]是个位digits_[1]是十位以此类推。小端序的好处是进位从下标 0 向高位传播扩容只需push_back不需要整体搬移。类的不变量有两条digits_永不为空至少含一个元素最高位digits_.back()不为 0除非整个数就是 0。只要构造函数和每个运算都维护这两条比较和输出就可以写得非常简单。前导零是大数实现里最常见的 bug 来源10 - 10如果留下一个0没问题但100 - 99若产生[1, 0, 0]就会在比较和输出时出错。二、模板参数、构造与比较模板参数Base限定在 2 到 36这样每一位都能用0-9、a-z表示字符串互转不需要额外的映射表。构造时从字符串读入逐字符校验并反转// 适用于 C17explicit 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()负责去掉高位的零并保证容器非空// 适用于 C17void trim() {while (digits_.size() 1 digits_.back() 0) {digits_.pop_back();}if (digits_.empty()) {digits_.push_back(0);}}在「无前导零」的不变量下两个非负数的比较可以分两步位数多的更大位数相同则从最高位向低位找第一个不同的位。这比逐位转换成数值再比要快也不会有溢出问题。// 适用于 C17int 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 的算法但实现复杂度高得多先保证正确性更重要。// 适用于 C17BigUInt 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_castint(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_castint(cur % Base);carry cur / Base;k;}}result.trim();return result;}这里用long long暂存中间结果。每位乘积最大(Base-1)²加上结果位与进位在Base ≤ 36时远小于long long的上限不会溢出。如果想把基提高到10^9就必须换用unsigned long long并重新核算上界。四、完整实现// 适用于 C17#include algorithm#include cstddef#include ostream#include stdexcept#include string#include vectortemplate int Base 10class 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_castint(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_castint(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_castint(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_castchar(0 digit): static_castchar(a digit - 10);}void trim() {while (digits_.size() 1 digits_.back() 0) {digits_.pop_back();}if (digits_.empty()) {digits_.push_back(0);}}std::vectorint digits_; // 小端序digits_[0] 是最低位};template int BaseBigUIntBase factorial(unsigned n) {BigUIntBase result(1ULL);for (unsigned i 2; i n; i) {result * BigUIntBase(i);}return result;}使用示例// 适用于 C17#include iostreamint main() {BigUInt a(12345678901234567890);BigUInt b(987654321ULL);std::cout a b \n;std::cout a * b \n;std::cout factorial10(30) \n;BigUInt c(100000000000000000000);c - BigUInt(1);std::cout c \n; // 99999999999999999999return 0;}BigUInt使用默认的十进制。若改成BigUInt16字符串输入输出就是十六进制表示内部运算仍然一致。常见坑点❌ 用int存中间乘积Base稍大就溢出。✅ 中间结果用long long并核算(Base-1)² Base的上界。❌ 减法不检查大小关系直接逐位借位。✅ 先compare被减数小于减数时抛异常或改用有符号表示。❌ 忘记去掉高位的前导零导致比较与输出错误。✅ 每个可能产生新长度的运算后调用trim()并保证容器非空。❌ 用for (std::size_t i v.size() - 1; i 0; --i)倒序遍历。✅ 无符号数会回绕用i-- 0或反向迭代器。❌ 乘法结果数组只分配n位进位写到界外。✅ 结果至少分配lhs.size() rhs.size()位。❌ 把大数当有符号数用却只实现了无符号运算。✅ 本文的实现只支持非负整数需要负数时单独维护符号位并重写比较与加减。❌ 认为operator*是 O(n)在上万位时直接调用。✅ 竖式乘法是 O(n²)位数很大时应换 Karatsuba 等算法或成熟库。总结设计点选择理由存储std::vectorint小端序进位向高位传播扩容方便不变量非空、无前导零简化比较与输出加法/减法O(n)进位/借位 0 或 1逐位处理即可乘法O(n²) 竖式实现简单逐位推演即可检查输入输出按Base映射字符支持 2 到 36 进制符号仅非负有符号需要额外符号位与规则大数实现的难点不在算法思想而在边界空容器、前导零、无符号回溯、乘法结果长度、中间值溢出。把这几个不变量守住一份几百行的类模板就能覆盖阶乘、斐波那契、组合数等常见需求。真到需要除法、取模或上千位乘法的场景再考虑专用库会更划算。