題目描述:在不使用乘法、除法和模運算的前提下,計算兩個整數的商。結果若超出 32 位元有號整數範圍 [-2³¹, 2³¹-1],則回傳邊界值。
解題思路:利用位元運算模擬除法。核心思路是:對被除數 dividend,找出最大的 divisor × 2^k 使其不超過 dividend,將商加上 2^k,被除數減去 divisor × 2^k,重複此過程。這等同於二進位除法。需要特別處理溢位情況:INT_MIN / -1 = 2³¹ 超出範圍應回傳 INT_MAX。為避免溢位,統一轉換為負數計算(因為負數範圍比正數大一個),最後再根據符號決定結果正負。
時間複雜度:O(log² n) — 外層迴圈最多執行 O(log n) 次,內層位移迴圈也最多 O(log n) 次。
空間複雜度:O(1) — 只使用常數個變數。
1. Handle special case: dividend == INT_MIN and divisor == -1, return INT_MAX 2. Determine sign based on XOR of signs of dividend and divisor 3. Convert both to positive long values 4. result = 0 5. While a >= b: a. temp = b, multiple = 1 b. While a >= temp * 2: temp *= 2, multiple *= 2 (use bit shifts) c. a -= temp, result += multiple 6. Return sign * result (clamped to int range)
逐一減法:反覆從被除數減去除數並計數,時間 O(dividend/divisor) 最壞情況 O(2³¹) 會超時。
對數法:利用 exp(log(|dividend|) - log(|divisor|)) 計算,但浮點精度問題難以處理邊界情況,不夠穩健。
遞迴二分:遞迴地將除數加倍尋找最大倍數,本質與迭代位移法相同,但需要額外堆疊空間。