# Problem 29: Divide Two Integers

> <https://leetcode.com/problems/divide-two-integers/>

## 思路

* 这道题可以看做是二分法的应用，每次用除数来翻倍（这里用 shift），然后和被除数比较
* 当除数翻倍到比被除数大了以后，我们就后退一位
* 这道题的 corner cases 要注意

## 复杂度

* 因为每次 while loop 都是对半分，消耗 `log(n)` 的时间，所以总的时间复杂度是 `(logn)^2`

```java
public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }
        if (divisor == 0) {
            return dividend >= 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        boolean isNegative = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        int rst = 0;
        while (a >= b) {
            int shift = 0;
            while (a >= (b << shift)) shift++;
            a -= b << (shift - 1);
            rst += 1 << (shift - 1);
        }

        return isNegative ? -rst : rst;
    }
}
```

## 易错点

1. corner cases &#x20;

   (1) 被除数为 0 &#x20;

   (2) 除数为 0 &#x20;

   这时候有可能是极大值，同时也有可能是极小值 &#x20;
2. 极大值和极小值

   ```java
   Integer.MAX_VALUE;  // 2^31 - 1; 2147483647
   Integer.MIN_VALUE;  // -2^31; -2147483648
   ```

   所以当被除数是极小值，除数是 -1 的时候会溢出
3. 数字翻倍的时候有可能溢出，转为 long 类型

   ```java
   long a = Math.abs((long) dividend);
   long b = Math.abs((long) divisor);
   ```
