我有三个 N
位数,A
、B
和 C
。我无法轻松计算 (A + B) % C
,但我可以轻松计算 A % C
和 B % C
。如果模运算是无符号的,并且我提前知道 A + B
不会环绕 N
位,那么我可以改为计算 ((A % C) + (B % C)) % C
。但是,对于模运算已签名或添加 A
和 B
可能导致环绕的情况,是否可以做任何事情。
对于为什么 ((A % C) + (B % C)) % C
不能始终有效,看起来可能存在一些混淆。这是一个未签名的示例:
unsigned A = 0x1U;
unsigned B = 0xFFFFFFFFU;
unsigned C = 0x3U;
((A % C) + (B % C)) % C == 0x1U but (A + B) % C == 0x0U
这是一个签名示例:
int A = 0x1;
int B = 0xE27F9803;
int C = 0x3U;
((A % C) + (B % C)) % C == 0x1U but (A + B) % C == -2
最佳答案
你想要的是:
((a+b)%2^n)%c
让
a+b = k 2^n + d
在哪里k = 0 or 1
和 d < 2^n
.
插入你得到:
((k 2^n + d) % 2^n) % c = (d % 2^n) % c = d % c
将前面的表达式取模 c
你得到
(a + b) % c = (k 2^n + d) % c => d % c = a % c + b % c - k 2^n % c
与 n = 32
, 在 C:
unsigned myMod(unsigned a, unsigned b, unsigned c)
{
// k = 1 if the sum overflows
unsigned k = ( a > UINT_MAX - b or b > UINT_MAX - a);
return ( a % c + b % c - k*(UINT_MAX%c + 1))%c;
}
myMod(0x1U,0xFFFFFFFFU,0x3U) == 0
关于c - 有效地计算两个数之和的模数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27246594/