逍遥游

负数取模、负数除法的问题

问题

最开始碰到负数取模、负数除法这个问题是在大一,当时需要对一个数除以2,开始都是正数,没碰到什么问题,后来又加入了负数。想着3/2=1、2/2=1、1/2=0、0/2=0,两个一组,于是理所当然的想着-1/2=-1,但是结果却是0。当时忙着完成程序设计,也没去深究,只是想着应该就是这样。

今天突然在想一个排序算法的时候,又遇到了这个问题。我发现负数取模竟然可以等于负数!比如-1%10=-1,并不是我想要的9。感觉这里有文章,于是上网搜了一下,发现果然是值得注意的一个问题。

经过(别人)测试,在不同的语言中,对负数执行取模运算,结果有可能会是不同的。例如,(-11)%5在python中计算的结果是4,而在C(C99)中计算的结果则是-1。(我并没有进行验证,因为暂时还不会python,也没有环境。)

分析

以下是可能的原理:

truncate除法 && floor除法

在大多数编程语言中,如果整数a不是整 数b的整数倍数的话,那么a、b做除法产生的实际结果的小数部分将会被截除,这个过程称为截尾(truncation)。如果除法的结果是正数的话,那么 一般的编程语言都会把结果趋零截尾,也就是说,直接把商的小数部分去除。但是如果除法的结果是负数的话,不同的语言通常采用了两种不同的截尾方法:一种是 趋零截尾(truncate toward zero),另一种是趋负无穷截尾(truncate toward negative infinity);相应的,两种除法分别被称为truncate除法和floor除法。
事实上,可以认为不管除法的结果是正是负,truncate除法都是趋零结尾;而floor除法都是趋负无穷结尾。

取模运算

取模运算实际上是计算两数相除以后的余数。假设q是a、b相除产生的商 (quotient),r是相应的余数(remainder),那么在几乎所有的计算系统中,都满足a=b*q+r,其中|r| < |a|。因此r有 两个选择,一个为正,一个为负;相应的,q也有两个选择。如果a、b都是正数的话,那么一般的编程语言中,r为正数;或者如果a、b都是负数的话,一般r 为负数。但是如果a、b一正一负的话,不同的语言则会根据除法的不同结果而使得r的结果也不同,并且一般r的计算方法都会满足r=a-(a/b)*b。
(1)C/Java语言
C/Java语言除法采用的是趋零截尾(事实上,C89 对于除数或被除数之一为负数情况的结果是未定义的;C99才正式确定了趋零截尾),即truncate除法。它们的取模运算符是%,并且此运算符只接受整 型操作数。一个规律是,取模运算的结果的符号与第一个操作数的符号相同(或为0)。因此(-11)%5=-11-[(-11)/5]*5=-11-(-2)*5=-1。

(2)C++语言
C++语言的截尾方式取决于特定的机器。如果两个操作数均为正,那么取模运算的结果也为正数(或为0);如果两个操作数均为负数,那么取模运算的结果为负数(或为0);如果只有一个操作数为负数,那么取模运算的结果是取决于特定实现的。

(3)Python语言
Python语言除法采用的是趋负无穷截尾,即floor除法。它的取模运算符也是%,并且此运算符可以接受浮点操作数。一个类似的规律是,取模运算的结果的符号与第二个操作数的符号相同。因此(-11)%5=-11-[(-11)/5]5=-11-(-3)\5=4。
这里需要注意的是,Python 3.x中”/“运算符的意义发生了变化,”/“产生的结果将不会再进行截尾;相应的”//“运算符的结果才会进行截尾。

(4)Common Lisp
Common Lisp的特殊操作符(special operator)”/“的结果是分数,因此不会存在截尾的问题。但是Common Lisp提供了TRUNCATE函数和FLOOR函数分别对应上述的两种除法。相应的,Common Lisp的REM函数类似于C/Java语言中的取模运算;而MOD函数类似于Python语言中的取模运算。

我的总结

首先,我觉得任何一种严谨的语言都应该满足 a/b + a%b = a 这个表达式,这应该能解释为什么不同语言中出现不同规范。毕竟 -1/10=0、-1%10=9 这两个更容易被人接受的结果是不能相容的(或者说是不满足上面那个式子的)。想要使前一个成立就必须更改后一个式子的结果,反之亦然。二者不可兼得,否则就会出现a/b + a%b != a 这个数学上的错误结论。

接下来就是在编程过程中怎么去处理了。一种方式是在用之前先去搞清楚你所用的语言支持那一种规范。另一种我觉得更好一点,就是将负数转换为整数,避免这种潜在的不确定性。如果这样做更麻烦那就只能采取第一种方法啦。

部分内容来自:负数的取模运算

附表:编程语言中不同的方式

语言 -1/10 -1%10
C/C++ 0 -1
Java

显然Newnius并不能学会所有语言,也就不能知道所有语言中负数取模的结果了。如果你看到了,不妨试试你用的语言中-1/10的结果,顺便留个言,我会及时更新附录的。


多说停止服务,disqus引导注册太过分,暂时不上评论系统了。有机会自己造轮子吧。邮箱:input@newnius.com