首页 > 代码库 > 【转】C/C++除法实现方式及负数取模详解
【转】C/C++除法实现方式及负数取模详解
原帖:http://blog.csdn.net/sonydvd123/article/details/8245057
一、下面的题目你能全做对吗?
1.7/4=?
2.7/(-4)=?
3.7%4=?
4.7%(-4)=?
5.(-7)/4=?
6.(-7)%4=?
7.(-7)/(unsigned)4=?
答案:
1
-1
3
3
-1
-3
1073741822
如过你全部答对,你可以无视后面的内容……
二、除法的取整分类
除法的取整分为三类:向上取整、向下取整、向零取整。
1.向上取整:向+∞方向取最接近精确值的整数。在这种取整方式下,7/4=2,7/(-4)=-1,6/3=2,6/(-3)=-2
2.向下取整:向-∞方向取最接近精确值的整数。在这种取整方式下,7/4=1,7/(-4)=-2,6/3=2,6/(-3)=-2
3.向零取整:向0方向取最接近精确值的整数,换言之就是舍去小数部分,因此又称截断取整。在这种取整方式下,7/4=1,7/(-4)=-1,6/3=2,6/(-3)=-2
通过观察可以发现,无论是向上取整还是向下取整,(-a)/b==-(a/b)都不一定成立。这给程序设计者带来了极大的麻烦。而对于向零取整,(-a)/b==-(a/b)是成立的,以此,C/C++采用这种取整方式。
三、负数取模
回想小学的公式:被除数÷除数=商……余数。
由此可知,余数=被除数-商×除数 (*)
对C/C++而言,(*)式依然成立。并且,该式是解决负数取模问题的关键。
例一:7%(-4)=?
解:由C/C++向零取整的整除方式可知,7/(-4)=-1;由(*)式知,余数=7-(-4)*(-1)=3.所以,7%(-4)=3
例二:(-7)%4=?
解:由C/C++向零取整的整除方式可知,(-7)/4=-1;由(*)式知,余数=(-7)-4*(-1)=-3.所以,(-7)%4=-3
例三:(-7)%(-4)=?
解:由C/C++向零取整的整除方式可知,(-7)/(-4)=1;由(*)式知,余数=(-7)-(-4)*1=-3.所以,(-7)%(-4)=-3
四、相关知识的拓展
1.对于有符号整数与无符号整数间的除法,C/C++会将有符号整数转换为无符号整数,需要特别注意的是,符号位并没有丢失,而是变成了数据位参与运算。这就是(-7)/(unsigned)4不等于-1,而等于1073741822的原因。
2.编译器对除法的优化
①在“无优化”条件下,编译器会在不影响正常调试的前提下,对除法进行简单的优化。
A.“常量/常量”型除法:编译器会直接计算出结果。
B.“变量/变量”型除法:无优化。
C.“变量/常量”型除法:若常量≠2^n,无优化;否则,除法将被转换为右移运算。由于由右移运算实现的整除实质上是向下取整,所以编译器会通过一些附加的指令在不产生分支结构的情况下将向下取整转换为向零取整。
以【变量/2^3】为例,反汇编代码如下:
mov eax,被除数
cdq ;若eax<0,则edx=0xFFFFFFFF;否则edx=0
and edx,7 ;若eax<0,则edx=7;否则edx=0
add eax,edx ;若eax<0,【(eax+7)/(2^3)】向下取整的值 与 【eax/(2^3)】向零取整的值相等,从而实现向零取整
sar eax,3 ;右移,完成除法
②在“O2优化”条件下,“变量/常量”型除法中,常量若≠2^n,也可以优化。此时,除法将被转换为乘法与右移的结合形式。例如,a/b=a*(1/b)=a*((2^n)/b)*(1/(2^n)),其中,((2^n)/b为MagicNumber,由编译器在编译过程中算出。这样a/b就变成了(a*MagicNumber)>>n,n的值由编译器选取。需要注意的是,本公式只是除法优化中的一个典型代表,编译器会根据除数对公式进行调整,但基本形式与原理是类似的。
转载地址:http://tieba.baidu.com/p/1881961036
——————————————————————————————————————————
以下摘录自C++ Primer(P130)
操作符%称为“求余”或“求模”操作符,该操作符的操作数只能为整型。
如果两个操作数为正,结果也为正;如果两个操作数都为负数,结果也为负数;如果一个操作数为正数,一个操作数为负数,求模结果的符号取决于机器。
当操作数中有一个为负,一个为正是,求模操作结果值的符号可依据分子(被除数)或分母(除数)的符号而定。如果求模的结果随分子的符号,则除出来的值向零一侧取整;如果求模与分母的符号匹配,则除出来的值向负无穷大一侧取整。
(VC貌似是根据左操作数来确定求模操作的符号)