第30章 字符串与数字互转（大数处理）：大数加法、大数乘法

各位同学，今天咱们聊点硬核的——大数处理。

你可能会问：C语言里不是有int、long long吗？为什么还要搞什么大数？

我当年刚入行时也这么想。直到有一次做金融系统，需要计算一个100位的整数乘法。int？long long？全炸了。那会儿我才意识到：语言内置的类型，根本扛不住真实世界的需求。

说白了，大数处理就是用字符串或数组来模拟数学运算。今天咱们就讲两个最基础的操作：大数加法和大数乘法。

---

30.1 大数加法：从小学竖式说起

大数加法的思路，其实就是你小学学过的竖式加法。

两个数从低位到高位逐位相加，逢十进一。只不过现在数字太大，我们得用字符串存。

我习惯用逆序存储。什么意思？比如数字"12345"，我存成字符数组时，让低位在索引0的位置：

原始数字: "12345"
逆序存储: ['5','4','3','2','1']

为什么这么干？因为加法是从低位开始的。逆序存储后，索引0就是最低位，循环起来特别顺手。

来看代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 大数加法：返回 a + b 的字符串结果
char* big_add(const char* a, const char* b) {
    int len_a = strlen(a);
    int len_b = strlen(b);
    int max_len = (len_a > len_b ? len_a : len_b) + 1; // 多留一位给进位
    char* result = (char*)malloc(max_len + 1);
    if (!result) return NULL;

    int i = len_a - 1, j = len_b - 1, k = 0;
    int carry = 0;

    // 从低位到高位逐位相加
    while (i >= 0 || j >= 0 || carry) {
        int digit_a = (i >= 0) ? a[i--] - '0' : 0;
        int digit_b = (j >= 0) ? b[j--] - '0' : 0;
        int sum = digit_a + digit_b + carry;
        result[k++] = (sum % 10) + '0';
        carry = sum / 10;
    }

    result[k] = '\0';

    // 翻转结果（因为我们是从低位往高位存的）
    for (int left = 0, right = k - 1; left < right; left++, right--) {
        char tmp = result[left];
        result[left] = result[right];
        result[right] = tmp;
    }

    return result;
}

这段代码我用了很多年。核心就三点：

• 从后往前遍历两个字符串
• 处理进位，carry变量是关键
• 最后翻转，因为结果也是逆序存的

你可能会问：如果两个数都是0呢？

嗯，这个代码会返回"0"。因为循环一开始carry=0，两个digit都是0，sum=0，结果存了个'0'，然后carry=0，循环结束。没问题。

---

30.2 大数乘法：别被复杂度吓到

大数乘法比加法复杂一些。但别怕，思路还是那个思路——模拟竖式乘法。

你还记得小学怎么算多位数乘法吗？

比如 123 × 45：

      1 2 3
   ×    4 5
   --------
      6 1 5   (123 × 5)
    4 9 2     (123 × 4，左移一位)
   --------
    5 5 3 5   (相加)

大数乘法就是把这个过程用代码实现。我个人的做法是：

1. 先逐位相乘，结果存到一个临时数组里（不处理进位）
2. 最后统一处理进位

这样逻辑更清晰，不容易出错。

来看代码：

char* big_multiply(const char* a, const char* b) {
    int len_a = strlen(a);
    int len_b = strlen(b);
    int total_len = len_a + len_b;
    int* temp = (int*)calloc(total_len, sizeof(int));
    if (!temp) return NULL;

    // 逐位相乘，结果累加到对应位置
    for (int i = len_a - 1; i >= 0; i--) {
        for (int j = len_b - 1; j >= 0; j--) {
            int digit_a = a[i] - '0';
            int digit_b = b[j] - '0';
            int pos = (len_a - 1 - i) + (len_b - 1 - j);
            temp[pos] += digit_a * digit_b;
        }
    }

    // 统一处理进位
    int carry = 0;
    for (int i = 0; i < total_len; i++) {
        int sum = temp[i] + carry;
        temp[i] = sum % 10;
        carry = sum / 10;
    }

    // 找到最高有效位
    int last = total_len - 1;
    while (last > 0 && temp[last] == 0) last--;

    // 转成字符串
    char* result = (char*)malloc(last + 2);
    if (!result) {
        free(temp);
        return NULL;
    }

    for (int i = 0; i <= last; i++) {
        result[i] = temp[last - i] + '0';
    }
    result[last + 1] = '\0';

    free(temp);
    return result;
}

这段代码的时间复杂度是O(n×m)，n和m分别是两个数的位数。对于几百位的数，完全够用。

但如果你要处理上万位的数，那就得考虑更高效的算法了，比如Karatsuba算法或FFT。不过那是进阶内容，咱们今天先打好基础。

---

30.3 知识结构图：大数处理的核心逻辑

下面这张图，是我自己总结的大数处理知识结构。你看一眼，心里就有谱了。

从图上你能看到，大数加法和乘法都基于同一个思想：模拟竖式运算。区别在于加法是一次遍历，乘法是两层循环。

---

30.4 避坑指南：我踩过的那些坑

做这行十几年，我在大数处理上栽过不少跟头。挑几个典型的说说：

---

30.5 实战经验：什么时候用大数？

你可能觉得大数处理离自己很远。其实不然。

我参与过一个区块链钱包项目，里面涉及以太坊的wei单位转换。1 ether = 10^18 wei，这个数字已经超过long long的范围了。所有金额计算都得用大数。

还有一个科学计算器的项目，用户输入"12345678901234567890 × 98765432109876543210"，普通计算器直接溢出，但我们的计算器能给出精确结果。靠的就是大数乘法。

所以，别觉得大数处理是屠龙之术。它其实是个很实用的技能。

---

30.6 总结

今天咱们讲了：

• 大数加法：逆序存储，逐位相加，处理进位
• 大数乘法：两层循环逐位相乘，统一处理进位
• 避坑指南：前导零、内存泄漏、类型转换、进位传递

这两个算法是基础中的基础。掌握了它们，你就能处理任意长度的整数运算了。

最后送你一句话：算法不难，难的是细节。写代码时多想想边界情况，多测试几个极端例子，你的代码就会越来越稳。

---

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