class Solution { public: int divide(int a,int b) { if (a == INT_MIN && b == -1) return INT_MAX; if(a!=INT_MIN && b== INT_MIN) //除数是INT_MIN特殊判定 return 0; if(a==b) return 1; int sign = 0; if ((a > 0 && b < 0) || (a < 0 && b > 0)) sign = 1; if (b == 1) return a; if(b==-1) return -a; if(a==-b) return -1; if (a > 0) a = -a; if (b > 0) b = -b; int base = 1, cp = b,ans=0; while (a <= b) { cp=b; //存一下当前循环的除数 base = 1; while(cp>=0xc0000000&&a<=cp+cp) { base+=base; cp+=cp; } ans+=base; a-=cp; } if(sign) ans=-ans; return ans; } };
主要思想首先对可能超时或者溢出的结果进行特殊判定。
对需要进行计算的值,找到最接近被除数a的2^k值,a>cp+cp时则找到了这个值,否则cp和商扩倍;
当找到了这个商后,则加到结果中,被除数减去这个商,继续重复这个循环,直到被除数大于除数,返回结果。
这是一种优化算法,效率接近logn,前面带一常数但不是n