给定A, B两个整数,不使用除法和取模运算,求A/B的商和余数。
1. 最基本的算法是,从小到大遍历:
for (i = 2 to A -1)
if (i * B > A)
商 = i -1; 余数 = A – (i-1)*B;
2. 较好的算法是采用2分法,查找[2, A]中满足尚的解。
3. 更好的算法是采用位操作的思想来实现除法。
以除数为初始测试值,以2的指数为步长来搜索问题空间,当被除数与测试值的差小于除数时便结束搜索,若在这之前测试值大于被除数,则将被除数减去前一个测试值,并重复上述过程直到搜索结束。举个例子,求1200/3:
顺序搜索时,我们要与1200比较的数有:3,6,9,12,15,...,1998,2001,比较次数667次
以2的指数为步长搜索时,与1200比较3,6,12,24,48,96,192,384,768,1536,然后与1200-768=432再进行比较3,6,12,24,48,96,192,384,768,再取432-384=48比较3,6,12,24,48,搜索结束,比较次数共24次,比顺序搜索有很大的提高。你可能会问,为什么要以2的指数为步长来搜索呢?答案是,这样我们就可以使用位操作来进一步提高计算效率了。下面是这个算法的实现:
intinteger_div_1(unsigned int dividend, unsigned int divisor)
{
if(divisor == 0)
{
cout
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?