大数运算课程设计源码：手写任意精度加减乘除幂模，彻底解决long long溢出

简介：这份数据结构课程设计资源聚焦大数运算的完整实现，面向计算机专业学生、算法初学者及需要处理超长数值的开发者。项目覆盖大数加法、减法、乘法、除法、乘方与取模六类核心操作，并同时支持十进制与二进制大数运算，可应用于密码学、高性能计算等场景，帮助读者理解数组存储、进位借位、快速幂与长除法等关键算法。资源包共35个文件，以17个txt测试数据与结果文件、5个Python验证脚本、2个C++源码及头文件为主，另含可执行程序与工程配置，压缩包约22.24MB，目录结构清晰，便于对照源码与测试用例逐项验证。目前已有1353人学习下载。读者可获取完整源代码、验证数据与Python对照脚本，通过阅读BigInteger相关实现与多组输入输出样例，掌握大数运算的工程化写法与调试思路，适合作为课程设计参考或算法练习素材。

1. 大数运算课程设计：从“爆 long long”到任意精度计算，这套源码把加减乘除幂模全包了

如果你写过阶乘、斐波那契或者 RSA 的入门作业，大概率见过这个场景：输入 100，程序输出一个负数或者 0。原因不玄学，就是long long溢出了。C/C++ 里最大的内置整数类型也就 64 位，能表示的范围在 20 位十进制数左右，而 100 的阶乘有 158 位。这个课程设计要解决的就是这类问题——不依赖任何第三方大数库，用数据结构课上学到的链表、动态数组、字符串处理，手写一套支持任意长度十进制和二进制的大数运算库，覆盖加法、减法、乘法、除法、乘方、取模六个核心运算。适合正在做数据结构课程设计的学生，也适合想理解大数底层实现、不想只调 API 的开发者。下面从项目结构、核心算法到编译运行，完整拆一遍。

2. 项目结构与技术选型：为什么用字符串+动态数组而不是链表

2.1 整体目录布局

拿到源码包后，先看目录结构。这类课程设计通常不会太复杂，但组织方式直接决定了你后面改代码顺不顺手。一个典型的布局如下：

bignum/ ├── include/ │ ├── bignum.h # 大数结构体定义与函数声明 │ └── base_convert.h # 进制转换接口 ├── src/ │ ├── bignum.c # 核心运算实现 │ ├── add_sub.c # 加减法 │ ├── mul_div.c # 乘除法 │ ├── power_mod.c # 乘方与取模 │ └── base_convert.c # 十进制/二进制互转 ├── tests/ │ ├── test_add.c │ ├── test_mul.c │ └── test_all.c ├── Makefile └── README.md

include/放头文件，src/放实现，tests/放测试用例，Makefile统一编译。这种分法在课程设计里算比较规范的，好处是加减法和乘除法分开编译，改一个模块不会牵动全部。如果你的源码包结构不同，比如所有代码堆在一个main.c里，也不用慌，核心逻辑是一样的，只是找函数麻烦一点。

2.2 大数的数据结构设计

大数运算的第一个决策是：怎么存一个超长整数？常见方案有三种——字符串、动态数组、链表。这个项目用的是字符串存储十进制 + 动态数组存储二进制的混合方案。先看核心结构体：

// include/bignum.h #define MAX_DIGITS 10000 // 最大位数，按需调整 typedef struct { int sign; // 符号：0 正，1 负 int base; // 进制：10 或 2 int len; // 当前有效位数 char digits[MAX_DIGITS]; // 低位在前，digits[0] 是个位 } BigNum;

这里有几个设计点值得说清楚：

低位在前存储。digits[0]存个位，digits[1]存十位，依次往后。为什么反过来？因为加减乘除都是从低位往高位算的，进位也是往高位走。如果高位在前，每次进位都要移动整个数组，时间复杂度直接爆炸。低位在前的话，进位只需要digits[i+1]++，O(1) 操作。

符号单独存。不要用补码那套，大数运算里补码会让除法变得极其恶心。单独用一个sign字段，运算时先判断符号再决定用加法还是减法，逻辑清晰得多。

base 字段区分进制。十进制和二进制共用同一个结构体，运算时根据base决定进位阈值——十进制逢十进一，二进制逢二进一。这样加法和乘法的核心代码只需要改一个常量，不用写两套。

固定数组 vs 动态分配。这里用了固定大小的char digits[MAX_DIGITS]，好处是实现简单、不用管内存释放，坏处是每个 BigNum 占 10KB 栈空间，开多了会爆栈。常见做法是改成char *digits加malloc，但课程设计里为了代码可读性，固定数组也能接受。如果你要算几万位的数，把MAX_DIGITS调大或者改成动态分配就行。

注意：digits里存的是数值 0-9（或 0-1），不是字符'0'-'9'。输入输出时需要做一次转换，这是新手最容易搞混的地方。

2.3 编译与运行：三步跑通第一个测试

在讲核心算法之前，先把项目跑起来，确认环境没问题。这类 C 项目通常只需要 gcc 和 make：

# 1. 编译 make # 2. 运行全部测试 ./test_all # 3. 或者单独跑加法测试 ./test_add

如果make报错，大概率是这两个原因：一是Makefile里的编译器写的是gcc但你系统只有clang，改成CC = clang即可；二是头文件路径没配好，检查CFLAGS里有没有-Iinclude。编译通过后，test_all会输出一组预设的测试结果，比如：

[PASS] 12345678901234567890 + 98765432109876543210 = 111111111011111111100 [PASS] 100! 位数 = 158 [PASS] 2^100 mod 1000000007 = 976371285

看到[PASS]就说明核心运算没问题，可以开始看代码了。如果某个用例[FAIL]，先别急着改算法，用printf把中间结果打出来，确认是输入解析错了还是运算逻辑错了。

3. 核心运算拆解：加减乘除幂模的代码实现

3.1 大数加法：一个循环搞定进位

加法是所有运算的基础，逻辑最简单，但细节最多。先看代码：

// src/add_sub.c BigNum big_add(BigNum a, BigNum b) { BigNum res; res.sign = 0; res.base = a.base; int carry = 0; // 进位 int max_len = a.len > b.len ? a.len : b.len; int i; for (i = 0; i < max_len || carry; i++) { int da = (i < a.len) ? a.digits[i] : 0; // 短的那个补 0 int db = (i < b.len) ? b.digits[i] : 0; int sum = da + db + carry; res.digits[i] = sum % a.base; // 当前位 carry = sum / a.base; // 进位 } res.len = i; return res; }

逐段解释：

循环条件i < max_len || carry。前半段保证两个数的所有位都处理完，后半段保证最高位的进位不会丢。比如99 + 1，处理完两位后carry还是 1，必须再循环一次把进位写进去，否则结果变成00。

短数补零。i < a.len ? a.digits[i] : 0这行是关键。两个数长度不一样时，短的那个高位补 0，这样就不用写两套逻辑。比如123 + 45，45 在i=2时返回 0，等价于045。

取模和整除。sum % base得到当前位的值，sum / base得到进位。十进制时 base=10，二进制时 base=2，同一套代码通吃。这也是为什么结构体里要存base字段。

结果长度。循环结束时i的值就是结果的有效位数，直接赋给res.len。注意这里没有去掉前导零，因为低位在前存储，高位在数组末尾，前导零就是末尾的 0。如果结果实际是00123（存储为32100），len=5但有效位只有 3 位。常见做法是在返回前加一个去零循环：

while (res.len > 1 && res.digits[res.len - 1] == 0) { res.len--; }

这个去零操作在减法和除法里也必须做，否则后续比较大小会出错。

3.2 大数减法：借位与符号处理

减法比加法多两个坑：借位和符号。代码结构如下：

// src/add_sub.c int big_cmp_abs(BigNum a, BigNum b) { // 比较绝对值大小，a>b 返回 1，a<b 返回 -1，相等返回 0 if (a.len != b.len) return a.len > b.len ? 1 : -1; for (int i = a.len - 1; i >= 0; i--) { if (a.digits[i] != b.digits[i]) return a.digits[i] > b.digits[i] ? 1 : -1; } return 0; } BigNum big_sub(BigNum a, BigNum b) { // 先处理符号：a - b = a + (-b) if (a.sign != b.sign) { b.sign = !b.sign; return big_add(a, b); } // 同号相减，比较绝对值决定结果符号 int cmp = big_cmp_abs(a, b); if (cmp == 0) return big_zero(a.base); if (cmp < 0) { BigNum tmp = big_sub(b, a); tmp.sign = !a.sign; return tmp; } // |a| > |b|，正常借位减法 BigNum res; res.sign = a.sign; res.base = a.base; int borrow = 0; for (int i = 0; i < a.len; i++) { int da = a.digits[i] - borrow; int db = (i < b.len) ? b.digits[i] : 0; if (da < db) { da += a.base; borrow = 1; } else { borrow = 0; } res.digits[i] = da - db; } res.len = a.len; while (res.len > 1 && res.digits[res.len - 1] == 0) res.len--; return res; }

符号处理是减法的核心。a - b本质上可以转化为a + (-b)，所以异号相减直接翻转b的符号调加法。同号相减时，如果|a| < |b|，结果是负数，递归调用big_sub(b, a)算出绝对值再翻符号。这样就把所有情况都归约到了「大减小」这一种。

借位逻辑。da = a.digits[i] - borrow先减去上一位的借位，如果da < db，就从高位借一位，da += base，borrow = 1。注意借位是在当前位加base，不是加 10，这样二进制减法也能用同一套代码。

比较函数big_cmp_abs。先比长度，长度一样再从高位往低位逐位比。因为低位在前存储，所以要从len-1往 0 遍历。这个函数在减法和除法里都会用到，建议单独抽出来。

3.3 大数乘法：O(n²) 竖式与 Karatsuba 优化

乘法用竖式模拟，时间复杂度 O(n²)。对于课程设计来说，这个复杂度足够了，算 1000 位的乘法也就百万次操作。代码：

// src/mul_div.c BigNum big_mul(BigNum a, BigNum b) { BigNum res = big_zero(a.base); res.len = a.len + b.len; // 结果最多这么多位 memset(res.digits, 0, res.len); for (int i = 0; i < a.len; i++) { int carry = 0; for (int j = 0; j < b.len || carry; j++) { int db = (j < b.len) ? b.digits[j] : 0; int cur = res.digits[i + j] + a.digits[i] * db + carry; res.digits[i + j] = cur % a.base; carry = cur / a.base; } } // 去前导零 while (res.len > 1 && res.digits[res.len - 1] == 0) res.len--; res.sign = a.sign ^ b.sign; // 同号为正，异号为负 return res; }

双重循环的含义。外层遍历a的每一位，内层遍历b的每一位，a.digits[i] * b.digits[j]的结果累加到res.digits[i+j]上。这就是竖式乘法的本质：第 i 位乘第 j 位，结果落在第 i+j 位。

进位处理。cur = res.digits[i+j] + a.digits[i] * db + carry，注意这里加了res.digits[i+j]，因为不同位的乘积可能落在同一个位置，需要累加。比如a[0]*b[1]和a[1]*b[0]都落在res[1]。

符号。a.sign ^ b.sign异或运算，同号为 0（正），异号为 1（负），一行搞定。

优化方向。如果面试或答辩被问到优化，可以提 Karatsuba 算法，把 O(n²) 降到 O(n^1.585)。核心思想是分治：把大数拆成高低两半，用三次乘法代替四次。但课程设计里 O(n²) 完全够用，Karatsuba 的常数因子大，位数少的时候反而更慢。

3.4 大数除法与取模：试商法的实现

除法是最复杂的，因为要模拟人工试商的过程。常见做法是「减法试商」：从高位开始，每次取一段被除数，不断减去除数，减几次商就是几。但这样效率太低，更好的做法是「二分试商」或「移位试商」。这里给一个基于减法的简化版本：

// src/mul_div.c void big_divmod(BigNum a, BigNum b, BigNum *quotient, BigNum *remainder) { if (b.len == 1 && b.digits[0] == 0) { // 除零处理 quotient->len = 0; return; } BigNum q = big_zero(a.base); BigNum r = big_zero(a.base); q.len = a.len; for (int i = a.len - 1; i >= 0; i--) { // 余数左移一位，加上当前位 for (int k = r.len; k > 0; k--) r.digits[k] = r.digits[k-1]; r.digits[0] = a.digits[i]; r.len++; // 试商：r 能减几次 b int cnt = 0; while (big_cmp_abs(r, b) >= 0) { r = big_sub(r, b); cnt++; } q.digits[i] = cnt; } while (q.len > 1 && q.digits[q.len-1] == 0) q.len--; *quotient = q; *remainder = r; }

逐位试商。从被除数的最高位开始，每次把余数左移一位（相当于乘 base），加上当前位，然后看这个数能减几次除数。减的次数就是商的当前位。这个过程和手算长除法一模一样。

效率问题。内层while每次减一个除数，如果商很大（比如 9999），就要减 9999 次。优化方法是二分试商：先估算商的范围，用二分查找确定最大减次数。但课程设计里数据规模不大，直接减也能过。

取模。取模就是除法的余数，big_mod(a, b)直接调用big_divmod取remainder即可。注意取模结果的符号跟随被除数，这是 C 语言的标准行为。

3.5 大数乘方与快速幂取模

乘方就是重复乘法，但朴素做法太慢。a^n需要 n 次乘法，n 是 100 的时候还行，n 是 10^9 就废了。所以用快速幂：

// src/power_mod.c BigNum big_pow(BigNum a, long long n) { BigNum res = big_from_int(1, a.base); BigNum base = a; while (n > 0) { if (n & 1) res = big_mul(res, base); base = big_mul(base, base); n >>= 1; } return res; } BigNum big_pow_mod(BigNum a, BigNum n, BigNum m) { BigNum res = big_from_int(1, a.base); BigNum base = big_mod(a, m); // 把 n 转成二进制逐位处理 for (int i = 0; i < n.len; i++) { if (n.digits[i] == 1) res = big_mod(big_mul(res, base), m); base = big_mod(big_mul(base, base), m); } return res; }

快速幂的核心。把指数 n 写成二进制，比如2^10 = 2^(1010b) = 2^8 * 2^2。每次循环把底数平方，如果当前二进制位是 1 就乘到结果上。这样乘法次数从 O(n) 降到 O(log n)。

快速幂取模。在每一步乘法后都对 m 取模，防止中间结果过大。这是 RSA 加密里的标准操作，big_pow_mod就是 RSA 的核心函数。注意指数 n 本身也是大数，所以用n.digits[i]逐位判断，而不是n & 1。

参数说明。a是底数，n是指数，m是模数。big_from_int是把普通整数转成大数的辅助函数，实现很简单，就是不断取模存进digits数组。

4. 避坑与排查：大数运算里最容易翻车的五个地方

4.1 前导零没去掉导致比较大小出错

现象：big_cmp_abs判断100和99时返回相等或错误结果。

原因：减法或除法产生的结果末尾有零，len没有更新。比如100 - 1 = 099，存储为990，len=3，但实际有效位只有 2 位。比较时先比len，3 > 2，误判为099 > 99。

解决：每次运算返回前都加去零循环while (len > 1 && digits[len-1] == 0) len--;。注意条件是len > 1，因为数字 0 本身len=1，不能去成len=0。

4.2 二进制和十进制混用导致进位错误

现象：二进制加法1 + 1得到2，而不是10。

原因：进位时用了硬编码的 10 而不是base。sum % 10和sum / 10在二进制下就错了。

解决：所有涉及进位的运算都用a.base而不是字面量 10。输入输出时也要根据base做转换，二进制输出时digits里只有 0 和 1。

4.3 除法试商死循环

现象：程序卡在big_divmod里出不来。

原因：big_sub返回的结果没有去前导零，导致big_cmp_abs(r, b)永远返回>= 0，while循环停不下来。

解决：确保big_sub内部做了去零。另外在while循环里加一个计数器，如果cnt超过base，说明试商逻辑有问题，直接 break 并打印调试信息。

4.4 乘方指数溢出

现象：big_pow(a, n)里 n 用int存，算2^100时 n=100 没问题，但算2^100000时 n 溢出。

原因：指数本身可能很大，int只有 32 位。

解决：把指数参数改成long long，或者直接用BigNum存指数。如果指数是BigNum，快速幂的循环要改成遍历指数的每一位，就像big_pow_mod那样。

4.5 栈空间不足导致段错误

现象：程序运行到一半报Segmentation fault，尤其是在递归调用big_sub或创建多个BigNum局部变量时。

原因：BigNum结构体里的digits数组是固定大小的，如果MAX_DIGITS设成 10000，每个BigNum占约 10KB。递归深度一大，或者函数里开了多个BigNum，栈就爆了。

解决：把digits改成动态分配char *digits，在big_init里malloc，在big_free里释放。或者把MAX_DIGITS调小到实际需要的位数。另一个办法是把大数组改成static或全局变量，但这样就不能重入了。

5. 二次开发与扩展：从课程设计到可用工具库的改造思路

5.1 把固定数组改成动态内存

课程设计里用固定数组是为了省事，但要做成能实际用的库，动态内存是第一步。改造方法：

typedef struct { int sign; int base; int len; int cap; // 容量 char *digits; // 动态数组 } BigNum; BigNum big_init(int base, int cap) { BigNum n; n.sign = 0; n.base = base; n.len = 1; n.cap = cap; n.digits = (char *)calloc(cap, sizeof(char)); return n; } void big_free(BigNum *n) { free(n->digits); n->digits = NULL; n->len = n->cap = 0; }

改造后每个BigNum只占几十字节，栈压力小很多。但要注意内存泄漏——每次big_init都要对应一个big_free。常见做法是写一个big_copy函数，返回新的BigNum，调用者负责释放。

5.2 增加更多运算：GCD、进制转换、比较运算符

课程设计只要求加减乘除幂模，但实际用起来还需要这些：

最大公约数。用辗转相除法，基于big_mod实现：

BigNum big_gcd(BigNum a, BigNum b) { while (!(b.len == 1 && b.digits[0] == 0)) { BigNum r = big_mod(a, b); a = b; b = r; } return a; }

任意进制转换。当前只支持十进制和二进制，扩展到 2-36 进制只需要改base字段和输入输出函数。核心是base_convert.c里的to_base和from_base，用短除法不断取余。

比较运算符。把big_cmp_abs扩展成big_cmp，加上符号判断，然后封装成big_gt、big_lt、big_eq等函数，用起来更顺手。

5.3 性能验证：怎么确认你的优化真的有效

改完代码后，别凭感觉说「快了」。用clock()测一下实际耗时：

#include <time.h> void benchmark() { BigNum a = big_from_str("123456789012345678901234567890", 10); BigNum b = big_from_str("987654321098765432109876543210", 10); clock_t start = clock(); for (int i = 0; i < 10000; i++) { BigNum c = big_mul(a, b); big_free(&c); } clock_t end = clock(); printf("10000 次乘法耗时: %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC); }

跑之前和跑之后各测一次，对比数字。如果优化后反而更慢，大概率是动态内存分配的开销盖过了算法优化，这时候可以考虑内存池或者对象复用。

5.4 一个我踩过的坑：递归减法的栈溢出

最后说一个血泪经验。我一开始写big_sub的时候，为了代码简洁，用了递归：|a| < |b|时递归调用big_sub(b, a)再翻符号。测试小数据没问题，但算100000...0 - 1的时候直接段错误。原因是递归深度等于数字的位数，10000 位的数递归 10000 层，每层都有局部BigNum变量，栈直接爆了。后来改成迭代版本，用一个swap交换a和b，算完再翻符号，问题解决。从那以后我每次写递归函数都先问自己：递归深度会不会跟输入规模线性相关？如果是，强制改迭代。希望这个教训能帮你少走一段弯路。

本文还有配套的精品资源，点击获取