C中位运算的模块运算

Question

描述

定义函数unsigned mod(unsigned a, unsigned b, unsigned c)；函数是计算和返回a* b %c的结果。测试a、b、c的范围必须大于0且小于2^31，程序不能使用64位整数(例如长类型或__int64)来求解。

问题: a*b可能溢出(超出32位无符号int类型的表示范围)。为了解决这个问题，可以使用以下算法。假设无符号变量b的每个二进制位为xi (i=0,1，…)，i=0是最低位，i=31是最高位，那么

​

和

​

在上述公式中，a*xi的结果要么是a，要么是0；*2运算可以通过向左移动1位来实现(整数小于2^31 *2，结果必须小于2^32，并且不会发生溢出)；%c的结果小于c，c小于2^31，它和a的和不会溢出。编写完整的程序，用迭代的方法实现上述算法。

我的密码

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

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

int main() {
    //to achieve the subject requirements
    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));

    //to verify output results
    unsigned long long ab, bb, cb;
    ab = a;
    bb = b;
    cb = c;
    printf("%llu*%llu%%%llu=%llu", ab, bb, cb, ab * bb % cb);
}

问题

当用较小的数字(如100*500/3)执行计算时，结果是正确的。但是当这个数字接近问题的上限时(比如2147483647*2147483647/3)，你就会得到错误的答案。我不知道为什么会这样，因为我只是根据问题中给出的公式来编程，我也不知道数学原理。

Answer 1

正如@Uduru已经指出的，sum可能会大于2^31，因此，左移位将导致溢出。

为了防止这一点，请记住:左移1等于乘2。所以，(sum << 1) % c和(sum * 2) % c是一样的。现在，模块规则声明如下：

(a * b) mod c == ((a mod c) * (b mod c)) mod c. 

因此，您可能会将代码更改为以下内容。

sum = ((sum % c) << 1) % c + a * ((b >> i) & 1);

因为c保证小于2^31 (根据引用的部分)，所以sum % c也保证小于2^31。

Answer 2

问题在于：

在mod()，你有sum = (sum << 1) % c + a * ((b >> i) & 1);，

而sum的值可能与a (a.k.a.，32位无符号整数)一样大。

当sum大于2^31 (大于0b'1000 0000 0000 0000 0000 0000 0000 0000)时，

左移仍然会导致溢出。