如何在处理负数的 C/C++/Obj-C 中编写模 (%) 运算符
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4003232/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to code a modulo (%) operator in C/C++/Obj-C that handles negative numbers
提问by P i
One of my pet hates of C-derived languages (as a mathematician) is that
我最讨厌 C 派生语言（作为数学家）之一是
(-1) % 8 // comes out as -1, and not 7
fmodf(-1,8) // fails similarly
What's the best solution?
最好的解决办法是什么？
C++ allows the possibility of templates and operator overloading, but both of these are murky waters for me. examples gratefully received.
C++ 允许模板和运算符重载的可能性，但这两者对我来说都是浑水。示例感谢收到。
采纳答案by Armen Tsirunyan
First of all I'd like to note that you cannot even rely on the fact that (-1) % 8 == -1. the only thing you can rely on is that (x / y) * y + ( x % y) == x. However whether or not the remainder is negative is implementation-defined.
首先，我想指出的是，您甚至不能依赖(-1) % 8 == -1. 你唯一可以依靠的是(x / y) * y + ( x % y) == x。然而，余数是否为负是实现定义的。
Now why use templates here? An overload for ints and longs would do.
现在为什么要在这里使用模板？整数和长整数的重载就可以了。
int mod (int a, int b)
{
int ret = a % b;
if(ret < 0)
ret+=b;
return ret;
}
and now you can call it like mod(-1,8) and it will appear to be 7.
现在你可以像 mod(-1,8) 一样调用它，它看起来是 7。
Edit: I found a bug in my code. It won't work if b is negative. So I think this is better:
编辑：我在我的代码中发现了一个错误。如果 b 是负数，它将不起作用。所以我认为这是更好的：
int mod (int a, int b)
{
if(b < 0) //you can check for b == 0 separately and do what you want
return -mod(-a, -b);
int ret = a % b;
if(ret < 0)
ret+=b;
return ret;
}
Reference: C++03 paragraph 5.6 clause 4:
参考：C++03第5.6段第4条：
The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined.
二元 / 运算符产生商，二元 % 运算符产生第一个表达式除以第二个表达式的余数。如果 / 或 % 的第二个操作数为零，则行为未定义；否则 (a/b)*b + a%b 等于 a。如果两个操作数都为非负，则余数为非负；如果不是，则余数的符号是 implementation-defined。
回答by P i
Here is a C function that handles positive OR negative integer OR fractional values for BOTH OPERANDS
这是一个 C 函数，它处理两个操作数的正或负整数或小数值
#include <math.h>
float mod(float a, float N) {return a - N*floor(a/N);} //return in range [0, N)
This is surely the most elegant solution from a mathematical standpoint. However, I'm not sure if it is robust in handling integers. Sometimes floating point errors creep in when converting int -> fp -> int.
从数学的角度来看，这无疑是最优雅的解决方案。但是，我不确定它在处理整数方面是否稳健。有时在转换 int -> fp -> int 时会出现浮点错误。
I am using this code for non-int s, and a separate function for int.
我将此代码用于非 int s，并为 int 使用单独的函数。
NOTE: need to trap N = 0!
注意：需要捕获 N = 0！
Tester code:
测试代码：
#include <math.h>
#include <stdio.h>
float mod(float a, float N)
{
float ret = a - N * floor (a / N);
printf("%f.1 mod %f.1 = %f.1 \n", a, N, ret);
return ret;
}
int main (char* argc, char** argv)
{
printf ("fmodf(-10.2, 2.0) = %f.1 == FAIL! \n\n", fmodf(-10.2, 2.0));
float x;
x = mod(10.2f, 2.0f);
x = mod(10.2f, -2.0f);
x = mod(-10.2f, 2.0f);
x = mod(-10.2f, -2.0f);
return 0;
}
(Note: You can compile and run it straight out of CodePad: http://codepad.org/UOgEqAMA)
（注意：您可以直接从 CodePad 编译并运行它：http://codepad.org/UOgEqAMA ）
Output:
输出：
fmodf(-10.2, 2.0) = -0.20 == FAIL!
10.2 mod 2.0 = 0.2
10.2 mod -2.0 = -1.8
-10.2 mod 2.0 = 1.8
-10.2 mod -2.0 = -0.2
fmodf(-10.2, 2.0) = -0.20 == 失败！
10.2 模 2.0 = 0.2
10.2 模 -2.0 = -1.8
-10.2 模 2.0 = 1.8
-10.2 模 -2.0 = -0.2
回答by P i
I have just noticed that Bjarne Stroustrup labels %as the remainderoperator, notthe modulo operator.
我刚刚注意到 Bjarne Stroustrup 标记%为余数运算符，而不是模运算符。
I would bet that this is its formal name in the ANSI C & C++ specifications, and that abuse of terminology has crept in. Does anyone know this for a fact?
我敢打赌，这是它在 ANSI C 和 C++ 规范中的正式名称，而且术语的滥用已经悄然出现。有人知道这是事实吗？
But if this is the case then C's fmodf() function (and probably others) are very misleading. they should be labelled fremf(), etc
但是，如果是这种情况，那么 C 的 fmodf() 函数（可能还有其他函数）就非常具有误导性。它们应该被标记为 fremf() 等
回答by Jens Gustedt
For integers this is simple. Just do
对于整数，这很简单。做就是了
(((x < 0) ? ((x % N) + N) : x) % N)
where I am supposing that Nis positive and representable in the type of x. Your favorite compiler should be able to optimize this out, such that it ends up in just one mod operation in assembler.
我假设它N在x. 你最喜欢的编译器应该能够优化它，这样它就可以在汇编程序中完成一个 mod 操作。
回答by Udayraj Deshmukh
The simplest general function to find the positive modulo would be this- It would work on both positive and negative values of x.
找到正模数的最简单的通用函数是这个 - 它适用于 x 的正值和负值。
int modulo(int x,int N){
return (x % N + N) %N;
}
回答by Cheers and hth. - Alf
The best solution 1for a mathematician is to use Python.
数学家的最佳解决方案 1 是使用 Python。
C++ operator overloading has little to do with it. You can't overload operators for built-in types. What you want is simply a function. Of course you can use C++ templating to implement that function for all relevant types with just 1 piece of code.
C++ 运算符重载与此无关。您不能重载内置类型的运算符。你想要的只是一个函数。当然，您可以使用 C++ 模板，通过 1 段代码为所有相关类型实现该功能。
The standard C library provides fmod, if I recall the name correctly, for floating point types.
fmod如果我没记错名字，标准 C 库为浮点类型提供了 。
For integers you can define a C++ function template that always returns non-negative remainder (corresponding to Euclidian division) as ...
对于整数，您可以定义一个 C++ 函数模板，该模板始终返回非负余数（对应于欧几里德除法）为...
#include <stdlib.h> // abs
template< class Integer >
auto mod( Integer a, Integer b )
-> Integer
{
Integer const r = a%b;
return (r < 0? r + abs( b ) : r);
}
... and just write mod(a, b)instead of a%b.
... 并且只写mod(a, b)而不是a%b.
Here the type Integerneeds to be a signed integer type.
这里的类型Integer需要是有符号整数类型。
If you want the common math behavior where the sign of the remainder is the same as the sign of the divisor, then you can do e.g.
如果您想要余数的符号与除数的符号相同的常见数学行为，那么您可以执行例如
template< class Integer >
auto floor_div( Integer const a, Integer const b )
-> Integer
{
bool const a_is_negative = (a < 0);
bool const b_is_negative = (b < 0);
bool const change_sign = (a_is_negative != b_is_negative);
Integer const abs_b = abs( b );
Integer const abs_a_plus = abs( a ) + (change_sign? abs_b - 1 : 0);
Integer const quot = abs_a_plus / abs_b;
return (change_sign? -quot : quot);
}
template< class Integer >
auto floor_mod( Integer const a, Integer const b )
-> Integer
{ return a - b*floor_div( a, b ); }
… with the same constraint on Integer, that it's a signed type.
... 对 具有相同的约束Integer，即它是有符号类型。
1 Because Python's integer division rounds towards negative infinity.
1 因为 Python 的整数除法向负无穷大舍入。
回答by david
I believe another solution to this problem would be use to variables of type long instead of int.
我相信这个问题的另一个解决方案是使用 long 类型的变量而不是 int 类型的变量。
I was just working on some code where the % operator was returning a negative value which caused some issues (for generating uniform random variables on [0,1] you don't really want negative numbers :) ), but after switching the variables to type long, everything was running smoothly and the results matched the ones I was getting when running the same code in python (important for me as I wanted to be able to generate the same "random" numbers across several platforms.
我只是在处理一些代码，其中 % 运算符返回了一个负值，这导致了一些问题（为了在 [0,1] 上生成统一的随机变量，你并不真正想要负数 :) ），但是在将变量切换到输入 long，一切运行顺利，结果与我在 python 中运行相同代码时得到的结果相匹配（对我来说很重要，因为我希望能够在多个平台上生成相同的“随机”数字。
回答by Kyle Butt
For a solution that uses no branches and only 1 mod, you can do the following
对于不使用分支且仅使用 1 个 mod 的解决方案，您可以执行以下操作
// Works for other sizes too,
// assuming you change 63 to the appropriate value
int64_t mod(int64_t x, int64_t div) {
return (x % div) + (((x >> 63) ^ (div >> 63)) & div);
}
回答by Vovanium
Oh, I hate % design for this too....
哦，我也讨厌这种设计......
You may convert dividend to unsigned in a way like:
您可以通过以下方式将股息转换为无符号：
unsigned int offset = (-INT_MIN) - (-INT_MIN)%divider
result = (offset + dividend) % divider
where offset is closest to (-INT_MIN) multiple of module, so adding and subtracting it will not change modulo. Note that it have unsigned type and result will be integer. Unfortunately it cannot correctly convert values INT_MIN...(-offset-1) as they cause arifmetic overflow. But this method have advandage of only single additional arithmetic per operation (and no conditionals) when working with constant divider, so it is usable in DSP-like applications.
其中 offset 最接近 (-INT_MIN) 模数的倍数，因此加减它不会改变模数。请注意，它具有无符号类型，结果将为整数。不幸的是，它无法正确转换值 INT_MIN...(-offset-1) 因为它们会导致 arifmetic 溢出。但是这种方法在使用常量除法器时每个操作只有一个附加算术（并且没有条件）的优点，因此它可用于类似 DSP 的应用程序。
There's special case, where divider is 2N(integer power of two), for which modulo can be calculated using simple arithmetic and bitwise logic as
有一种特殊情况，其中除法器为 2 N（2 的整数幂），可以使用简单的算术和按位逻辑计算模数为
dividend&(divider-1)
for example
例如
x mod 2 = x & 1
x mod 4 = x & 3
x mod 8 = x & 7
x mod 16 = x & 15
More common and less tricky way is to get modulo using this function (works only with positive divider):
更常见且不太棘手的方法是使用此函数求模（仅适用于正分频器）：
int mod(int x, int y) {
int r = x%y;
return r<0?r+y:r;
}
This just correct result if it is negative.
如果它是负数，这只是正确的结果。
Also you may trick:
你也可以欺骗：
(p%q + q)%q
(p%q + q)%q
It is very short but use two %-s which are commonly slow.
它很短，但使用两个通常很慢的 %-s。
回答by TemplateRex
Here's a new answer to an old question, based on this Microsoft Research paperand references therein.
这是一个旧问题的新答案，基于这篇Microsoft Research 论文和其中的参考资料。
Note that from C11 and C++11 onwards, the semantics of divhas become truncation towards zero(see [expr.mul]/4). Furthermore, for Ddivided by d, C++11 guarantees the following about the quotient qTand remainder rT
请注意，从 C11 和 C++11 开始， 的语义div已变为向零截断（请参阅参考资料[expr.mul]/4）。此外，对于D除以d，C++11 保证以下关于商qT和余数rT
auto const qT = D / d;
auto const rT = D % d;
assert(D == d * qT + rT);
assert(abs(rT) < abs(d));
assert(signum(rT) == signum(D));
where signummaps to -1, 0, +1, depending on whether its argument is <, ==, > than 0 (see this Q&Afor source code).
wheresignum映射到 -1, 0, +1，取决于它的参数是否是 <, ==, > than 0（请参阅此问答以获取源代码）。
With truncated division, the sign of the remainder is equal to the sign of the dividend D, i.e. -1 % 8 == -1. C++11 also provides a std::divfunction that returns a struct with members quotand remaccording to truncated division.
对于截断除法，余数的符号等于被除数的符号D，即-1 % 8 == -1。C++11 还提供了一个std::div函数，该函数返回一个带有成员quot并rem根据截断除法的结构体。
There are other definitions possible, e.g. so-called floored divisioncan be defined in terms of the builtin truncated division
还有其他可能的定义，例如所谓的地板除法可以根据内置的截断除法来定义
auto const I = signum(rT) == -signum(d) ? 1 : 0;
auto const qF = qT - I;
auto const rF = rT + I * d;
assert(D == d * qF + rF);
assert(abs(rF) < abs(d));
assert(signum(rF) == signum(d));
With floored division, the sign of the remainder is equal to the sign of the divisor d. In languages such as Haskell and Oberon, there are builtin operators for floored division. In C++, you'd need to write a function using the above definitions.
使用地板除法时，余数的符号等于除数的符号d。在 Haskell 和 Oberon 等语言中，有用于地板除法的内置运算符。在 C++ 中，您需要使用上述定义编写一个函数。
Yet another way is Euclidean division, which can also be defined in terms of the builtin truncated division
另一种方法是欧几里得除法，它也可以根据内置的截断除法来定义
auto const I = rT >= 0 ? 0 : (d > 0 ? 1 : -1);
auto const qE = qT - I;
auto const rE = rT + I * d;
assert(D == d * qE + rE);
assert(abs(rE) < abs(d));
assert(signum(rE) != -1);
With Euclidean division, the sign of the remainder is always positive.
使用欧几里德除法，余数的符号始终为正。
