LeetCode Top Interview Questions 29. Divide Two Integers (Java版； Medium)

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

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Note:

Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. 
For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows

class Solution {
    public int divide(int dividend, int divisor) {
        int flag = dividend>0 ^ divisor>0 ? -1 : 1;
        int res = 0;
        if(dividend==Integer.MIN_VALUE){
            if(divisor==-1){
                return Integer.MAX_VALUE;
            }
            if(divisor==Integer.MIN_VALUE){
                return 1;
            }
            dividend = dividend + Math.abs(divisor);
            res++;
        }
        //
        if(divisor==Integer.MIN_VALUE){
            return 0;
        }
        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);
        while(dividend >= divisor){
            int count = 1;
            int cur = divisor;
            //cur >= 2*cur
            while(dividend - cur >= cur){
                count = count * 2;
                //
                cur = cur * 2;
            }
            res = res + count;
            dividend = dividend - cur;
        }
        return res*flag;
    }
}

/*
不用乘法,除法,取模操作进行除法运算
因为涉及取绝对值的操作, 所以要格外小心dividend和divisor为Integer.MIN_VALUE的情况, 因为Math.abs(Integer.MIN_VALUE)=Integer.MIN_VALUE

整体流程:
    1.判断符号
    2.讨论dividend为Integer.MIN_VALUE的情况
    3.讨论divisor为Integer.MIN_VALUE的情况
    4.将dividend和divisor都变成正数进行处理, 判断dividend中有几个完整的divisor, 由于不能用乘法, 所以用移位操作
细节:
    1.当divisor为Integer.MIN_VALUE时,只有dividend为Integer.MIN_VALUE时quotient为1, 其他的dividend的对应结果都是0
    2.cur<<1可能会越界, 所以执行cur<<1操作前可以用dividend-cur >= cur 判断cur能否乘2
    3.方法的本质: while循环的操作就是计算dividend里有多少个divisor,可以一个一个的累加divisor, 这样做的缺点是太慢了; 可以通过移位操作成倍的增加divisor的数量, 当divisor不能再加倍时,从dividend中减去divisor, 然后使用新的dividend继续计算包含多少个最原始的divisor
*/
class Solution {
    public int divide(int dividend, int divisor) {
        //判断符号
        int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
        //最终结果
        int res = 0;
        //需要注意Integer.MIN_VALUE
        if(dividend==Integer.MIN_VALUE){
            if(divisor==-1)
                return Integer.MAX_VALUE;
            if(divisor==Integer.MIN_VALUE)
                return 1;
            //核心:因为接下来要对数字取绝对值,所以得改变一下dividend. 相当于从dividend绝对值中减去了一个divisor, 这也是为什么res执行++操作
            dividend = dividend + Math.abs(divisor);
            res++;
        }
        if(divisor==Integer.MIN_VALUE)
            return 0;
        //转成正数计算
        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);
        //不考虑余数, 所以只需要考虑dividend >= divisor的情况即可
        while(dividend >= divisor){
            //记录内循环执行的次数
            int count = 1;
            int cur = divisor;
            //循环条件很细节, 防止2*cur越界
            while(dividend - cur >= cur){
                count = count << 1;      
                cur = cur << 1;
            }
            //
            res = res + count;
            //细节: 移位要带括号, 因为移动操作优先级太低了 
            dividend = dividend - cur;
        }
        return sign>0?res:-res;
    }
}

class Solution {
    public int divide(int dividend, int divisor) {
        int sign = (dividend<0)^(divisor<0) ? -1 : 1, quotient = 0;
        if(dividend == Integer.MIN_VALUE){
            if(divisor == -1) return Integer.MAX_VALUE;
            if(divisor == Integer.MIN_VALUE) return 1;
            //细节:减小dividend, 防止取绝对值时溢出, 因为Math.abs(-2147483648)=-2147483648
            dividend += Math.abs(divisor);
            quotient++;
        }
        if(divisor == Integer.MIN_VALUE) return 0;
        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor); //Math.abs(-2147483648)=-2147483648
        while(dividend >= divisor){
            //count初始成1更合适, 我开始初始成0
            int tmp = divisor, count = 1;
            //细节:循环条件不能用dividend >= tmp<<1, 因为tmp<<1的结果可能会溢出!! 我踩了这个坑
            while(dividend - tmp >= tmp){ //(dividend >= tmp<<1 or >= 2*tmp) may cause overflows
                tmp <<= 1;
                count <<= 1;
            }
            dividend -= tmp;
            quotient += count;
        }
        return sign * quotient;
    }
}

/*
参考评论区的题解，用左移去减。
正数边界问题比较麻烦，所以改用负数计算。
*/
class Solution {
    public int divide(int dividend, int divisor) {
        boolean sign = (dividend > 0) ^ (divisor > 0);
        int result = 0;
        if(dividend>0) {
            dividend = -dividend;
        }
        if(divisor>0) divisor = -divisor;
        while(dividend <= divisor) {
            int temp_result = -1;
            int temp_divisor = divisor;
            while(dividend <= (temp_divisor << 1)) {
                if(temp_divisor <= (Integer.MIN_VALUE >> 1))break;
                temp_result = temp_result << 1;
                temp_divisor = temp_divisor << 1;
            }
            dividend = dividend - temp_divisor;
            result += temp_result;
        }
        if(!sign) {
            if(result <= Integer.MIN_VALUE) return Integer.MAX_VALUE;
            result = - result;
        }
        return result;
    }
}