Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
https://leetcode.com/problems/divide-two-integers/
需要注意的点：
- 除数为零的情况
- 被除数为Integer.MIN_VALUE，除数为-1时会超出Integer的表示范围，可以把被除数和除数都转换成long
- 被除数和除数的符号问题：先计算结果的符号（如果被除数和除数异号，那么结果为负），然后把被除数和除数取绝对值
- 被除数减除数的过程可以通过除数左移来加速
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public int divide(int dividend, int divisor) {
if(divisor == 0) return Integer.MAX_VALUE;
long a = dividend, b = divisor;
boolean positive = true;
if(a < 0 && b > 0 || a > 0 && b < 0) positive = false;
a = Math.abs(a);
b = Math.abs(b);
long res = 0;
while(a >= b) {
long bt = b, rt = 1;
while((bt << 1) <= a) {
bt = bt << 1;
rt = rt << 1;
}
a -= bt;
res += rt;
}
if(positive && res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
return positive ? (int)res : -(int)res;
}
|