学步园

题目描述：编程实现两个正整数的除法，当然不能用除法操作符。
// return x/y.
int div(const int x, const int y)
{
          ....
}

别小看这道题目啊，这个是MS的面试题目啊。刚拿到这道题目的时候。我想过用二分法来求，但二分也还不是要用到除法么。后来想到了一种方法，这种方法我觉得还是可行的，就是把正数转换为字符串，模拟小学学过的竖式除法运算。这样就很快能出结果了，但有一点不好的是，这个模拟起来有点困难。后来XT在网上说这个是用位移运算的方法做的。呵呵，是的呀，于是，我就写了一个位移运算的代码。当然这个代码用二分还可以优化，但我觉得不必要了，就算是 INT_MAX ÷ 1都能很快的出结果了。所以我就没有优化了。当然，这个题目还可以稍微转换一下描述，比如，不使用 "%" && "/" 求 a % b。

#include<stdio.h></p> <p>int div(const int x, const int y)<br /> {<br /> int dividend = x, multi, result = 0;<br /> while(dividend >= y)<br /> {<br /> multi = 1;<br /> while( multi * y <= (dividend >> 1) )<br /> {<br /> multi <<= 1;<br /> }<br /> result += multi;<br /> dividend -= multi * y;<br /> }<br /> return result;<br /> }</p> <p>int main()<br /> {<br /> int x, y;<br /> while( scanf("%d %d", &x, &y) != EOF )<br /> {<br /> printf("%d÷%d=%d/n", x, y, div(x, y));<br /> }<br /> return 0;<br /> }