描述
定義函式
unsigned mod(unsigned a, unsigned b, unsigned c)；功能是計算并回傳a*b%c的結果。測驗a、b、c的范圍要求大于0且小于2^31，程式不能用64位整數（如long long型別或__int64）求解。
問題：a*b 可能溢位（超出 32 位 unsigned int 型別的表示范圍）。為了解決這個問題，可以使用以下演算法。假設無符號變數b的每個二進制位為xi (i=0,1, …, 31)，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），就會得到錯誤的答案。我不知道這是為什么，因為我只是根據問題中給出的公式進行編程，我不知道數學原理。
uj5u.com熱心網友回復：
問題在這里：
在 中mod()，您得到sum = (sum << 1) % c a * ((b >> i) & 1);，
而 的值sum可能與a（也就是 32 位無符號整數）一樣大。
當sum大于 2^31（大于0b'1000 0000 0000 0000 0000 0000 0000 0000）時，
左移仍然會導致溢位。
uj5u.com熱心網友回復：
正如@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。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/351310.html
上一篇：演算法中的大O
下一篇：音樂椅問題在C 中的實作