leetcode29.Divide Two Integers

题目要求

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

在不使用乘法，除法和求余操作的情况下，计算两个整数相除的结果。如果溢出了，则返回最大值。

在这里核心思路是使用逆向二分法和递归的思路来进行计算。其中一个难点在于如何处理溢出的情况。在这里我们使用取值范围更广的long来处理数值溢出的场景。其次我们将所有的正负值运算从递归中提取出来，直接判断结果的正负情况并直接在返回最后结果时添上正负值

解题代码

public int divide(int dividend, int divisor) {
    //判断最终结果的正负性
    boolean isPositive = true;
    if((dividend<0&&divisor>0) || (dividend>0&&divisor<0)){
        isPositive = false;
    }
    
    //判断结束后全部当做正数进行操作
    //使用long解决数值溢出情况
    long ldividend = Math.abs((long)dividend);
    long ldivisor = Math.abs((long)divisor);
    if(ldivisor==0) return Integer.MAX_VALUE;
    if(ldividend==0 || ldividend<ldivisor) return 0;
    
    long result = divide(ldividend, ldivisor);
    if(result>Integer.MAX_VALUE){
        return isPositive? Integer.MAX_VALUE : Integer.MIN_VALUE;
    }
    return (int)(isPositive? result : -result);
}

public long divide(long ldividend, long ldivisor){
    if(ldividend<ldivisor) return 0;
    long sum = ldivisor;
    long result = 1;
    //二分法计算结果
    while(ldividend >= (sum+sum)){
        sum += sum;
        result += result;
    }
    return result + divide(ldividend-sum, ldivisor);
}