Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
Solution：
思路： 被除数39，除数5：主要目的是要找到39最多可以减多少(result)个5，而找result的过程利用累积二倍尝试(二分查找思想)。先试5(times=1倍): 39 - 5 = 34还 > 0，可以继续减，再试10(times=2倍): 39 - 10 = 29 > 0，还可以继续，再试20(times=4倍)，再试40，39 - 40 < 0，40不行，则4倍的5是可以的。再找剩下的39 - 4 * 5 = 19持续此过程直到 剩下的 < 5，将这些倍数times加到一起就是result * 5 <并最接近39.
Time Complexity: The best case: O(log(n)) (example: 256, 2); The worst case: O(log(n)^2) (example: 255 / 2 , 7 + 6 + 5 + 4 + 3 + 2 + 1) (n = dvd / dvs)
Space Complexity: O(1)
Solution Code：
class Solution {
public int divide(int dividend, int divisor) {
if(divisor==0 || (dividend == Integer.MIN_VALUE && divisor == -1)) return Integer.MAX_VALUE;
long dvd = Math.abs((long)dividend);
long dvs = Math.abs((long)divisor);
int res = 0;
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
while(dvd >= dvs) {
long tmp_dvs = dvs, times = 1;
while(dvd >= (tmp_dvs <<1 )){
tmp_dvs <<= 1;
times <<= 1;
}
dvd -= tmp_dvs;
res += times;
}
return sign == 1 ? res : -res;
}
}
