LeetCode 29 兩數相除：無乘除取模實現商計算，邊界條件全覆蓋

題目要求

給定 dividend (被除數) 和 divisor (除數)，不使用乘法、除法、取模 運算符，返回商。結果截斷向零取整。32 位有符號整數範圍，溢出返回 INT_MAX。

核心思路：位移加速 (指數級查找)

利用 a << k = a × 2^k，將除法轉化為「被除數能減去多少個 divisor × 2^k」。

示例：23 ÷ 4

4 << 2 = 16 ≤ 23  → 商貢獻 2² = 4
23 - 16 = 7
4 << 1 = 8 > 7
4 << 0 = 4 ≤ 7   → 商貢獻 2⁰ = 1
7 - 4 = 3 < 4 結束
商 = 4 + 1 = 5

完整代碼 (含詳細邊界處理)

class Solution {
public:
    int divide(int dividend, int divisor) {
        // 0. 特殊值處理
        if (divisor == 0) return INT_MAX;      // 除數為0
        if (dividend == 0) return 0;           // 被除數為0
        if (divisor == 1) return dividend;     // 除數1
        if (divisor == -1) {                   // 除數-1，注意溢出
            if (dividend == INT_MIN) return INT_MAX; // -2147483648 / -1 = 2147483648 溢出
            return -dividend;
        }

        // 1. 符號處理：統一轉為負數運算 (避免 INT_MIN 絕對值溢出)
        bool negative = (dividend > 0) ^ (divisor > 0);
        if (dividend > 0) dividend = -dividend;
        if (divisor > 0) divisor = -divisor;

        // 2. 位移加速主循環
        int quotient = 0;
        while (dividend <= divisor) { // 負數比較：-10 <= -3 表示 |10| >= |3|
            int shift = 0;
            // 找到最大 shift 使得 divisor << shift >= dividend (負數意義)
            while (dividend <= (divisor << shift) && (divisor << shift) < 0) {
                ++shift;
            }
            --shift; // 回退一步
            dividend -= divisor << shift;
            quotient += 1 << shift;
        }

        return negative ? -quotient : quotient;
    }
};

關鍵邊界條件總結

為什麼用負數運算？

INT_MIN = -2147483648，其絕對值 2147483648 超出 int 範圍 (INT_MAX = 2147483647)。統一轉為負數，範圍對稱 [-2147483648, 0]，無溢出風險。

複雜度

• 時間：O(log n) — 外層循環每次至少減半，內層位移 O(log n)
• 空間：O(1)

優化版本：避免內層重複位移

// 預計算 divisor 的倍數
vector doubles;
vector powers;
doubles.push_back(divisor);
powers.push_back(1);
while (doubles.back() >= dividend && doubles.back() < 0) {
    doubles.push_back(doubles.back() + doubles.back()); // 相加代替左移
    powers.push_back(powers.back() + powers.back());
}

// 從大到小貪心減
for (int i = doubles.size()-1; i >= 0; --i) {
    if (dividend <= doubles[i]) {
        dividend -= doubles[i];
        quotient += powers[i];
    }
}

將內層循環提前預計算，實際運行更快。