题目描述：编程实现两个正整数的除法，当然不能用除法操作。
题目来自昨天上午远程面试牛客网的算法题，数据结构和算法一直是我的薄弱项，所以此次面试最后也不大理想。不得不说，面试官人还是很好的，一直在给我提示，可是终究因为自己能力不够而没过。。。
我的答案
刚开始，我写出了如下的代码，基本上是符合条件可以运行的：
/**
* Created by clearbug on 2018/2/26.
*/
public class Solution {
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.div(2, 3));
System.out.println(s.div(3, 2));
System.out.println(s.div(5, 2));
System.out.println(s.div(6, 2));
}
/**
* 两个正整数的除法
*
* @param x
* @param y
* @return
*/
public int div(int x, int y) {
if(x < y) {
return 0;
}
int res = 0;
while(x - y >= 0) {
res++;
x = x - y;
}
return res;
}
}
代码虽然可以正确运行，但是确实有效率问题的：比如说，当 x 很大 y 却很小时。
面试官说：可以利用类似二分查找的思想来提高效率
我说：二分查找求中值是需要除法的啊，但是这道题目规定不能使用除法的
面试官说：求中值不一定非得用除法，比如可以用移位操作
然后我虽然有了点思路，但并没有清楚的表达出来。现在已经面试完了，就在写下这种方法吧：
/**
* Created by clearbug on 2018/2/26.
*/
public class Solution {
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.div(2, 3));
System.out.println(s.div(3, 2));
System.out.println(s.div(5, 2));
System.out.println(s.div(6, 2));
System.out.println(s.div(13, 3));
System.out.println(s.div(26, 3));
System.out.println(s.div(26, 2));
}
/**
* 两个正整数的除法
*
* @param x
* @param y
* @return
*/
public int div(int x, int y) {
if(x < y) {
return 0;
}
int res = 0;
while (x >= y) {
int multi = 1;
while (y * multi <= x >> 1) {
multi = multi << 1;
}
res += multi;
x = x - y * multi;
}
return res;
}
}
好吧，我承认我自己并没有写出来，我是参考了这位老铁的代码写的：http://www.xuebuyuan.com/3120516.html。
现在我也没完全想明白为啥要与 x 的一半做比较，以后想明白了再说吧！