有效地计算两个数之和的模数

Question

我有三个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

Answer 1

在数学中，整数除法通常向下舍入到负无穷大，模的符号与“除数”相同或者为零：-10 mod 3 = 2 和 10 mod -3 = -2（商舍入）降至-4)。在 C / C++ 中，整数除法向零舍入，% 的符号与“被除数”或“分子”的符号相同或者为零，-10 mod 3 = -1 和 10 mod -3 = 1 (商向零舍入到-3)。使用 C / C++ 进行有限域类型数学计算时，需要进行后校正，以使结果与模的数学定义相匹配。例如，如果 X % 3 = -1，则加 3，使得 X mod 3 = +2。

假设 C 为正，则以 C 为模的数学域由数字 {0, 1, ... C-1} 组成，没有任何负数。如果 C 为负（这对于模数来说不常见），则该字段为 {0, -1, -2, ... C+1}。假设C是正数，那么如果A或B是负数，使用((A%C)+(B%C))%C仍然是安全的，然后如果结果是负数，则通过在结果中添加C来修正。