为什么在C++中使用取模运算符时会输出负数？

Question

数学:

如果你有这样一个方程:

x = 3 mod 7

x可以是-4，3，10，17等，更一般地说：

x = 3 + k * 7

其中k可以是任何整数。我不知道是否为数学定义了模运算，但因子环肯定是。

Python：

在Python中，当您使用正数m和%时，您将始终获得非负值：

#!/usr/bin/python
# -*- coding: utf-8 -*-

m = 7

for i in xrange(-8, 10 + 1):
    print(i % 7)

结果为：

6    0    1    2    3    4    5    6    0    1    2    3    4    5    6    0    1    2    3

C++：

#include <iostream>

using namespace std;

int main(){
    int m = 7;

    for(int i=-8; i <= 10; i++) {
        cout << (i % m) << endl;
    }

    return 0;
}

将输出：

-1    0    -6    -5    -4    -3    -2    -1    0    1    2    3    4    5    6    0    1    2    3    

ISO/IEC 14882:2003(E) - 5.6 乘法操作符：

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

和

74) 根据正在进行的 ISO C 修订工作，整数除法的首选算法遵循 ISO Fortran 标准，ISO/IEC 1539:1991 中定义的规则，其中商始终向零舍入。

来源：ISO/IEC 14882:2003(E)

我找不到免费版本的ISO/IEC 1539:1991。有人知道在哪里可以获取吗？

这个操作似乎是这样定义的：

问题：这样定义有意义吗？

这个规范的论据是什么？是否有一个讨论创建此类标准的人员的地方？我在哪里可以阅读一些关于为什么决定以这种方式进行的原因的东西？

大多数情况下，当我使用模运算时，我想要访问数据结构的元素。在这种情况下，我必须确保mod返回一个非负值。所以，对于这种情况，mod总是返回一个非负值会很好。 （另一个用法是欧几里得算法。在使用此算法之前，您可以使两个数字都为正数，那么模数的符号就很重要。）

附加材料：

请参阅维基百科以获取不同语言中模运算执行的长列表。

- Martin Thoma

---

C语言（因此也包括C++）的通常原因是现有的硬件以某种方式进行数学运算。语言标准只是记录正在发生的事情（以及未发生的事情）。 - Bo Persson

这个问题的一个有用的补充可能是：“在C++代码中，有什么好的替代方法可以获得Python所显示的行为？” - hertzsprung

一个很好的解决方案，可以得到mod的正值，详见这里：[https://dev59.com/OGct5IYBdhLWcg3wL6qi#12277233] - zardosht

也许问题在于将函数命名为“模数”。如果使用“模数”，它必须是数学方式。如果不是数学方式，那么可以将其命名为其他名称。这篇帖子中的所有答案都令人沮丧。我们很幸运，例如乘法按照数学方式工作。他们本可以发明一个更快的函数并将其命名为乘法。 - Mehmet Kaplan

@zardosht 需要2个慢模除操作，比 int ret = a%b; return ret>=0? ret: ret+b; 更糟糕。可以使用条件移位来完成。 - phuclv

Answer 1

在x86（和其他处理器架构）上，整数除法和取模通过单个操作idiv（对于无符号值为div），产生商和余数（对于字大小的参数，在AX和相应的DX中）。这在C库函数divmod中使用，编译器可以将其优化为单个指令！

整数除法遵守两个规则：

- 非整数商向零舍入；和 - 等式被除数 = 商 * 除数 + 余数 通过结果满足。

因此，当用正数除以负数时，商将是负数（或零）。

因此，这种行为可以看作是一系列局部决策的结果：

- 处理器指令集设计优化常见情况（除法）而不是不常见情况（取模）； - 一致性（向零舍入并遵守除法方程）优先于数学正确性； - C喜欢效率和简洁（特别是考虑到将C视为“高级汇编程序”）；和 - C++倾向于与C兼容。

- ecatmur

---

我想知道在二进制除数非常常见的情况下，截断除法比向下取整除法更快的频率有多高，因为这种除数很容易适用于缩放乘法。 - supercat

Answer 2

早些年，设计x86指令集的人决定将整数除法向零舍入而不是向下舍入。（愿千只骆驼的跳蚤在他母亲的胡须里筑巢。）为了保持某种程度的数学正确性，操作符REM（读作“remainder”）必须相应地行事。请勿阅读此内容：https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/rzatk/REM.htm

我警告过你了。后来，一位制定C规范的人决定编译器可以按照正确方式或x86方式执行此操作。然后，一个制定C++规范的委员会决定采用C的做法。之后，又过了一段时间，一个C++委员会决定标准化错误的方式。现在我们被困在这个问题上了。许多程序员已经编写了以下函数或类似的函数。我可能至少做过十几次。

 inline int mod(int a, int b) {int ret = a%b; return ret>=0? ret: ret+b; }

你的效率就这样降低了。

现在我主要使用以下内容，其中包括一些type_traits的东西。(感谢Clearer的评论，给了我一个改进的想法，使用更晚期的C++。见下文。)

<strike>template<class T>
inline T mod(T a, T b) {
    assert(b > 0);
    T ret = a%b;
    return (ret>=0)?(ret):(ret+b);
}</strike>

template<>
inline unsigned mod(unsigned a, unsigned b) {
    assert(b > 0);
    return a % b;
}

事实：我曾游说Pascal标准委员会正确处理mod，直到他们屈服。令我惊讶的是，他们错误地处理了整数除法。所以它们甚至不匹配。

编辑：Clearer给了我一个想法。我正在开发一个新的。

#include <type_traits>

template<class T1, class T2>
inline T1 mod(T1 a, T2 b) {
    assert(b > 0);
    T1 ret = a % b;
    if constexpr  ( std::is_unsigned_v<T1>)
    {
        return ret;
    } else {
        return (ret >= 0) ? (ret) : (ret + b);
    }
}

- Jive Dadson

---

一个断言 a % b >= 0 是正确的吗？一些平台可能会定义 a % b，以做正确的事情（通过意外、扩展或故意反叛），并断言 a % b >= 0。 - Clearer

@Clearer - 不是，但你给了我一个好主意。请查看编辑后的答案。 - Jive Dadson

@if constexpr 是 C++17 的新特性。 - Jive Dadson

@Clearer - 断言指出：“此函数不适用于处理负b”。如果您想允许b为负数，则需要更复杂的解决方案。[通常情况下，b被认为是正数，只有a有时会倾向于为负数] - ToolmakerSteve

为什么不直接写return (a + b) % b，然后就完成了呢？ - Igor Levicki

Answer 3

这个规范的论点是什么？

C ++ 的设计目标之一是高效映射到硬件。如果底层硬件以产生负余数的方式实现除法，则在 C ++ 中使用 % 运算符将得到这种结果。实际上就是这样。

有没有讨论制定这些标准的人们的地方？

您可以在 comp.lang.c++.moderated 和较少的程度上在 comp.lang.c++ 上找到有趣的讨论。

- fredoverflow

---

这与 C++ 的目标“不用支付你不使用的东西”的理念非常契合。默认情况下永远不会为了方便而牺牲性能。如果你需要检查/取模结果的绝对值，你可以轻松地在需要该行为的任何地方进行包装。 - Preet Kukreti

“高效映射到硬件”的目标是否更好地指定为：如果x或y为负且模数非零，则编译器可以任意返回正数或负数结果？最快的实现（x％123456789）在处理正数时可能会产生负数结果，但最快的实现（x％8）将产生正数。如果y为正数且x可能为负数，则计算（x mod y）的最快方法可能是：m=x%y; if (m<0) m+=y;，即使编译器... - supercat

对于不能被y整除的负x值，/运算符随机返回正数或负数结果。我唯一能看到的是，在/上指定截断为零以及在%上对应的行为所实现的唯一目标就是使像x/=4;或y%=4;这样的操作比它们本来需要的速度慢三倍。你见过任何受益于-5%2=-1的代码吗？ - supercat

@Preet - 我总是希望模运算能够正确地工作，所以我总是为此付出代价。 - Jive Dadson

Answer 4

其他人已经很好地描述了“为什么”，不幸的是提出解决方案的问题被标记为重复的问题，而在这个方面缺乏全面的答案。似乎有两个常用的一般解决方案和一个我想包括的特殊情况：

// 724ms
inline int mod1(int a, int b)
{
  const int r = a % b;
  return r < 0 ? r + b : r;
}

// 759ms
inline int mod2(int a, int b)
{
  return (a % b + b) % b;
}

// 671ms (see NOTE1!)
inline int mod3(int a, int b)
{
  return (a + b) % b;
}

int main(int argc, char** argv)
{
  volatile int x;
  for (int i = 0; i < 10000000; ++i) {
    for (int j = -argc + 1; j < argc; ++j) {
      x = modX(j, argc);
      if (x < 0) return -1;  // Sanity check
    }
  }
}

注意1：这通常是不正确的（即如果a < -b）。我包括它的原因是因为每次我需要对负数取模时，几乎都是在处理已经进行模运算的数字时，例如(i1-i2)%n，其中0 <= iX < n（例如循环缓冲区的索引）。

一如既往，时间可能会有差异。

- Luis