68

数学：

如果你有这样的等式：

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。有人知道从哪里得到它吗？）

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

在此处输入图像描述

问题：

这样定义有意义吗？

该规范的论据是什么？创建此类标准的人是否有讨论它的地方？我可以在哪里阅读有关他们决定这样做的原因的信息？

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

附加材料：

有关模数在不同语言中的作用的长列表，请参阅Wikipedia。

4

3 回答 3

38

在 x86（和其他处理器架构）上，整数除法和取模由单个操作idiv（div对于无符号值）执行，该操作同时产生商和余数（对于字大小的参数，分别为 inAX和DX）。这是在C库函数中使用的divmod，可以被编译器优化为单条指令！

整数除法遵循两个规则：

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

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

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

  • 处理器指令集设计针对不太常见的情况（模）优化常见情况（除法）；
  • 一致性（向零舍入，并尊重除法方程）优于数学正确性；
  • C 更喜欢效率和简单（特别是考虑到将 C 视为“高级汇编程序”的趋势）；和
  • C++ 更喜欢与 C 兼容。
于 2012-07-24T12:43:05.163 回答
19

过去，设计 x86 指令集的人认为将整数除法向零舍入而不是向下舍入是正确和好的。（愿一千只骆驼的跳蚤在他母亲的胡须里筑巢。）为了保持某种数学正确性，操作员 REM（发音为“余数”）必须做出相应的行为。请勿阅读：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);
    }
}
于 2018-01-24T09:51:22.950 回答
10

What are arguments for this specification?

One of the design goals of C++ is to map efficiently to hardware. If the underlying hardware implements division in a way that produces negative remainders, then that's what you'll get if you use % in C++. That's all there is to it really.

Is there a place where the people who create such standards discuss about it?

You will find interesting discussions on comp.lang.c++.moderated and, to a lesser extent, comp.lang.c++

于 2012-07-24T12:08:30.130 回答