Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
Solution
Use << operator.
直观的方法是,用被除数逐个的减去除数,直到被除数小于0。这样做会超时。
那么如果每次不仅仅减去1个除数,计算速度就会增加,但是题目不能使用乘法,因此不能减去k*除数
,我们可以对除数进行左移位操作,这样每次相当于减去2k个除数,如何确定k呢,只要使 (2^k)*除数 <= 当前被除数 <(2^(k+1))*除数
.
Complexity
时间复杂度 O(logn),空间复杂度 O(1)
Code
public class Solution {
public int divide(int dividend, int divisor) {
boolean flag = dividend < 0 ^ divisor < 0;
long Dividend = Math.abs((long)dividend);
long Divisor = Math.abs((long)divisor);
long res = 0;
while (Dividend >= Divisor) {
long c = Divisor;
for (int i = 0; (c << i) <= Dividend; ++i) {
Dividend -= (c << i);
res += (1 << i);
}
}
if (flag == true) res = -res;
if (res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
return (int)res;
}
}