LeetCode Divide Two Integers：不使用乘除模實現除法（位運算 + 二分）

關鍵細節

• 符號處理：先記錄符號，將兩數轉為 long long 正數運算，避免 INT_MIN 取絕對值溢出。
• 溢出案例：dividend = INT_MIN, divisor = -1 → 結果 2³¹ 溢出，返回 INT_MAX。
• 循環條件：外層 while (a >= b)，內層 while (a >= (b << shift))。

代碼實現 (C++)

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;
        long long a = llabs((long long)dividend);
        long long b = llabs((long long)divisor);
        int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
        long long res = 0;
        while (a >= b) {
            long long tmp = b, cnt = 1;
            while (a >= (tmp << 1)) {
                tmp <<= 1;
                cnt <<= 1;
            }
            a -= tmp;
            res += cnt;
        }
        return sign > 0 ? (int)res : (int)-res;
    }
};

複雜度分析

• 時間：O(log² n) 或 O(log n)（內層位移最多 log n 次，外層每次至少減半）。實際極快。
• 空間：O(1)。

關鍵點總結

• 用 long long 避免 abs(INT_MIN) 未定義行為。
• 位移模擬乘法：b << k == b * 2^k。
• 指數搜索（倍增）將線性減法加速為對數級。
• 特判 INT_MIN / -1 溢出。

這題是「位運算實現算術運算」的經典練習，展示了如何用移位和減法高效模擬除法，是面試高頻考點。