LeetCode 兩數相除：位運算模擬除法 O(log n)

題目描述

不使用乘法、除法、取模運算，實現兩整數相除。溢出返回 INT_MAX。

範例：

dividend = 10, divisor = 3 → 3
dividend = 7, divisor = -3 → -2

解題思路：倍增法（位運算加速減法）

直觀減法 O(n) 會超時。利用二進制性質：任何整數可分解為 2 的冪次之和。

dividend = divisor * (flag0*2^0 + flag1*2^1 + ...)

算法步驟：

1. 處理符號，轉為正數運算（用 long 防溢出）
2. 外層循環：被除數 ≥ 除數
3. 內層循環：除數左移（×2）直到超過被除數，記錄移位次數 i
4. 被除數減去 divisor << i，結果加 1 << i
5. 恢復符號，檢查溢出

時間複雜度：O(log n)，空間複雜度：O(1)。

C++ 參考實現

class Solution {
public:
    int divide(int dividend, int divisor) {
        // 特殊情況
        if (dividend == 0) return 0;
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;  // 溢出
        
        bool negative = (dividend > 0) ^ (divisor > 0);
        long a = std::labs((long)dividend);
        long b = std::labs((long)divisor);
        long result = 0;
        
        while (a >= b) {
            long temp = b, multiple = 1;
            while (a >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }
            a -= temp;
            result += multiple;
        }
        
        return negative ? -result : result;
    }
};

核心要點總結

• 位運算本質：左移 = ×2，右移 = ÷2，將線性減法加速為對數級
• 溢出處理：INT_MIN / -1 唯一溢出情況，long 避免中間過程溢出
• 符號分離：先算絕對值，最後加符號
• 類型陷阱：abs(INT_MIN) 未定義行為，必須轉 long 再 labs

這道題是位運算替代算術運算的經典範例，掌握「倍增法」核心思想，可應用於大整數運算、定點數除法等底層算法實現。