C语言不使用64位整数通过位运算实现a*b%c时大数计算错误求解

错误原因 #

你的代码核心问题是每次加上当前位对应的a值后没有及时对c取模，导致sum变量的值可能超过2^31，下一次循环执行左移1位操作时，会超出算法预期的数值范围，最终计算结果出错。

题目描述里明确提到：%c的结果小于c，而c小于2^31，因此它和a的和不会溢出，这个结论成立的前提是你加完a之后要再次对c取模，保证sum永远小于c（也就是小于2^{31），这样下一次左移1位的结果最大为2*(2}31-2) = 2^{32-4，完全在32位无符号整数的表示范围内，不会出现非预期的溢出。你现在的写法只在左移后取模，加完a之后没有取模，sum可能会大于等于c甚至超过2}31，后续左移时就会出现错误。

修复方案 #

对mod函数做两处修改：

1. 初始sum计算后先对c取模，也可以提前对a取模缩小计算量级
2. 每次循环中，加完a*xi的结果后，整体再对c取模，保证sum始终小于c

修改后的完整代码如下：

#pragma warning(disable:4996)
#include <stdio.h>

unsigned mod(unsigned a, unsigned b, unsigned c) {
    a = a % c;
    unsigned sum = (a * ((b >> 30) & 1)) % c;
    for (int i = 29; i >= 0; i--) {
        sum = ((sum << 1) % c + a * ((b >> i) & 1)) % c;
    }
    return sum;
}

int main() {
    unsigned a, b, c;
    printf("Input unsigned integer numbers a, b, c:\n");
    scanf("%u %u %u", &a, &b, &c);
    printf("%u*%u%%%u=%u\n", a, b, c, mod(a, b, c));

    //验证输出结果
    unsigned long long ab, bb, cb;
    ab = a;
    bb = b;
    cb = c;
    printf("%llu*%llu%%%llu=%llu", ab, bb, cb, ab * bb % cb);
}

修改后的代码完全符合题目要求，不会使用64位整数，所有中间操作都不会出现非预期溢出，测试2147483647*2147483647%3可以得到正确结果1。

内容的提问来源于stack exchange，提问作者fjybiocs