取余, 真的那么简单么?

取余的概述
取余 是一个比较常见的运算，在各种编程语言中均有相应的运算符（Java/C的%, Pascal/Delphi的mod等等），我们使用的也比较多，比如

5 % 3 = 2,   
10 % 2 = 0. 
问题的产生
这样一个问题： -3 % 2 = ? 我们可以使用这样一段Java程序来验证：
                 System.out.println("result:" + (-3)%2); 

运行，结果是： result:-1

不过问题就在这：记得按照以前的数学书中的叙述，似乎不是这样的，于是将书翻了出来，在 Concrete Mathematics 的82页，看到：

也就是说，x mod y等于 x 减去 y 乘上 x与y的商的下界。于是，上面的-3 mod 2就变成了 

奇怪的事情发生了。这个结果与上面程序计算得出的结果不一致。同样，我们使用Mathematics画出图像，来考察-5~5对2取余的情况：

 

在该图中，同样可以看出，-3对2取余的结果是1，而不是程序计算出来的-1。为何会有这样的结果呢？

程序计算结果原因分析
使用以下一段Delphi程序来考察：

var   
   i,j,k:Integer;   
begin   
   i:=-3;   
   j:=2;   
   k:=i mod j;   
   ShowMessage(IntToStr(k));   
end;  
编译后，查看汇编，关键的计算部分如下：

Unit1.pas.30: i:=-3;   
00486D84 B9FDFFFFFF       mov ecx,$fffffffd   
Unit1.pas.31: j:=2;   
00486D89 BB02000000       mov ebx,$00000002  
Unit1.pas.32: k:=i mod j;   
00486D8E 8BC1             mov eax,ecx   
00486D90 99               cdq    
00486D91 F7FB             idiv ebx   
00486D93 8BDA             mov ebx,edx 
 

 

在上面的代码中，首先将-3赋值给eax(ecx为临时中间变量)，然后将2赋值给ebx，之后执行一条idiv指令。执行该指令后，商在eax中，余数在edx中。这样，与书上结论不一样的原因就出来了：按照书上的定义，应该首先做除法，得到浮点数，然后取其下界。如果附点数是正的，其下界相当与取整；如果浮点数是负的，相当于将小数部分抹去再减一，而idiv指令根本没有计算浮点并取下界的过程，所以造成与数学中的mod定义不一致。实际上，严格的说，我们在程序中使用的余数，其定义为：

                x - y(x div y)

这就是二者的区别。这个区别，对于正数，二者计算出的结果是相等的，但是负数就不相等了。这就意味着，如果以后在使用数学中余数相关定理的时候，要注意计算机中余数的计算和数学定义不是完全一致的，所以在计算机上，对于负数，数学定理并不完全适用。当然，对于正数，二者是没有区别的。至于为什么计算机上要这么实现，我想恐怕还是历史原因，最早的计算机如果这样计算除法（取余是靠除法来完成的），那么就涉及到浮点数的计算以及取下界，这样，将比较大的降低效率，所以实现成了这样的方式，一直沿用至今。

 

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/liuxiaolei7676/archive/2010/04/06/5453228.aspx