題目

題目翻譯

要求你實現除法，但是不能使用乘法、除法和取餘數

解題思路

這題要求模擬兩個整數的除法運算，不允許使用乘法、除法和取模運算符。問題要求返回商值，如果商超過整數範圍（32位帶符號整數範圍），需要返回 INT_MAX 或 INT_MIN。

思路：

1. 處理正負號：除數和被除數的正負號會影響最終商的符號，因此首先處理這一部分，計算結果的正負號。

2. 轉換為正數運算：為了簡化運算，將被除數和除數都轉換成正數進行運算，通過 abs() 來處理。

3. 位移運算：通過位移的方式來實現高效除法：

   • 每次嘗試將除數左移，直到超過被除數。這樣可以一次減去較大的倍數，減少運算次數。
   • 左移的操作等效於乘以 2，所以這樣的策略可以有效地模擬除法的過程。

4. 處理溢出：如果最終計算的結果超過了 32 位整數的上限 INT_MAX 或下限 INT_MIN，則返回相應的極限值。

改進的程式碼

class Solution {
public:
    int divide(int dividend, int divisor) {
        // 特殊情況: 如果被除數是 INT_MIN 且除數是 -1，會溢出
        if (dividend == INT_MIN && divisor == -1)
            return INT_MAX;

        // 確定結果的正負號
        int sign = (dividend >= 0 ^ divisor >= 0) ? -1 : 1;

        // 使用 long long 避免溢出，並取被除數和除數的絕對值
        long long dividendL = labs(dividend);
        long long divisorL = labs(divisor);

        long long quotient = 0;
        long long sum = 0;

        // 利用位移進行除法計算
        for (int i = 31; i >= 0; i--) {
            if (sum + (divisorL << i) <= dividendL) {
                sum += (divisorL << i);
                quotient += (1LL << i);
            }
        }

        // 返回帶正負號的商，並處理溢出
        return sign * quotient;
    }
};

解題步驟

1. 處理邊界情況：

   • 如果被除數是 INT_MIN 並且除數是 -1，這會導致溢出，因此返回 INT_MAX。

2. 確定正負號：

   • 使用異或運算 ^ 來判斷結果的正負號。如果被除數和除數符號不同，則結果為負數，否則為正數。

3. 使用位移進行除法計算：

   • 通過位移操作將除數不斷左移（即乘以 2），直到左移的結果不再小於或等於被除數。這樣可以加速計算，類似於逐步減去更大的除數倍數來計算商。

4. 返回結果：

   • 最後將商乘以計算出的符號來得到結果。如果結果超過整數範圍，則返回相應的極限值。

時間與空間複雜度

• 時間複雜度：O(32) ≈ O(1)。由於每次左移一位，最多需要進行 32 次檢查，因此時間複雜度是常數級別。

• 空間複雜度：O(1)，只使用了常數額外空間。