您当前的位置: 首页 > 

壹小俊

暂无认证

  • 3浏览

    0关注

    885博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

给定A, B两个整数,不使用除法和取模运算,求A/B的商和余数

壹小俊 发布时间:2020-03-17 16:31:26 ,浏览量:3

给定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            
关注
打赏
1664335782
查看更多评论
0.0647s