LeetCode_29(Divide Two Integers) 心得(Medium)

6 min readAug 7, 2020

題目:
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, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.

Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -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.

想法:
這題其實滿難的! 不能用乘除，然後又有 edge cases 要考慮!
這題要注意的是 INT_MIN 的處理，因為 INT_MIN / -1 = UINT_MAX。
題目要求 UINT_MAX 要回傳 INT_MAX。

又 abs (INT_MIN) 是超過範圍的，undefined behavior。
所以網路上的解法其實不太對。
因為這個原因，所以我建議直接用 long 下去解。
long 主要是為了處理 INT_MIN，因此搭配”解法4" 會比較合理 (解法4 在運算時候不會在 INT 上 overflow)。

第一個解法是用加法去找出商。
E.g. 15 / 4 = 3 …3 => 15 = 4 + 4+ 4 …. 3
因此就是把除數一直累加直到快超過的次數就是商!
但是這個方法會超時。

第二個解法是第一個解法的改良。
累加的方式用 1, 2, 4, 8 倍數成長 (雖然是2 的倍數成長，但是像下面例子一樣是用累加)。
E.g. 70 / 4 = 16 … 6
第一次累加找最接近
4….X
4+4 = 8 ….X
8+8 = 16 ….X
16 + 16 = 32 ….X
32 + 32 = 64 ….O

70–64 = 6，6 進入第二是累加。
4….O

6–4 = 2, 2 進入第三次累加。
2…. 小於 4!

這個方法可以配合遞迴來解。
可以參考:
https://leetcode.com/problems/divide-two-integers/discuss/13397/Clean-Java-solution-with-some-comment.

第三個解法是用用二進制的除法來思考的!
每個數都可以換成二進制 (binary)
E.g: 5 = 101

二進制也可以像十進制一樣除法。下面網路上找的圖示:

第一次的 “-11” 其實是 1100，也就是要算 10101–1100 ( = 1001)
而這一次的商就是 00100。

第二次的 “-11” 其實是 110，也就是要算 1001–110 ( = 11)
而這一次的商就是 00010。

這兩次的商可以加起來，也就是目前的商是 00110。

第三次的 “-11” 就是 11，要算 11–11 ( = 0)
商就是 00001。

到這邊除法就完成了，把商全部加起來就是 00111。

總結除法:
先把除數"位移X"到最接近被除數的值 (小於等於)，而此時商就是 1 << X。

相減後再重複剛才的流程。

最後把商相加。

第四個解法是第三個解法的變形。

第三個解法是把除數往左 shift，程式上會直接從 shift 31 開始，到 shift 0 判斷過去，往左 shift 可能會 overflow (INT32)，這樣的 behavior 是 undefined。

因此可以換個角度想，除數往左 shift，其實可以換成是被除數往右 shift，這樣就不會有 overflow 的問題了! 其他流程的概念也是一樣!

程式:
我常犯錯的地方是在比較 divisor << i 和 dividend 的時候常常只有用小於，應該是要小於等於。

第三個解法:

class Solution {
public:
    int divide(int dividend, int divisor) {
        int sign = (dividend >= 0 ^ divisor >= 0) ? -1 : 1;
        long long int quotient = 0;
        long long int sum = 0;
        
        long long int dividendL = dividend;
        dividendL = abs(dividendL);
        long long int divisorL = divisor;
        divisorL = abs(divisorL);
        
        for (int i = 31; i >= 0; i--)
        {
            if (sum + (divisorL << i) <= dividendL)
            {
                sum += (divisorL << i);
                quotient += (1LL << i);
            }
        }
        
        if (sign * quotient > INT_MAX)
            return INT_MAX;
            
        
        return sign * quotient;
    }
};

第四個解法:

class Solution {
public:
    int divide(int dividend, int divisor) {
        int sign = (dividend >= 0 ^ divisor >= 0) ? -1 : 1;
        long long int quotient = 0;
        long long int sum = 0;
        
        long long int dividendL = dividend;
        dividendL = abs(dividendL);
        long long int divisorL = divisor;
        divisorL = abs(divisorL);
        
        for (int i = 31; i >= 0; i--)
        {
            if ((dividendL >> i) >= divisorL)
            {
                dividendL -= (divisorL << i);
                quotient += (1LL << i);
            }
        }
        
        if (sign * quotient > INT_MAX)
            return INT_MAX;
            
        
        return sign * quotient;
    }
};

LeetCode_29(Divide Two Integers) 心得(Medium)

Written by ChingYuanYang