logo标签列表

某些编程语言为什么允许使用负数取模？

javacmathmodulus
12

我对那些忽略了模运算的数学定义的编程语言（Java，C……）很好奇。

为什么在模运算中返回负值（根据定义应该总是返回正数）？有何意义？

12
没有任何定义说任何事情都应该是“始终积极的”。模运算是关于等价类的，任何代表都和其他代表一样好。 - Kerrek SB
2
虽然拥有一个产生规范代表的模数运算会很好。 - hmakholm left over Monica
1
@Matt：是的，隐含了这个条件。它强制要求 (a/b)*b+a%b==a，并且除法朝着零截断。 - Oliver Charlesworth
2
@KerrekSB 这里的问题是负数与正数不同于数学模运算，它们属于不同的等价类。 - soulcheck
1
(time_t)(-10000) 是哪个(GMT)时间？如果你回答了21:13:20而不是-2:-46:-40，那么你可能会更喜欢Python对%的定义，胜过于C99。 - dan04
显示剩余10条评论
6个回答
8
在Java中，它不是模运算符，而是余数运算符。
我相信之所以选择这种方式，是为了使这个关系成立（来自JLS）：
对于经过二进制数字提升（§5.6.2）后是整数的操作数，余数运算产生一个结果值，使得（a/b）* b +（a％b）等于a。即使被除数是其类型的最大可能大小的负整数，而除数是-1（余数为0）的特殊情况也适用此标识。根据这个规则，余数运算的结果只有在被除数为负数时才能为负数，并且只有在被除数为正数时才能为正数；此外，结果的大小总是小于除数的大小。
这个等式关系似乎是作为定义的一部分使用的合理东西。如果您认为向零截断的除法已经确定，那么就会留下一个负余数。
@JerryCoffin：是的，但与截断为0的除法结合使用，你最终会得到这个结果。我会在我的回答中添加关于除法的部分。 - Jon Skeet
在C99中，同样的情况也是广泛存在的：运算符除了“%”没有其他名称，但其结果是“余数”；并且a和b之间的欧几里得关系也是相同的（除了C语言没有针对INT_MIN % -1的特殊情况——这是未定义的行为）。 - caf
2
@JerryCoffin：实际上我认为你是对的——INT_MIN / -1可能由于整数溢出而未定义，但似乎余数仍应为零。然而，我可以通过那个操作让gcc发出SIGFPE信号... - caf
@JerryCoffin：看起来R.和Jens在我们之前就已经到过这里了 - 当前的草案标准现在明确将其列为未定义行为。 - caf
@JerryCoffin: 我不确定你指的是哪个评论 - INT_MIN / -1 由于有符号整数溢出而导致未定义行为，就像 INT_MAX + 1 一样。草案中引用的新语言特别指出 % 运算符的 行为 是未定义的。 - caf
显示剩余6条评论
6

来自 维基百科 (我的强调):

给定两个正数，a（被除数）和n（除数），a模n（简写为a mod n）可以视为在a被n整除时的余数。例如，“5 mod 4”的表达式将计算结果为1，因为5被4除后余数为1，而“9 mod 3”的结果将计算为0，因为9被3除后余数为0；在乘以3次3之后，9没有需要减去的部分了。（请注意，用计算器执行除法不会显示此操作所引用的结果，商将表示为小数。）当a或n为负数时，这个朴素的定义就会失效，编程语言在如何定义这些值方面存在差异。虽然通常使用整数作为a和n的数据类型，但许多计算系统允许其他类型的数字操作数。 对于n的整数取模的数字范围是0到n-1。（n mod 1始终为0；n mod 0未定义，可能导致计算机编程语言中的“除以零”错误）有关在数论中应用的更古老和相关的约定，请参见模运算。

从数学上讲，整数的余数始终在0到除数减1的范围内，假设除数为正数。这与编程语言（和CPU）倾向于使用的丑陋定义相冲突。前者的定义非常有用，例如用于日期计算。后者除了将整数用作非整数值的近似值（例如定点数）时几乎没有用处。 - R.. GitHub STOP HELPING ICE
@R..：我不会说“数学上”（除非你有一些真正的理论来支持这个观点），而是“惯例上”。（对于正股息，这只与负除数相关。） - Kerrek SB
2
我学过的除法的代数定义是 n=qd+r，其中 0≤r<d。 :-) - R.. GitHub STOP HELPING ICE
@R..：实际上，这是一个很好的观点——这仍然只是惯例，但这是除法定理被陈述的流行方式。(尽管请注意，该定理对于任何其他固定余类的选择同样有效。) 话虽如此，这是支持将余数固定为正值的一个不错的论据。 - Kerrek SB
6
我怀疑取余运算符不是有意设计成具有这些语义的，我认为这些语义并不是非常有用。（你会编写一个日历程序，在纪元前显示星期天、反周六、反周五等吗？）
相反，负余数是整数除法定义方式的副作用。
A rem B := A - (A div B) * B

如果定义A div B为trunc(A/B)，则得到C的%运算符。如果定义A div B为floor(A/B)，则得到Python的%运算符。其他定义也是可能的。
因此，真正的问题是：
为什么C ++、Java、C＃等使用截断整数除法？
因为这就是C的方法。
为什么C使用截断除法？
最初，C没有规定/如何处理负数。它留给硬件来处理。
事实上，每个重要的C实现都使用了截断除法，因此在1999年这些语义正式成为C标准的一部分。
为什么硬件使用截断除法？
因为它更容易（更便宜）在无符号除法方面实现。您只需计算abs(A) div abs(B)，并在(A < 0) xor (B < 0)的情况下翻转符号。
如果余数不为零，则Floored除法需要从商中减去1。
我想知道C99版本的有符号除法在哪些应用程序中实际上是有用的？根据我的经验，在需要精确计算的情况下，我几乎总是需要特别处理负数，因此涉及负数的除法返回未指定的值并不比按照标准规定的行为更有用。我可以理解为什么要将行为保留为未指定（这可能会加快缺少有符号除法指令的硬件的速度），但按照现有标准没有太多优势。 - supercat
3
大部分编程语言中，所述运算符未定义返回模数。它们仅定义返回余数，正负值都有合理性。
在 C 或 C++ 中，它很合理地产生底层硬件生成的结果。但这个借口 / 理由在 Java 中并不那么管用。
另外请注意，在 C89/90 和 C++98/03 中，余数可以是正数或负数，只要余数和除法的结果配合使用（(a/b)*b+a%b == a）即可。在 C99 和 C++11 中，规则已经被加强，以便除法必须向零截取，如果有余数，则余数必须为负数。
1

返回模数的负值的实用原因可能是硬件指令实现模数。

因此，标准将其定义不清，以便编译器可以执行对它们更简单的操作。

3
例如在一些标准中已经有了明确定义，例如 Java 和 C99。 - Oliver Charlesworth
你确定C99定义了负数的情况吗？ - Basile Starynkevitch
1
是的。它是通过/运算符定义的，其行为现在对于负值已经有了明确定义。 - Oliver Charlesworth
1

在 C 或 Java 标准中，% 不被称为模运算符，而是返回 余数。

它被定义为对于负被除数返回负数，以便关系式 (a/b)*b + a%b == a 成立，只要 a / b 是可表示的。由于除法运算符被定义为向零截断，这限制了余数的符号。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接