描述

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

思路

这里我一开始的思路是通过减法来实现，不过实现了，超时了。实在想不到什么方法了，参考了一下讨论区，找到大神的思路。使用<<，>> 操作来运算。我在原来的代码基础上，将符号位的判断修改了一下，时间少了。

代码

class Solution { public: int divide(int dividend, int divisor) { if (!divisor || (dividend == INT_MIN && divisor == -1)) return INT_MAX; int sign =(dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0) ? 1 : -1; long long dvd = labs(dividend); long long dvs = labs(divisor); int res = 0; while (dvd >= dvs) { long long temp = dvs, multiple = 1; while (dvd >= (temp << 1)) { temp <<= 1; multiple <<= 1; } dvd -= temp; res += multiple; } return sign == 1 ? res : -res; } };

结果

他山之玉

C++ O(n) solutioin

int divide(int dividend, int divisor) { if(!divisor || (dividend == INT_MIN && divisor == -1)) return INT_MAX; int minus = ((dividend ^ divisor) >> 31) ? -1 : 1; pair<long, long> r = mdiv(labs(dividend), labs(divisor)); return r.first * minus; } pair<long, long> mdiv(long de, long di) { if(de < di) return make_pair(0, de); pair<long, long> sub = mdiv(de >> 1, di); long f, s; f = (sub.first) << 1; s = (sub.second << 1) + (de & 1); if(s >= di) { s -= di; f += 1; } return make_pair(f, s); }

Java O(n) solution

public class Solution { public int divide(int dividend, int divisor) { int sign=(dividend>0&&divisor>0)||(dividend<0&&divisor<0)?1:-1; long divd=Math.abs((long)dividend),divi=Math.abs((long)divisor); long res=0,lo=1,hi=divd; while(lo<=hi){ long mid=lo+(hi-lo)/2; if(mid*divi<=divd){ res=mid; lo=mid+1; }else{ hi=mid-1; } } return res*sign==2147483648L?Integer.MAX_VALUE:(int)res*sign; } }

python O(n) solution

class Solution: # @return an integer def divide(self, dividend, divisor): positive = (dividend < 0) is (divisor < 0) dividend, divisor = abs(dividend), abs(divisor) res = 0 while dividend >= divisor: temp, i = divisor, 1 while dividend >= temp: dividend -= temp res += i i <<= 1 temp <<= 1 if not positive: res = -res return min(max(-2147483648, res), 2147483647)