问题描述
https://leetcode.com/problems/divide-two-integers/
解决思路
这道题不可以用除法，不可以用取模运算。举例35和3，思路如下：
3«0,3
3«1,6
3«2,12
3«3,24
3«4,48.
此时48>35,所以只能左移3次到24,38等于24，留下8.此时35-24=11
3«0,3
3«1,6
3«2,12
此时12>11,所以只能左移1次到6,32等于6，留下2,加上上一次的8，得到10.此时11-6=5
3«0,3
3«1,6
此时6>5,所以只能左移0次到3,3*1等于3，留下1，加上上一次的10，得到11.此时5-3=2
3«0,3
此时3>2，跳出循环，取上一次11作为结果。
代码
class Solution {
public int divide(int dividend, int divisor) {
//corner case
if(divisor == 0) return Integer.MAX_VALUE;
if(dividend == Integer.MIN_VALUE){
//in this condition, the result will be overflow since 2^31 -1 is the max value of positive number, and the min value of negative number is -2^32. Then -2^32 / -1 will be out of the range.
if(divisor == -1) return Integer.MAX_VALUE;
else if(divisor == 1) return Integer.MIN_VALUE;
}
//to avoid overflow
long divd = (long)dividend;
long divs = (long)divisor;
//convert dividend and divisor to positive numbers to process together
int sign = 1;
if(divd < 0){
divd = -divd;
sign = -sign;
}
if(divs < 0){
divs = - divs;
sign = -sign;
}
//to calculate the res
int res = 0;
while(divd >= divs){
int shift = 0;
while(divd >= (divs << shift)){
shift++;
}
//res represent how many divs contains in divd (the reslut of divd / divs). Also it need to be added with former res after every loop
//shift need to minus 1 since it was added one more time
res += 1 << (shift - 1);
//this represents divd - (divd / divs)
divd -= divs<< (shift - 1);
}
return sign * res;
}
}
复杂度分析
时间复杂度：O(n^2)
空间复杂度：O(1)
