

- Divide Two Integers
這題要求在不使用乘法、除法和模數運算子的情況下實現兩個整數的除法。
核心概念:利用減法和位移操作
除法本質上是重複的減法。例如,10÷3 可以看作是從 10 中減去 3 多少次:
10−3=7 (1 次)
7−3=4 (2 次)
4−3=1 (3 次)
1<3,停止。
商就是 3。
然而,如果僅僅使用簡單的重複減法,當被除數(dividend)很大而除數(divisor)很小時(例如 2^31−1÷1),會導致時間複雜度太高(O( dividend/divisor)),這是不可接受的。
為了提高效率,我們需要利用 位移運算(Bitwise Shift),這能讓我們在對數時間內(O(logN))完成除法。
優化方法:指數級減法
我們希望一次減去多個除數,而不是一個一個地減。由於我們不能用乘法,我們可以利用**左位移操作(<<)**來實現 2 的冪次乘法,例如:
3×2^1=3≪1=6
3×2^2=3≪2=12
具體步驟如下:
- 處理邊界條件 (Edge Cases): 特別是溢位情況。
- 確定符號 (Sign): 由於位移操作主要適用於正數,我們通常將兩者都轉換為負數(或絕對值),在計算完商後再應用正確的符號。這裡選擇轉換為負數是因為在 32 位元整數範圍內,負數的範圍比正數大( 的絕對值 無法用正數 表示),使用負數可以避免處理 這個特殊的絕對值溢位問題。
- 重複減法與位移:
o 從最大的 倍的 divisor 開始,檢查是否可以從 dividend 中減去。
o divisor 左移 位(即 )如果仍然 dividend,則執行減法:
dividend 減去 。
商 (quotient) 加上 。
o 不斷重複此過程,直到 dividend 小於 divisor。