如何在C语言中计算32字节无符号大整数（含加减模乘）

这是个非常实用的大整数运算场景——32字节刚好对应256位的无符号整数，咱们可以通过模拟手动计算十进制数的逻辑，来实现这些基础运算。首先要明确一个前提：假设你的uint8_t*缓冲区采用小端存储（也就是缓冲区的第0个元素是整数的最低有效字节，第31个元素是最高有效字节），这是处理字节级运算最方便的存储方式；如果你的数据是大端存储，只需要调整循环的方向即可。

下面逐个拆解每个运算的实现思路和代码示例：

1. 加法运算 #

加法的核心就是逐字节相加+进位传递，和咱们手算十进制加法完全一样，只不过这里是按8位字节（相当于256进制的数位）来计算。

实现代码 #

#include <stdint.h>
#include <string.h>

// a和b都是32字节的小端存储无符号大整数
// result用来存储结果（需提前分配至少32字节空间）
// 返回值：加法的进位（1表示溢出，0表示正常）
uint8_t big_add(uint8_t *a, uint8_t *b, uint8_t *result) {
    uint8_t carry = 0;
    for (int i = 0; i < 32; i++) {
        uint16_t sum = (uint16_t)a[i] + (uint16_t)b[i] + carry;
        result[i] = (uint8_t)(sum & 0xFF);
        carry = (uint8_t)(sum >> 8);
    }
    return carry;
}

说明 #

• 用uint16_t来临时存储和，避免8位字节相加时溢出；
• 循环从最低字节（索引0）到最高字节（索引31），依次处理每一位的和与进位；
• 返回的进位如果是1，说明两个32字节数相加的结果超过了32字节，发生了溢出。

2. 乘法运算 #

乘法的思路是逐位相乘+累加+进位传递，类似手算乘法时，用乘数的每一位去乘被乘数，然后把结果错位相加。对于32字节的数，乘积最大会是64字节，所以结果缓冲区要分配足够的空间。

实现代码 #

// a和b都是32字节的小端存储无符号大整数
// result用来存储乘积（需提前分配至少64字节空间，且初始化为0）
void big_mul(uint8_t *a, uint8_t *b, uint8_t *result) {
    // 先清空结果缓冲区
    memset(result, 0, 64);
    
    for (int i = 0; i < 32; i++) {
        uint8_t carry = 0;
        // 用a的第i位去乘b的每一位
        for (int j = 0; j < 32; j++) {
            uint32_t product = (uint32_t)a[i] * (uint32_t)b[j] + result[i+j] + carry;
            result[i+j] = (uint8_t)(product & 0xFF);
            carry = (uint8_t)((product >> 8) & 0xFF);
        }
        // 处理当前字节相乘后的剩余进位
        if (carry != 0) {
            result[i+32] += carry;
        }
    }
}

说明 #

• 必须提前将result清零，否则会有垃圾数据影响计算；
• 用uint32_t存储临时乘积，避免两个8位字节相乘（最大255*255=65025）加上已有结果和进位时溢出；
• 乘积的第i+j位对应a的第i位和b的第j位相乘的结果，这和十进制乘法的错位相加逻辑一致。

3. 取模运算 #

取模运算相对复杂一点，高效的实现思路是模拟长除法的“移位减”逻辑：先把模数左移到和被除数的最高位对齐，然后逐位比较，如果被除数大于等于当前移位后的模数，就减去它，最后把模数逐步右移，直到回到原始大小，剩下的就是余数。

实现代码 #

// 辅助函数：比较两个32字节小端存储的大整数，a >= b返回1，否则返回0
int big_ge(uint8_t *a, uint8_t *b) {
    for (int i = 31; i >= 0; i--) {
        if (a[i] > b[i]) return 1;
        if (a[i] < b[i]) return 0;
    }
    return 1; // 相等
}

// 辅助函数：将大整数左移1位（小端存储），返回进位
uint8_t big_shift_left(uint8_t *num) {
    uint8_t carry = 0;
    for (int i = 0; i < 32; i++) {
        uint8_t new_carry = num[i] >> 7;
        num[i] = (num[i] << 1) | carry;
        carry = new_carry;
    }
    return carry;
}

// 辅助函数：大整数减法（假设a >= b），结果存在a中
void big_sub(uint8_t *a, uint8_t *b) {
    uint8_t borrow = 0;
    for (int i = 0; i < 32; i++) {
        if (a[i] >= b[i] + borrow) {
            a[i] -= b[i] + borrow;
            borrow = 0;
        } else {
            a[i] = (a[i] + 256) - b[i] - borrow;
            borrow = 1;
        }
    }
}

// num是32字节的被除数，mod是32字节的模数（mod不能为0）
// result存储余数（需提前分配32字节空间）
void big_mod(uint8_t *num, uint8_t *mod, uint8_t *result) {
    // 先把被除数复制到result中作为初始值
    memcpy(result, num, 32);
    
    uint8_t shifted_mod[32];
    memcpy(shifted_mod, mod, 32);
    int shift_count = 0;
    
    // 把模数左移，直到它的最高位和被除数对齐
    while (!big_ge(result, shifted_mod) && shift_count < 256) {
        if (big_shift_left(shifted_mod)) {
            break; // 左移后溢出，停止
        }
        shift_count++;
    }
    
    // 逐位减移位后的模数
    while (shift_count >= 0) {
        if (big_ge(result, shifted_mod)) {
            big_sub(result, shifted_mod);
        }
        // 把模数右移1位
        uint8_t carry = 0;
        for (int i = 31; i >= 0; i--) {
            uint8_t new_carry = shifted_mod[i] & 1;
            shifted_mod[i] = (shifted_mod[i] >> 1) | (carry << 7);
            carry = new_carry;
        }
        shift_count--;
    }
}

说明 #

• 依赖三个辅助函数：比较大小、左移、减法，这些都是大整数运算的基础工具；
• 移位减的效率比直接循环减法高得多，尤其当模数远小于被除数时；
• 要确保模数mod不为0，否则会导致未定义行为。

额外注意事项 #

• 存储顺序：如果你的缓冲区是大端存储（第0个元素是最高有效字节），只需要把循环的索引方向反过来（比如加法从31到0循环）；
• 缓冲区大小：乘法结果必须用64字节的缓冲区，加法如果要处理溢出可以用33字节的缓冲区；
• 性能优化：如果需要更高的性能，可以考虑按32位或64位字来处理（比如用uint32_t代替uint8_t循环），减少循环次数；
• 边界情况：要测试一些极端情况，比如全1的数相加、乘1、模1等，确保代码的鲁棒性。

内容的提问来源于stack exchange，提问作者H.Hoang