29. Divide Two Integers

📘 題目敘述

給你兩個整數 dividend 和 divisor，請在不使用乘法、除法、取模運算子的情況下完成相除，並回傳商（quotient）。

整數除法需朝 0 截斷（truncate toward zero）。若超出 32-bit 有號整數範圍，回傳邊界值。

條件限制

• -2^31 <= dividend, divisor <= 2^31 - 1
• divisor != 0

🧠 解題思路

核心想法是使用「加倍（doubling）」加速減法：每輪找出最大的 temp = b * 2^t，使得 temp <= a，再一次扣掉這大塊並把對應倍數加入答案。

兩個重點：

1. 溢位特例：INT_MIN / -1 會超出 INT_MAX，直接回傳 INT_MAX。
2. 正負號：用 XOR 判斷答案是否為負數。

所有變數

• dividend：被除數
• divisor：除數
• sign：答案是否為負數
• a：dividend 的絕對值（long long）
• b：divisor 的絕對值（long long）
• ans：累積商
• temp：當前可扣除的加倍除數
• mul：temp 對應倍數

🪜 主要流程步驟

1. 先處理唯一溢位特例：INT_MIN / -1 直接回傳 INT_MAX。
2. 計算正負號，並把被除數/除數轉成絕對值。
3. 外層迴圈在 a >= b 時持續進行：
   • 內層用加倍找到最大的 temp（temp + temp <= a）。
   • 更新 a -= temp、ans += mul。
4. 依 sign 回傳 -ans 或 ans。

💻 程式碼實作

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }
        bool sign = (dividend > 0) ^ (divisor > 0); // XOR, true為負
        long long a = llabs((long long)dividend);
        long long b = llabs((long long)divisor);
        long long ans = 0;
        while (a >= b) {
            long long temp = b;
            long long mul = 1;
            while (temp + temp <= a) {
                temp += temp;
                mul += mul;
            }
            a -= temp;
            ans += mul;
        }
        return (sign ? -ans : ans);
    }
};

🔗 題目連結

https://leetcode.com/problems/divide-two-integers/