Chinaunix首页 | 论坛 | 博客
  • 博客访问: 365700
  • 博文数量: 53
  • 博客积分: 139
  • 博客等级: 入伍新兵
  • 技术积分: 589
  • 用 户 组: 普通用户
  • 注册时间: 2012-12-27 01:55
个人简介

学习linux,学习编程。

文章分类

全部博文(53)

文章存档

2019年(1)

2018年(4)

2016年(4)

2014年(11)

2013年(33)

分类: C/C++

2013-09-08 00:16:59

在CU论坛上 mathieu  提出如下一个问题:
面试题,实现一个变量除以15,不使用/除法运算符和库函数
在网上搜到下面的思路:
我们不妨将A转化一下,加上一定的数字a,使得
(A + a) / 15 = A / 16 ,(A >>4)
求得 a = A >> 16 + 1
最后实现代码:quotient=(i + (i >> 4) + 1 ) >> 4;
我琢磨了半天也没看懂这个思路是什么意思,
以及为什么能得出后面的实现代码。有人能帮忙解释下吗?
其中 (A >>4) 的意思是指将2进制数A向右移4位。

我给出了如下解释。
(A + a) / 15 = A / 16 ,(A >>4)                          (1)
由(1)=>         a= -(A/16)。                             (2)      
由(1)=>         A/15=A/16-a/15。                     (3)
将(2)代入(3)=>  A/15=A/16 + (A/16)/15。    (4)
 等式(4)是一个递归的表达试,对应一个递归的程序。
等式(4)里有 A/15 和 (A/16)/15,它们的分母都是15。
进一步处理,用(4)代入(4) ,得到:
A/15=A/16 + (A/16)/16 + (A/16/16)/15。           (5)
继续迭代,得到的结果是:
A/15 = A>>4 + A>>8 + A>>12 +A>>16 + ......         (6)

阅读(1495) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~