29 Divide Two Integers

1. Question

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

2. Implementation

(1) 倍增法
1
class Solution {
2
public int divide(int dividend, int divisor) {
3
long a = Math.abs((long)dividend);
4
long b = Math.abs((long)divisor);
5
long res = 0;
6
7
while (a >= b) {
8
long temp = b;
9
int i = 0;
10
11
while (a >= temp) {
12
a -= temp;
13
temp <<= 1;
14
res += 1 << i;
15
++i;
16
}
17
}
18
19
if (dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0) {
20
res = -res;
21
}
22
return res > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)res;
23
}
24
}
Copied!

3. Time & Space Complexity

倍增法:时间复杂度O(log(divisor)), 空间复杂度O(1)