20、大整数运算：用链表表示大整数、大整数加法、大整数乘法

说到大整数运算，我估计不少同学第一反应是：「int不够用就用long long呗，再不行就unsigned long long？」嗯，我以前也是这么想的。直到有一次我在做嵌入式支付终端项目，需要处理一个128位的金额数值——你想想看，标准C语言里最大的整数类型也就64位，根本装不下。

那怎么办？用数组？数组长度固定，万一数字再大一点就尴尬了。我个人习惯用链表来存大整数，每个节点存一位数字（或者几位数字），这样要多大有多大，动态扩展，非常灵活。

大整数的链表表示

说白了，就是用链表模拟一个「无限长」的整数。每个节点存一位数字，从低位到高位依次链接。为什么从低位开始？因为做加法、乘法时都是从低位往高位算，这样遍历起来顺手。

我一般这样定义节点：

typedef struct BigIntNode {
    int digit;                // 当前位，0-9
    struct BigIntNode *next;  // 指向更高位
} BigIntNode;

举个例子，数字 12345 用链表表示就是：

头节点 -> [5] -> [4] -> [3] -> [2] -> [1] -> NULL

注意看，个位5在最前面，万位1在最后面。这样设计的好处是：做加法时从链表头开始遍历，正好是从低位到高位，不用反转链表。

核心思路：链表节点存一位数字，头节点存最低位。这样加法、乘法都可以从头部开始顺序处理进位。

大整数加法

加法其实很简单，就是模拟我们小学学的竖式计算。两个链表从头开始遍历，对应位相加，处理进位，结果存到新链表里。

我在项目中遇到过一个问题：两个大整数的位数可能不一样。比如一个100位，一个50位。那短的链表遍历完了怎么办？很简单，短的链表遍历完后，它的对应位就当作0处理。

BigIntNode* bigIntAdd(BigIntNode *a, BigIntNode *b) {
    BigIntNode *result = NULL;
    BigIntNode **tail = &result;
    int carry = 0;

    while (a != NULL || b != NULL || carry != 0) {
        int sum = carry;
        if (a != NULL) {
            sum += a->digit;
            a = a->next;
        }
        if (b != NULL) {
            sum += b->digit;
            b = b->next;
        }

        // 创建新节点存当前位
        BigIntNode *node = (BigIntNode*)malloc(sizeof(BigIntNode));
        node->digit = sum % 10;
        node->next = NULL;
        *tail = node;
        tail = &(node->next);

        carry = sum / 10;
    }

    return result;
}

你看，代码里while循环的条件包含了 carry != 0，这是为了防止最后还有进位没处理。我曾经漏掉这个条件，结果999+1算出来是000，调试了半天才发现——嗯，这种低级错误犯过一次就不会再犯了。

小技巧：用二级指针 tail 来维护链表尾部，比每次遍历到末尾再插入要高效得多。这是链表操作里很实用的一个手法。

大整数乘法

乘法比加法复杂一些。还是用竖式思路：拿乘数的每一位去乘以被乘数，得到中间结果，然后把这些中间结果按位对齐后相加。

举个例子，123 × 45：

  • 先用5乘123，得到615
  • 再用4乘123，得到492，但要对齐到十位（相当于4920）
  • 最后615 + 4920 = 5535

用链表实现时，我习惯这样写：

BigIntNode* bigIntMul(BigIntNode *a, BigIntNode *b) {
    BigIntNode *result = NULL;

    int shift = 0;  // 记录当前是对齐到哪一位
    BigIntNode *pb = b;

    while (pb != NULL) {
        // 用 pb->digit 去乘整个 a
        BigIntNode *temp = mulSingleDigit(a, pb->digit, shift);

        // 累加到结果中
        result = bigIntAdd(result, temp);

        // 释放临时链表（略）
        pb = pb->next;
        shift++;
    }

    return result;
}

// 大整数乘以一位数字，并左移 shift 位
BigIntNode* mulSingleDigit(BigIntNode *a, int digit, int shift) {
    BigIntNode *result = NULL;
    BigIntNode **tail = &result;
    int carry = 0;

    // 先补 shift 个0（相当于左移）
    for (int i = 0; i < shift; i++) {
        BigIntNode *zero = (BigIntNode*)malloc(sizeof(BigIntNode));
        zero->digit = 0;
        zero->next = NULL;
        *tail = zero;
        tail = &(zero->next);
    }

    // 逐位相乘
    while (a != NULL || carry != 0) {
        int product = carry;
        if (a != NULL) {
            product += a->digit * digit;
            a = a->next;
        }
        BigIntNode *node = (BigIntNode*)malloc(sizeof(BigIntNode));
        node->digit = product % 10;
        node->next = NULL;
        *tail = node;
        tail = &(node->next);
        carry = product / 10;
    }

    return result;
}

注意：乘法的时间复杂度是O(n×m)，n和m分别是两个大整数的位数。如果两个数都是1000位，那就是100万次乘法操作。对于嵌入式环境来说，这个开销不小。如果性能敏感，可以考虑用Karatsuba算法优化，不过那是进阶内容了。

知识体系结构图

下面这张图把大整数运算的核心逻辑串起来了，你可以对照着看：

大整数运算核心逻辑 链表表示大整数 头节点存最低位 大整数加法 逐位相加 + 进位 大整数乘法 逐位相乘 + 移位累加 加法关键细节 • 两个链表长度可能不同 • 最后一位可能有进位 乘法关键细节 • 每位相乘后要左移对齐 • 多个中间结果累加 核心：用链表模拟竖式计算，动态扩展无上限 时间复杂度：加法O(n) | 乘法O(n×m)

实际项目中的注意事项

我在嵌入式项目里用大整数链表时，踩过几个坑，分享给你：

  • 内存泄漏：每次malloc都要对应free。尤其是乘法里会产生很多临时链表，用完不释放，跑几次内存就爆了。我建议写一个专门的 freeBigInt() 函数来统一释放。
  • 性能问题：如果每个节点只存一位数字，链表会很长。对于1000位的整数，链表就有1000个节点。我后来改成每个节点存4位数字（0-9999），这样链表长度缩短到1/4，加法乘法的遍历次数也大幅减少。
  • 符号处理：上面的例子只考虑了正数。实际项目中大整数可能有正负。我习惯在链表头再加一个符号位，或者单独用一个字段记录符号。做加法时要根据符号决定是相加还是相减。

优化建议：每个节点存4位数字时，加法进位变成 sum / 10000，取余变成 sum % 10000。这样既节省了链表节点数，又保持了代码的清晰度。我个人比较推荐这种折中方案。

好了，大整数运算的核心就是这些。链表表示、加法、乘法，说白了都是模拟我们手算的过程。你只要把竖式计算的逻辑想清楚，代码写起来就很顺畅。至于除法、取模这些运算，思路类似，但实现上会更复杂一些，有兴趣可以自己尝试扩展。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →