C中位运算的模运算

Question

描述

Define the function unsigned mod(unsigned a, unsigned b, unsigned c); The function is to calculate and return the result of a*b%c. The range of test a, b, c is required to be greater than 0 and less than 2^31, and the program cannot use 64-bit integer (such as long long type or __int64) to solve.

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

和

In the above formula, the result of a*xi is either a or 0; *2 Operation can be achieved by shifting 1 bit to the left (integer less than 2^31 *2 The result must be less than 2^32, and overflow will not occur); The result of %c is less than c, and c is less than 2^31, and the sum of it and a will not overflow. Write a complete program and implement the above algorithm by iterative method.

我的代码

#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

问题出在这里：

在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）时，
左移仍然会造成溢出。

Answer 2

正如@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。

C中位运算的模运算

Modulo operation by bit operation in C

c

algorithm

math

modulo

描述

我的代码

问题