为什么C++在使用模运算时输出负数?

rmbxnbpk  于 2022-11-27  发布在  其他
关注(0)|答案(4)|浏览(207)

数学

如果你有一个这样的方程:

x = 3 mod 7

x可以是...... -4、3、10、17、......,或者更一般地说:

x = 3 + k * 7

其中k可以是任意整数,我不知道数学中有没有模运算的定义,但是因子环肯定是。
巨蟒:
在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的免费版本。有人知道从哪里可以得到它吗?)
该操作似乎是这样定义的:

问题

这样定义有意义吗?
这个规范的论据是什么?有没有一个地方可以让创建这样的标准的人讨论它?在那里我可以读到一些关于他们决定这样做的原因的东西?
大多数时候,当我使用modulo时,我想访问数据结构的元素。在这种情况下,我必须确保mod返回一个非负值。因此,在这种情况下,mod总是返回一个非负值是很好的。(另一种用法是欧几里得算法。因为在使用该算法之前,你可以使两个数字都为正,所以modulo的符号很重要。)

其他材料

参见Wikipedia,了解模在不同语言中的作用。

pb3s4cty

pb3s4cty1#

在x86上(和其他处理器架构),整数除法和取模运算通过单个运算idiv执行。(div表示无符号值),它同时生成商和余数(对于字长参数,分别为AXDX)。这在C库函数divmod中使用,编译器可以将其优化为单个指令!
整数除法遵循两个规则:

  • 非整数商舍入为零;和
  • 结果满足方程dividend = quotient*divisor + remainder

因此,当负数除以正数时,商将为负(或零)。
因此,这种行为可以看作是一系列局部决策的结果:

  • 处理器指令集设计针对常见情况(除法)而不是不太常见的情况(模)进行优化;
  • 一致性(向零舍入,并遵守除法方程)优于数学正确性;
  • C更喜欢效率和简单(特别是考虑到将C视为“高级汇编程序”的趋势);和
  • C++更倾向于与C兼容。
8xiog9wr

8xiog9wr2#

当年,设计x86指令集的某个人认为整数除法向零取整比向下取整更好。(愿一千只 Camel 的跳蚤在他母亲的胡子里筑巢。)为了保持某种数学正确性的表象,运算符REM(读作“余数”)必须相应地表现。不要阅读以下内容:https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/rzatk/REM.htm
我警告过你。后来有人做C规范决定编译器要么用正确的方式要么用x86的方式。然后一个做C规范的委员会决定用C的方式。后来,在这个问题被贴出来之后,一个C委员会决定用错误的方法标准化。2现在我们被它卡住了。许多程序员都写过下面的函数或类似的东西,我大概写过至少十几次。

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

x7yiwoj43#

此规范的参数是什么?
C的设计目标之一是有效地Map到硬件。如果底层硬件以产生负余数的方式实现除法,那么如果你在C中使用%,你将得到负余数。这就是它的全部内容。
有没有一个地方让制定这些标准的人讨论它?
您将在comp.lang.c++.moderated和comp.lang.c++(在较小程度上)上找到有趣的讨论。

egdjgwm8

egdjgwm84#

其他人已经很好地描述了 * 为什么 *,不幸的是the question which asks for a solution被标记为这个问题的重复,似乎缺少一个全面的答案。似乎有两个常用的一般解决方案和一个特例,我想包括在内:

// 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(例如循环缓冲区的索引)。
一如既往,YMMV在时机方面。

相关问题