【LeetCode】No.29. Divide Two Integers -- Java Version

题目链接： https://leetcode.com/problems/divide-two-integers/

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

【Translate】： 给定两个整数的被除数和除数，两个整数相除时不能使用乘法、除法和取余运算。

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.

【Translate】： 整数除法应该向零截断，这意味着失去小数部分。例如，8.345将被截断为8，-2.7335将被截断为-2。

Return the quotient after dividing dividend by divisor.

【Translate】： 返回商。

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

【Translate】： 注意:假设我们处理的环境只能存储32位带符号整数范围内的整数:[2³¹，2³¹-1]。对于这个问题，如果商严格大于2³¹ - 1，则返回2³¹ - 1，如果商严格小于-2³¹，则返回-2³¹。

【测试用例】：

【约束】：

  该题解的思想就是通过计算数字相减的次数，从而确定商。通过dividend < 0 ^ divisor < 0来确定最后的结果是否为负。

    public int divide(int dividend, int divisor) {
        // return (int) dividend/divisor;
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; 
        int i = 0;
        boolean negative = dividend < 0 ^ divisor < 0;
        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);
        for (i = 0; dividend - divisor >= 0; i++)
        {
            dividend = dividend - divisor;
        }
        return negative? -i : i;
    }

  pprabu49提供的题解Java | 0ms | 100% faster | Obeys all conditions。

解题思想：

1. 以指数方式增加除数，直到它超过被除数，然后用它减去。
2. 将除数相加，求余数。
3. 重复同样的操作，直到它变为 0
   

    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; //Cornor case when -2^31 is divided by -1 will give 2^31 which doesnt exist so overflow 
         
        boolean negative = dividend < 0 ^ divisor < 0; //Logical XOR will help in deciding if the results is negative only if any one of them is negative
        
        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);
        int quotient = 0, subQuot = 0;
        
        while (dividend - divisor >= 0) {
            for (subQuot = 0; dividend - (divisor << subQuot << 1) >= 0; subQuot++);
            quotient += 1 << subQuot; //Add to the quotient
            dividend -= divisor << subQuot; //Substract from dividend to start over with the remaining
        }
        return negative ? -quotient : quotient;
    }