如何在C/C++/Obj-C中编写一个能处理负数的取模（%）运算符

Question

作为一名数学家，我对C衍生语言之一的一个小恶习是

(-1) % 8 // comes out as -1, and not 7

fmodf(-1,8) // fails similarly

最佳解决方案是什么？

C++允许使用模板和操作符重载，但这两者对我来说都是比较深奥的领域。欢迎提供示例。

- P i

---

我认为这不完全是 https://dev59.com/-XRA5IYBdhLWcg3wyBD1 的“重复”。根据官方定义，这个问题的答案不能合并到那个问题中，因为这个问题只问模数，而不涉及除法。但我认为这个问题已经被那个问题覆盖了，所以很接近。我的答案已经在那里了。 - Steve Jessop

也许应该将那个线程拆分，因为它提出了两个不同的问题。最好的方法可能是单独重新提出分割问题，然后将其指向该答案。我会把这个任务留给更了解这个网站机制的人。 - P i

@Pi owhere在哪里说“％”是“模数”...它是“余数”。 - obataku

以下是关于“%”问题的参考链接，这也是一个与此问题“重复”的线程：https://dev59.com/X3NA5IYBdhLWcg3wH6EW - leetNightshade

如果你只是在进行2的幂次数除法，那么使用按位与符号&可能是更好的选择：(-1) & 8 == 7 - Henricus V.

@Henry W. (-1) & 8 == 7？(-1) & 8只会产生0或8，而不是7。也许你的意思是(-1) & (8-1)？ - chux - Reinstate Monica

Answer 1

首先我想指出的是，你甚至不能指望 (-1) % 8 == -1 这样的事实。唯一可以依赖的是 (x / y) * y + ( x % y) == x。但余数是否为负数是由具体实现定义的。

参考文献：C++03 第5.6款第4条：

二元 / 运算符生成商，而二元 % 运算符生成从第一个表达式除以第二个表达式的余数。如果 / 或 % 的第二个操作数为零，则行为未定义；否则（a/b）*b + a%b 等于 a。如果两个操作数都是非负的，则余数是非负的; 如果不是，则余数的符号是由具体实现定义的。

下面是一个处理负操作数的版本，这样从余数中减去除数的结果就可以从被除数中减去，这样就可以得到实际除法的 floor 结果。 mod(-1,8) 的结果为7，而 mod(13,-8) 则为-3。

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;
}

- Armen Tsirunyan

---

@Ohmu：是的，这是C++标准中规定的。对于整数操作数，/运算符产生代数商，并舍去任何小数部分；如果商a/b可以在结果类型中表示，则（a/b）* b + a％b等于a。 - Ben Voigt

自从11年前实现方式变更以来，这个问题一直没有得到解决。ISO 9899:1999标准对此进行了定义，但不幸的是选择了错误的定义。 - R.. GitHub STOP HELPING ICE

你方便地删除了脚注 <quote>... 整数除法遵循 ISO Fortran 标准 ISO/IEC 1539:1991 中定义的规则，其中商始终向零舍入 </quote>。 新版 C++ 标准将此行为从“首选”升级为强制执行，就像 Fortran 和 C 一样。 - Ben Voigt

@Armen：旧规范已经失效，但破裂与符号问题不同，除非您查看新措辞否则很容易被忽略。C++03没有“如果商a / b可以在结果类型中表示”，这会对INT_MIN / -1（在二进制补码实现中）造成问题。根据旧规范，-32768％-1可能必须评估为-65536（也不在16位类型的范围内，呃！）以满足标识。 - Ben Voigt

然而，“余数是否为负是实现定义的”这一点，C++11保证整数除法向0舍入。 - Cheers and hth. - Alf

Answer 2

这是一个处理正数或负数整数或小数值的C函数，适用于两个运算数。

#include <math.h>
float mod(float a, float N) {return a - N*floor(a/N);} //return in range [0, N)

从数学角度来看，这肯定是最优雅的解决方案。但是我不确定它在处理整数时是否强大。有时候在将int -> fp -> int转换时会出现浮点误差。

我正在使用这段代码处理非整数s，并使用另一个函数处理整数。

注意：需要捕获N = 0！

测试代码：

#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;
}

(注意：您可以直接在CodePad上编译和运行它：http://codepad.org/UOgEqAMA)

输出：

fmodf(-10.2, 2.0) = -0.20 == 失败！

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

- P i

---

不幸的是，这对整数无效。在除法之前，它们需要转换为浮点数才能允许您使用 floor()。此外，当您转换为浮点数时，可能会失去精度：尝试 (float)1000000001/3，您会惊讶于结果！ - cmaster - reinstate monica

这个很好用，我正在寻找替代使用负数a参数的fmod()函数的不良用法。 - Kingsley

Answer 3

我刚刚注意到Bjarne Stroustrup将%标记为余数运算符，而不是模运算符。

我敢打赌，在ANSI C和C++规范中，这是它的正式名称，并且术语的误用已经渗入其中。有人知道这件事吗？

但如果是这样的话，C的fmodf()函数（以及可能还有其他函数）就会非常误导人。它们应该被标记为fremf()等。

- P i

---

C11标准（或确切的公共草案）提到“模数”六次，但仅涉及各种类型的表示。它从未在与余数运算符（%）有关的情况下提到“模数”。 - Nisse Engström

Answer 4

最简单的通用函数来找到正模数是这样的—它适用于x的正负值。

int modulo(int x,int N){
    return (x % N + N) %N;
}

- Udayraj Deshmukh

Answer 5

对于整数，这很简单。只需执行

(((x < 0) ? ((x % N) + N) : x) % N)

我假设N是正数并且可以在x的类型中表示。您喜欢使用的编译器应该能够优化此操作，使其最终成为汇编中的一个模运算。

- Jens Gustedt

---

有误：对于 int x=-9001; unsigned int N=2000;，它给出的结果是2295，而不是999。 - Hubert Kario

@HubertKario 也许再检查一下？模2000的结果不可能是2295，你一定犯了错误。 - sam hocevar

@SamHocevar：我认为这里的问题在于奇怪的C整数提升规则。有符号整数提升为无符号整数，将负的有符号整数值提升为无符号整数会在C中引发未定义行为。 - datenwolf

我相信一个更简单（更有效）的形式是：(x < 0) ? (x % N + N) : (x % N)。 - Chris Nolet

Answer 6

以下是一篇基于微软研究论文及其参考文献的关于一个旧问题的新答案。

请注意，从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) || rT == 0);

signum 将其参数映射为 -1、0、+1，具体取决于其参数是 <、== 还是 > 0（有关源代码，请参见 this Q&A）。

通过截断除法，余数的符号等于被除数 D 的符号，即 -1 % 8 == -1。C++11 还提供了一个 std::div 函数，根据截断除法返回一个带有成员 quot 和 rem 的结构体。

还有其他可能的定义，例如所谓的向下取整除法可以根据内置的截断除法来定义。

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));

使用向下取整除法，余数的符号等于除数d的符号。在Haskell和Oberon等语言中，有内置的向下取整除法运算符。在C++中，您需要编写一个使用上述定义的函数。

另一种方法是欧几里得除法，它也可以用内置的截断除法来定义。

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) >= 0);

使用欧几里得除法，余数的符号始终为非负数。

- TemplateRex

---

assert(signum(rT) == signum(D)); can definitely fail. Correct statement: signum(rT) is a member of the set { 0, signum(D) }, or as an assert assert(rT == 0 || signum(rT) == signum(D)); - Ben Voigt

@BenVoigt，你能给出一个会触发断言的反例吗？ - TemplateRex

反例：D = 10 和 d = 5 - Ben Voigt

你的答案中最后一个加粗语句也是错误的，应该是“非负”而不是“正数”。 - Ben Voigt

@BenVoigt 谢谢您提供的建议修改，我已经更新了答案。顺便说一下，我使用了一个自己编写的库来编写这个答案，该库已经包含了您的建议修改，但是我忘记将其添加到这个答案中。请参见 https://github.com/rhalbersma/xstd/blob/master/include/xstd/cstdlib.hpp - TemplateRex

Answer 7

对于数学家来说，最好的解决方案¹是使用Python。

C++运算符重载与此无关。您无法为内置类型重载运算符。您想要的只是一个函数。当然，您可以使用C++模板将该函数实现为所有相关类型的1个代码片段。

标准C库提供了fmod，如果我记得名字正确的话，用于浮点类型。

对于整数，您可以定义一个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);
}

...只需编写mod(a, b)，而不是a％b。

在这里，类型Integer需要是有符号整数类型。

如果您希望具有常见的数学行为，其中余数的符号与除数的符号相同，则可以执行以下操作：

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 ); }

… 在相同的限制条件下，Integer 是有符号类型。

---

^{¹ 因为 Python 的整数除法向负无穷取整。}

- Cheers and hth. - Alf

---

@Armen：谢谢！但是我懒得为了这个去编辑... :-) - Cheers and hth. - Alf

@ArmenTsirunyan：r 的结果必须使 a = r + b*(a/b) 成立。无论整数除法如何实现，b*something 都是 b 的倍数。即使为负数，这使得 r 成为有效的模数结果。您可以将 abs(b) 加到它上面，它仍然是一个有效的模数结果。 - Cheers and hth. - Alf

@downvoters：这个答案仍然是正确的，而所选的“解决方案”现在包含了由于C++11中的新保证而导致的不正确评论。下降投票一个仍然正确的答案是相当具有讽刺意味的。如果没有给出理由，那么人们必须假设至少有两个联想的人，几乎完全无知，阅读了这个问题的评论并膝跳反应地投了反对票。请解释一下你们的反对票。 - Cheers and hth. - Alf

数学上期望的结果是余数为零或与除数（分母）具有相同的符号。如果除数为负，则余数应为零或负数。C/C++实现的结果是余数为零或与被除数（分子）具有相同的符号。 - rcgldr

@rcgldr：然而我不确定Fortran是否具有数学语义，因为C++从Fortran中获得了当前（C++11后）的舍入规则，即向0舍入。 - Cheers and hth. - Alf

Answer 8

如果要使用不带分支和只有1个模运算的解决方案，您可以执行以下操作：

// 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);
}

- Kyle Butt

Answer 9

哦，我也讨厌这种百分号设计……

你可以通过以下方式将除数转换为无符号数：

unsigned int offset = (-INT_MIN) - (-INT_MIN)%divider

result = (offset + dividend) % divider

偏移量应该尽可能靠近模数的(-INT_MIN)倍，这样加减它不会改变模数。请注意，它具有无符号类型，结果将为整数。不幸的是，它不能正确地转换值INT_MIN...(-offset-1)，因为它们会导致算术溢出。但是，在使用常数除法时，此方法每个操作仅需要单个附加算术（和无条件语句），因此在类DSP应用程序中可用。

有一种特殊情况，即除数为2的N次方（整数的二次幂），可以使用简单的算术和按位逻辑计算模数，如下所示：

dividend&(divider-1)

例如

x mod 2 = x & 1
x mod 4 = x & 3
x mod 8 = x & 7
x mod 16 = x & 15

更常见且不那么棘手的方法是使用此函数获取模数（仅适用于正除数）：

int mod(int x, int y) {
    int r = x%y;
    return r<0?r+y:r;
}

如果结果为负数，这只是正确的结果。

还有一个技巧：

(p%q + q)%q

这很简短，但使用了两个通常很慢的%-s。

- Vovanium

Answer 10

我认为解决这个问题的另一个方法是使用长整型变量，而不是整型变量。

我刚刚在编写代码时遇到了一些问题，其中%操作符返回了负值，这导致了一些问题（生成[0,1]上均匀随机变量时，您确实不希望出现负数:)），但是将变量更改为长整型后，一切顺利进行，并且结果与我在python中运行相同代码时得到的结果相匹配（对我很重要，因为我希望能够在几个平台上生成相同的“随机”数字）。

- david