29. Divide Two Integers

Question

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return *the quotient after dividing dividend by *divisor.

**Note: **Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2<sup>31</sup>, 2<sup>31</sup><span> </span>− 1]. For this problem, if the quotient is strictly greater than 2<sup>31</sup><span> </span>- 1, then return 2<sup>31</sup><span> </span>- 1, and if the quotient is strictly less than -2<sup>31</sup>, then return -2<sup>31</sup>.

Solution

解题思路类似于快速幂。

使用快速乘法来快速的获得商。

计算过程相当于：
60/8 = (60-32)/8 + 4 = (60-32-16)/8 + 2 + 4 = 1 + 2 + 4 = 7

需要注意的是由于只使用了整数（int）而不是长整数（long）储存数据，因此计算时需要处理各种溢出问题。

整数溢出

由于采用32位整数记录数字，负数要比正数的值范围大1。
因此当divisor为负数时，如果负数为整数最小值，则需要返回对应的整数最大值。

同时，为了在计算时防止整数溢出，因此将被除数与除数统一转为负数计算。（负数的数值比整数范围大）
当向下递归时，要保持dividend和divisor的正负性不变。

快速乘

只要被除数大于除数，则商至少为1。
循环，当被除数大于两倍的除数时，则商的结果可以直接翻倍。

否则将被除数减去当前的除数，然后向下递归新的被除数和除数。
最后返回快速乘中计算出的商加上向下递归返回的结果。

Code

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        if(divisor == 1) return dividend;
        if(divisor == -1) return dividend == Integer.MIN_VALUE ? Integer.MAX_VALUE : -dividend; //当dividend为最小整数时，其负数溢出，此时返回Integer.MAX_VALUE
        int a = dividend, b = divisor;
        int sign = a > 0 && b > 0 || a < 0 && b < 0 ? 1 : -1;   //记录除数与被除数是否同号
        if(dividend > 0) a = -a;    //将除数与被除数转换为负数，因为负数能记录的数值比正数大1，防止溢出
        if(divisor > 0) b = -b;
        if(a > b) return 0; //被除数小于除数时返回0
        int res = 1;
        while(a <= b+b && b+b < 0){ //算法核心，快速乘法
            b += b; //除数每次翻倍，直到大于被除数
            res += res; //商的结果翻倍
        }
        res = sign == 1 ? res : -res;   //根据是否同号记录商
        
        divisor = dividend > 0 ? -divisor : divisor;  //当原有被除数是正数时，要将除数取反
        return res + divide(a-b, divisor);
    }
}