具体来说:我有两个无符号整数(a,b),我想计算(a * b)%UINT_MAX(UINT_MAX定义为最大无符号整数)。最好的方法是什么?
背景:我需要为Linux编写一个模块来模拟几何序列,从它读取将为我提供下一个元素(模UINT_MAX),我发现的唯一解决方案是将当前元素添加到自身次,而添加是使用以下逻辑完成:(我用于算术序列)
for(int i=0; i<b; ++i){
if(UINT_MAX - current_value > difference) {
current_value += difference;
} else {
current_value = difference - (UINT_MAX - current_value);
}
当第一次迭代中 current_value = a 时(并且在每次迭代中更新,并且差值 = a(始终))。 显然这不是一个明智的解决方案。 一个聪明的人如何实现这一目标?
谢谢!
如前所述,如果您有可用宽度两倍的类型,请在此处使用该类型
(unsigned int)(((unsigned long long)a * b) % UINT_MAX)
如果
int
是 32 位且 long long
64(或更多)。如果没有更大的类型,可以将因子拆分为一半的位宽,将各个部分相乘并减少,最后将其组合起来。这里以 32 位无符号为例:
a_low = a & 0xFFFF; // low 16 bits of a
a_high = a >> 16; // high 16 bits of a, shifted in low half
b_low = b & 0xFFFF;
b_high = b >> 16;
/*
* Now a = (a_high * 65536 + a_low), b = (b_high * 65536 + b_low)
* Thus a*b = (a_high * b_high) * 65536 * 65536
* + (a_high * b_low + a_low * b_high) * 65536
* + a_low * b_low
*
* All products a_i * b_j are at most (65536 - 1) * (65536 - 1) = UINT_MAX - 2 * 65536 + 2
* The high product reduces to
* (a_high * b_high) * (UINT_MAX + 1) = (a_high * b_high)
* The middle products are a bit trickier, but splitting again solves:
* m1 = a_high * b_low;
* m1_low = m1 & 0xFFFF;
* m1_high = m1 >> 16;
* Then m1 * 65536 = m1_high * (UINT_MAX + 1) + m1_low * 65536 = m1_high + m1_low * 65536
* Similar for a_low * b_high
* Finally, add the parts and take care of overflow
*/
m1 = a_high * b_low;
m2 = a_low * b_high;
m1_low = m1 & 0xFFFF;
m1_high = m1 >> 16;
m2_low = m2 & 0xFFFF;
m2_high = m2 >> 16;
result = a_high * b_high;
temp = result + ((m1_low << 16) | m1_high);
if (temp < result) // overflow
{
result = temp+1;
}
else
{
result = temp;
}
if (result == UINT_MAX)
{
result = 0;
}
// I'm too lazy to type out the rest, you get the gist, I suppose.
当然,如果你需要的实际上是减少模
UINT_MAX + 1
,正如@Toad假设的那样,那么这就是unsigned int
的乘法所做的。
编辑:正如评论中所指出的......这个答案适用于 Modulo MAX_INT+1 我会把它留在这里,以供将来参考。
比这简单得多:
只需将两个无符号整数相乘,结果也将是一个无符号整数。 所有不适合 unsigned int 的东西基本上都不存在。 所以不需要做模运算:
#include <stdio.h>
void main()
{
unsigned int a,b;
a = 0x90000000;
b = 2;
unsigned int c = a*b;
printf("Answer is %X\r\n", c);
}
答案是:0x20000000(所以它应该是0x120000000,但答案已被截断,正是您想要的模运算)
您可以在 C99 中执行模乘法:
typedef unsigned long long int ulong;
我正在使用这个功能:
ulong mul_mod(ulong a, ulong b, const ulong mod) {
ulong res = 0, c; // return (a * b) % mod, avoiding overflow errors while doing modular multiplication.
for (b %= mod; a; a & 1 ? b >= mod - res ? res -= mod : 0, res += b : 0, a >>= 1, (c = b) >= mod - b ? c -= mod : 0, b += c);
return res % mod;
}
该函数使用“俄罗斯农民乘法”或“二进制乘法”方法实现模乘法,通过确保每个中间结果使用模运算保持在范围内来避免溢出。