用+,-,移位实现除法运算

本文转自：http://blog.csdn.net/imcdragon/article/details/6850530

如何利用+,-,移位来实现除法.假设求 dividend / divisor

方法一:

首先想到的是用减法来实现.

算法思想:

对dividend 循环减 divisor, 减一次res++, 直到刚好减为0或余数小于divisor.

int integer_div_1(unsigned int dividend, unsigned int divisor)
{
if (divisor == 0)
{
cout << "除数不能为0" << endl;
exit(1);
}
int res = 0;
while ((dividend -= divisor) >= 0)
++res;
return res;
}

这个算法每次都以一倍的divisor进行叠加,算法效率并不高,可以改进.

以100/3为例.

算法分别比较97, 94, 91, ..., 4,1, -2,最后dividend = -2退出while循环.算法比较了34次.

如果采用每次采用将比较数翻倍的比较方法. 算法会得到优化. 举例如下: k初始化为0,  res = 0;

首先用3与100比,小于. 然后翻倍6, 小于. 12, 24, 48, 96, 192, 因为192 > 100.  退回到 96. 这里共比较了 5次. 每比较一次 k++, res += 1<<k.

100 - 96 = 4 > 除数3. 再用4重做上一步. 先跟3比较, 然后6, 6 > 4. 这次比较2次.

回到3. 4 - 3 = 1 < 除数3. 算法停止. 总共比较了5 + 2 + 1 = 8次, 比原来的34次快了很多.

代码实现如下:

//递归代码
int integer_div_2(unsigned int dividend, unsigned int divisor)
{
if (divisor == 0)
{
cout << "除数不能为0" << endl;
exit(1);
}
if (dividend < divisor) return 0;
unsigned int k = 0, c = divisor, res = 0;
for ( ; dividend >= c; c <<= 1, k++)
if (dividend - c < divisor)
return 1<<k;
return integer_div_2(dividend - (c>>1), divisor) + (1<<(k - 1));
}

//非递归算法
int integer_div_3(unsigned int dividend, unsigned int divisor)
{
if(divisor == 0)
{
cout << "除数不能为0" << endl;
exit(1);
}
if (dividend < divisor)
return 0;
unsigned int k, c, res=0;
while (dividend > divisor)
{
for (k = 0,c = divisor; dividend >= c; c <<= 1, k++)
{
if (dividend - c < divisor)
{
res += 1<<k;
break;
}
}
if (dividend - c < divisor)
break;
res += 1<<(k - 1);
dividend -= c>>1;
}
return res;
}

方法二:

另一种方法是使用魔数进行运算.

如果你看过编译器生成代码优化或一些大型系统的源码，或者嵌入式代码优化等等性能要求非常高的代码，你就会发现一些称之为magic number的数.

如0xAAAAAAAB、0x66666667、0x24924925、0x51EB851F、0x10624DD3......这些分别是快速除法（3，5，7。。。）的魔幻数字
编译器一般用这个来优化除法，至于怎么得来的自己google吧.

例如求一个数除以3的值可以这样求:

int divby3(int x)
{
return ((__int64)x*0xAAAAAAABUL) >> 33 ;
}

这里推荐一本书,里面有讲关于魔数的算法. <<Hacker's Delight>> By Henry S. Warren, Publisher : Addison Wesley 

最后

以上就是外向唇膏为你收集整理的用+,-,移位实现除法运算的全部内容，希望文章能够帮你解决用+,-,移位实现除法运算所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。