divide two integers


Solve the problem
虽然标签是二分查找,但是用到了一些位操作的技巧。

  1. 判断结果的符号。在第6行中,用到了异或操作,即两个条件中有且仅有一个条件为真,才为真。
  2. 左移操作。左移即乘以2。

e.g. dividend = 100, divisor = 3
(1) temp = 96, num = 32, end = 4, ans = 32
(2) temp = 3, num = 1, end = 1, ans = 33

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int (int dividend, int divisor) {
if (divisor == 1)
return dividend;
if (dividend == Integer.MIN_VALUE && divisor == -1)
return Integer.MAX_VALUE;
int sign = (dividend > 0 ^ divisor > 0) ? -1 : 1;
long ans = 0;
long begin = Math.abs((long)divisor);
long end = Math.abs((long)dividend);
while (begin <= end) {
long temp = begin;
long num = 1;
while ((temp << 1) < end) {
temp <<= 1;
num <<= 1;
}
ans += num;
end -= temp;
}
return (int)(sign * ans);
}