为什么在许多脚本语言中整数除法会向下取整？

Question

在我测试过的语言中，-（x div y）与-x div y不相等；我在Python中测试了//，在Ruby中测试了/，在Perl 6中测试了div；C语言有类似的行为。

由于div通常被定义为除法结果向下取整，因此这种行为通常符合规范，但从算术角度来看，它没有太多意义，因为它使得div根据符号的不同而表现出不同的行为，并且引起混淆，例如Python的实现方式。

这种设计决策背后是否有特定的原理，还是简单地从头定义了div？显然，Guido van Rossum在一篇博客文章中使用了一种连贯性论点来解释Python中如何进行整数除法，但是如果你选择向上取整，同样可以实现连贯性。

（受PMurias在＃perl6 IRC频道中提出的这个问题的启发）

- jjmerelo

---

顺便提一下，在Python中，“//”被称为地板除法。试试这个：.7 // .1。请注意，它不会评估为“int”。 - PM 2Ring

在Python中，你可以使用双重否定来进行向上取整除法：例如 -（-23 // 10）。 - PM 2Ring

Answer 1

理想情况下，我们希望有两个操作div和mod，满足每个b>0：

1. (a div b) * b + (a mod b) = a
2. 0 <= (a mod b) < b
3. (-a) div b = -(a div b)

然而，这在数学上是不可能的。如果以上所有条件都成立，那么我们将会得到：

1 div 2 = 0
1 mod 2 = 1

由于这是方程（1）和（2）的唯一整数解。因此，根据（3），我们也有

0 = -0 = -(1 div 2) = (-1) div 2

由（1）可推出

-1 = ((-1) div 2) * 2 + ((-1) mod 2) = 0 * 2 + ((-1) mod 2) = (-1) mod 2

使得 (-1) mod 2 < 0，与 (2) 相矛盾。

因此，我们需要放弃 (1)，(2) 或 (3) 中的某些属性。

有些编程语言放弃了 (3)，并且使 div 向下取整 (如 Python、Ruby)。

在一些（罕见的）情况下，语言提供多个除法运算符。例如，在 Haskell 中，我们有 div,mod 只满足 (1) 和 (2)，类似于 Python；还有 quot,rem 只满足 (1) 和 (3)。后面一组操作符将除法向零舍入，但付出的代价是返回负余数，例如，我们有 (-1) `quot` 2 = 0 和 (-1) `rem` 2 = (-1)。

C# 也放弃了 (2)，并允许 % 返回负余数。一致地，整数除法向零舍入。从 C99 开始，Java、Scala、Pascal 和 C 也采用了这种策略。

- chi

---

C# 放弃了（2）。C# 中的 % 运算符不是“mod”运算符，而是“remainder”运算符，而余数可以是负数。 - Eric Lippert

只是出于好奇，如果是这样的话，为什么操作符的标识字符串是op_Modulus而不是op_Remainder？ - Heinzi

没有我能够确定的充分理由。这只是一个非常长的小错误清单中的又一个，并不真正重要。 - Eric Lippert

Answer 2

浮点数运算是由IEEE754标准定义的，主要用于数字应用，并默认以非常严格的方式四舍五入到最接近的可表示值。

计算机中的整数运算没有被国际通用标准定义。语言提供的操作（特别是C家族的语言）往往遵循底层计算机提供的操作。一些语言比其他语言更强大地定义了某些操作，但为了避免在其时代可用的（和流行的）计算机上进行过于困难或缓慢的实现，会选择一个紧密跟随其行为的定义。

因此，整数运算倾向于在溢出时环绕（对于加法、乘法和左移），并在产生不精确结果时向负无穷方向取整（对于除法和右移）。这两个操作都在整数的两个补码二进制算术的各自端点处简单地截断；处理角落情况的最简单方法。

其他的回答讨论了语言可能会提供的余数或模数运算符与除法之间的关系。不幸的是，它们的顺序相反了。余数取决于除法的定义，而不是相反，而模数可以独立于除法定义 - 如果两个参数都是正数并且除法向下舍入，则它们计算出来的结果相同，因此人们很少注意到。

大多数现代语言都提供余数或模数运算符，很少同时提供两者。对于那些关注差异的人，库函数可以提供另一个操作，即余数保留被除数的符号，而模数保留除数的符号。

- Chromatix

---

这是一个有趣的观点，也因为您提到了模算术。您认为如果问题是：“为什么在许多脚本语言中整数除法会向上取整？”，同样的答案是否适用？ - iGian

@iGian 事实上，大多数语言在整数除法时不会四舍五入，原因如我在答案中所述。通常它们要么调用CPU的DIV指令并接受其结果，要么调用一个实现欧几里得除法的子程序并执行相同的操作。一个合理的问题可能是“为什么语言X在大多数其他语言不这样做时会四舍五入（或向最近的整数，或朝零方向）？”-但您必须指定X，并且答案将针对该语言。 - Chromatix

就是这样，我手头没有一个，你是提出这个问题的人。有几个处理整数操作数并默默地强制执行浮点除法的例子，除非你明确指定否则它们会执行浮点除法；例如BBC BASIC将“ /”定义为FP div，“ DIV”定义为整数舍入。 6502甚至没有DIV指令，所以需要使用子程序来实现。 - Chromatix

@GOTO0: “向零取整”舍入模式的名称为“截断”。例如，浮点数trunc()函数：https://en.cppreference.com/w/c/numeric/math/trunc。如果您将整数除法视为产生实数的数学除法，然后将其四舍五入为整数，则截断舍入模式表达了该行为。当然，这不是实际内部实现的方式。顺便说一下，对于算术右移，向负无穷大显然是2的补码最简单的方法：您只需将符号位的副本移入即可。 - Peter Cordes

@PeterCordes：实际上，“截断”只描述了在符号-幅度表示法中朝向零舍入，例如IEEE-754浮点数。在二进制补码表示法中，截断实际上是朝负无穷舍入，而通过在最高有效端插入符号位的简单方法就可以得到这种结果。特别地，如果0xFFFF是-1，则0xFFFE是-2。 - Chromatix

Answer 3

整数除法的含义是包括余数在内的完整答案。

- Paula Thomas

---

...并且根据定义余数必须始终为正数吗？显然，并非在每种编程语言中都是这样：在C99中，余数与被除数具有相同的符号。 - jjmerelo

是的，没错，而且评论长度的下限让我发疯了！ - Paula Thomas

在Python中，余数（使用％或divmod()）始终与除数具有相同的符号。例如，123％-10-> -7。 - PM 2Ring

据维基百科关于求模运算的条目所述，这只是一种约定成俗的问题：“当a或n为负数时，朴素的定义就会失效，并且各种编程语言在如何定义这些值方面存在差异。” - jjmerelo

Answer 4

维基百科有一篇非常好的文章，介绍了其历史和理论。

---

只要一个语言满足欧几里得除法属性，即 (a/b) * b + (a%b) == a，向下取整和截断除法都是连贯且算术上合理的。

---

当然，人们喜欢争论哪个显然是正确的，哪个显然是错误的，但这更像是一场神圣的战争，而不是一场明智的讨论，通常更多地与他们早期选择的语言有关。他们也经常主要针对自己选择的%进行辩论，尽管先选择/，然后再选择相匹配的%可能更有意义。

• 向下取整（如Python）：
  • 没有比Donald Knuth更权威的人提出过这个建议。
  • 据说约70%的学生猜测%遵循除数的符号
  • 运算符通常被读作mod或modulo，而不是remainder。
  • "C也这么做"——这甚至不是真的。¹
• 截断（如C++）：
  • 使整数除法与IEEE浮点除法（默认舍入模式）更一致。
  • 更多的CPU实现它。（可能在历史上的不同时期不是真的。）
  • 运算符被读作modulo，而不是remainder（即使这实际上反对了他们的观点）。
  • 除法属性在概念上更多涉及到余数而不是模数。
  • 运算符被读作mod，而不是modulo，因此应该遵循Fortran的区别。（这听起来可能很傻，但可能是C99的决定因素。请参见这个线程。）
• 欧几里得（如Pascal-/根据符号向下取整或截断，因此%永远不会是负数）：
  • Niklaus Wirth认为，没有人会感到正数mod令人惊讶。
  • 后来，Raymond T. Boute认为不能用任一其他规则朴素地实现欧几里得除法。

许多编程语言都提供了这两种操作。通常情况下（比如Ada、Modula-2、一些Lisp方言、Haskell和Julia），这些语言使用与 Python 中 mod 运算符相关的名称来表示这个操作，而使用与 C++ 中的运算符相关的名称来表示余数操作符。但并非总是如此，例如Fortran将它们称为模数(modulo)和mod(就像C99中提到的一样)。

---

我们不知道 Python、Tcl、Perl以及其他有影响的脚本语言为什么大多选择 floor 型除法。正如问题中所指出的那样，Guido van Rossum 的回答只是解释了他不得不选择其中一个连贯的答案，而没有解释他为什么选择了他选择的答案。

然而，我认为 C 语言的影响至关重要。大多数脚本语言最初都是用 C 实现的，并从 C 中借鉴了它们的运算符库。C89 中实现定义的 % 操作显然是有缺陷的，不能用于像 Tcl 或 Python 这样“友好”的语言。C 调用这个操作符是 "mod"。所以他们选择了模数，而不是余数。

---

尽管问题中说了许多人使用这个作为论据，但实际上 C 并不具备与 Python 和其它类似的行为。C99 要求对除法进行截断，而不是向下取整。C89 两者都允许使用，并且也允许使用 mod 的任一版本，因此不能保证除法性质，并且无法编写可移植的有符号整数除法代码。这是错误的。

- abarnert

---

一些Lisp方言：Common Lisp定义了mod和rem，请参见http://www.lispworks.com/documentation/HyperSpec/Body/f_mod_r.htm和http://www.lispworks.com/documentation/HyperSpec/Body/f_floorc.htm。 - coredump

@coredump 和其他一些 Lisp 方言使用其他名称。MacLisp 只提供了一个，而 Racket 今天也是如此。Scheme 提供了三个（modulo、remainder 和 Wirth 风格的 mod）。我认为答案不需要链接到世界上每种语言的每种方言；说“一些 Lisp 方言”使用 mod/rem 风格的命名似乎已经足够了。 - abarnert

Answer 5

如 Paula 所说，这是因为余数。

该算法基于欧几里得除法。

在 Ruby 中，您可以编写以下代码来重建具有一致性的被除数：

puts (10/3)*3 + 10%3
#=> 10

在现实生活中，它的工作方式相同。 10个苹果和3个人。好吧，你可以把一个苹果切成三份，但超出了设定的整数。

对于负数，一致性也得以保持：

puts (-10/3)*3 + -10%3 #=> -10
puts (10/(-3))*(-3) + 10%(-3) #=> 10
puts (-10/(-3))*(-3) + -10%(-3) #=> -10

商总是向下取整（沿负轴向下），余数如下所示：

puts (-10/3) #=> -4
puts -10%3 #=> 2

puts (10/(-3)) #=> -4
puts 10%(-3) # => -2

puts (-10/(-3)) #=> 3
puts -10%(-3) #=> -1 

- iGian

---

因此，除法和取模运算必须是一致的，这很清楚。但是，只要这些相等性成立，您可以选择四舍五入或向下取整，并仍然使其保持一致。 - jjmerelo

@jjmerelo，我同意你的观点，从数学上讲，你可以选择不同的规则，其中 # 10 / 3 = 4 # 10 % 3 = -2 # 3 * 4 - 2 = 10。但是，在自然数集合中，这种方法行不通，因为 -2 不存在。 - iGian

@iGian，你的答案缺少的是，在不改变正数结果的情况下，保持负数一致性的方式不止一种。 - Alexey Romanov

Answer 6

这个答案回答了其他（优秀）答案没有明确回答的问题的一个子部分。您指出：

“如果您选择四舍五入，您也可以有一致性。”

其他答案讨论了向下取整（向-∞）和截断（向0舍入）之间的选择，但没有比较向上取整（向∞舍入）。

（已接受的答案涉及在二进制补码机器上优先选择向下舍入的性能原因，这也适用于与向上舍入进行比较。但是，避免向上舍入的更重要的语义原因。）

这个答案直接回答了为什么向上舍入不是一个好的解决方案。

向上舍入破坏了小学的期望

在以前答案的例子基础上，通常会非正式地说：

“如果我把十四个弹珠平均分给三个人，每个人得到四个弹珠，剩下两个弹珠。”

实际上，这就是许多学生在被介绍到分数/小数之前首先学习除法的方式。一个学生可能会写成 14 ÷ 3 = 4 remainder 2。由于这个概念被引入得如此早，我们真的希望我们的 div 运算符能够保持这个特性。

或者更正式地说，在 最受欢迎的答案 中讨论的三个特性中，第一个特性 ((a div b) × b + (a mod b) = a) 是最重要的。

但是向上取整破坏了这个特性。如果 div 向上取整，则 14 div 3 返回 5。这意味着上面的等式简化为 15 + (13 mod 4) = 13 - 而对于 任何 定义的 mod 都不成立。同样，较不正式/小学的方法也不行 - 或者至少需要引入负弹珠：“每个人得到 5 个弹珠，还剩下负一颗弹珠”。

“四舍五入到最近的整数也会破坏这个属性，就像上面的例子一样，这意味着向上取整。因此，如果我们想保持基本的期望，我们不能向上取整。而且，既然不能向上取整，你在问题中提供的连贯性论证已足以证明向下取整的合理性。”

- codesections