LintCode链接
将两个整数相除，要求不使用乘法、除法和 mod 运算符。
如果溢出，返回 2147483647 。
您在真实的面试中是否遇到过这个题？ Yes 样例给定被除数 = 100 ，除数 = 9，返回 11。
标签 二分法 public class Solution { /* * @param dividend: the dividend * @param divisor: the divisor * @return: the result */ public int divide(int dividend, int divisor) { return helper_2(dividend,divisor); } //方法一 //二分法 //移位+减法 int helper_2(int dividend, int divisor){ int flag = (dividend<0)^(divisor<0)?-1:1; long a = Math.abs((long)dividend); long b = Math.abs((long)divisor); long res=0; while(a>=b){ //先尽量的从小减到大 //2倍，2倍的增长 long tmp=b; long cnt=1; while(a>=tmp){ a-=tmp;//先减去一次b res+=cnt;//结果加上cnt倍的b //b增长2倍，相应的a要减去的b的次数也会增长2倍 cnt = cnt<<1; tmp = tmp<<1; }//一直到减不够了，重新从b的一倍开始减起 } //溢出处理 if(res == (Integer.MAX_VALUE+1l) && flag==1) return Integer.MAX_VALUE; return (int)(res*flag); } //方法二 //一直做减法 //超时 int helper_1(int dividend, int divisor){ int flag = (dividend<0)^(divisor<0)?-1:1; long a = Math.abs((long)dividend); long b = Math.abs((long)divisor); long res=0; while(a>=b){ res++; a-=b; } //溢出处理 if(res == (Integer.MAX_VALUE+1l) && flag==1) return Integer.MAX_VALUE; return (int)res*flag; } }