在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) |