文章目錄
- 29. 兩數相除(Divide Two Integers)
- 1. 題目重述與約束解析
- 2. 算法選擇與總體設計
- 3. 核心難點與關鍵技巧
- 4. 解法一:快倍增(重復加倍減法)
- 4.1 思路
- 4.2 流程圖
- 4.3 正確性要點
- 5. 解法二:位移長除法(從高位到低位)
- 5.1 思路
- 5.2 流程圖
- 5.3 正確性要點
- 6. 代碼實現(Go)
- 7. 邊界用例與正確性驗證
- 7.1 必測邊界
- 7.2 樣例(摘自 main.go)
- 8. 復雜度分析
- 9. 常見坑位與排錯指南
- 10. 測試策略
- 11. 代碼實現要點 Checklist
- 12. 小結
- 完整題解代碼
29. 兩數相除(Divide Two Integers)
要求:在不使用乘法、除法和取余運算的前提下,計算整數商,向零截斷;同時嚴格按照 32 位有符號整數范圍返回(越界截斷到 INT_MAX/INT_MIN)。
1. 題目重述與約束解析
- 輸入:
dividend
(被除數)、divisor
(除數),二者均為 32 位有符號整數范圍內的值。 - 輸出:
quotient
(商,向零截斷)。 - 禁止:
*
、/
、%
。 - 邊界與異常:
divisor != 0
(題目保證,但實現仍需防御性處理);- 溢出場景:
INT_MIN / -1
,理論答案為 2147483648(超出 32 位上界),需返回INT_MAX
; - 其他結果均需保持在
[INT_MIN, INT_MAX]
內; - 向零截斷:即正負混合時直接丟棄小數部分,如
7 / -3 = -2
。
2. 算法選擇與總體設計
由于禁止使用乘除取余,核心思路是把「除法」轉化為「減法 + 位移(乘2/除2的替代)」。常見可行路線:
- 暴力減法(線性):從被除數中不斷減去除數,計數;時間復雜度 O(|商|),僅用于教學和極小數值。
- 快倍增減法(指數加速):每次嘗試將除數倍增至不超過剩余被除數的最大 2^k 倍,整體像「貪心 + 倍增」,復雜度 O(log(|dividend|))。
- 位移長除法(從高位到低位):類似十進制長除法的二進制版本,逐位構造商,復雜度 O(32) ≈ O(1)。
在工程實踐中:
- 快倍增減法實現簡單、速度穩定;
- 位移長除法邏輯清晰、邊界好控;
- 兩者均需小心:符號處理、使用 int64 承接中間量避免溢出、INT_MIN 絕對值處理等。
本文給出兩種主力解法:
-「快倍增減法」與「位移長除法」。并提供線性減法作為校驗/教學版本。
3. 核心難點與關鍵技巧
- 符號處理:結果符號 =
(dividend < 0) XOR (divisor < 0)
;可統一轉正處理后在結果末尾加符號。 - 極值處理:
INT_MIN
的絕對值在 32 位有符號中不可表示,需轉int64
后再abs64
。 - 上溢保護:僅
INT_MIN / -1
會上溢;處理在最開始即可提前返回INT_MAX
。 - 位運算:使用
<<
作為乘 2,>>
作為除 2 的替代;嚴格避免使用*
、/
、%
。
4. 解法一:快倍增(重復加倍減法)
4.1 思路
- 將除數不斷左移(乘 2)直至超過當前剩余被除數之前的最大值,并記錄對應的倍數
mul
(同樣左移)。 - 用該最大倍數從被除數中一次性減去,累加
mul
到答案; - 循環直到剩余被除數小于原始除數。
4.2 流程圖
flowchart TDA[開始] --> B[特判: divisor=0? INT_MIN/-1?]B --> C[轉為int64并取絕對值]C --> D{ad >= adv?}D -->|否| E[返回結果(帶符號/截斷)]D -->|是| F[tmp=adv, mul=1]F --> G{ad >= (tmp<<1)?}G -->|是| H[tmp<<=1, mul<<=1]H --> GG -->|否| I[ad-=tmp, res+=mul]I --> D
4.3 正確性要點
- 每輪選擇不超過剩余被除數的最大 2^k 倍,保證每次盡可能大的推進,輪數 O(log 倍數)。
- 等價于把被除數
ad
拆成若干個adv * 2^k
的和,商即所有對應2^k
之和。
5. 解法二:位移長除法(從高位到低位)
5.1 思路
- 將被除數與除數都取正(int64)。
- 維護答案
res=0
,從第 31 位到第 0 位嘗試:- 若
(ad >> i) >= adv
,說明除數左移i
位不超過當前剩余,則將該位加入商:res += 1<<i
,并扣減ad -= adv<<i
。
- 若
- 結束后按符號還原,并做截斷。
5.2 流程圖
flowchart TDA[開始] --> B[特判: divisor=0? 溢出?]B --> C[轉為int64并取絕對值]C --> D[i=31..0 遍歷]D --> E{(ad>>i) >= adv?}E -->|是| F[res+=1<<i; ad-=adv<<i]E -->|否| G[繼續下一位]F --> DG --> DD --> H[結果帶符號&截斷返回]
5.3 正確性要點
- 與十進制長除法一致,是逐位確定商位是否為 1 的過程;
- 由于 32 位固定,因此復雜度近似 O(1)。
6. 代碼實現(Go)
所有實現均不使用
*
、/
、%
;中間量統一用int64
;集中處理溢出與符號。
package mainimport ("fmt"
)const (INT_MAX = 2147483647INT_MIN = -2147483648
)// divide 快倍增減法
func divide(dividend int, divisor int) int {if divisor == 0 {return INT_MAX}if dividend == INT_MIN && divisor == -1 {return INT_MAX}d := int64(dividend)dv := int64(divisor)neg := (d < 0) != (dv < 0)ad := abs64(d)adv := abs64(dv)var res int64 = 0for ad >= adv {tmp := advmul := int64(1)for ad >= (tmp << 1) {tmp <<= 1mul <<= 1}ad -= tmpres += mul}if neg { res = -res }if res > int64(INT_MAX) { return INT_MAX }if res < int64(INT_MIN) { return INT_MIN }return int(res)
}// divideBit 位移長除法
func divideBit(dividend int, divisor int) int {if divisor == 0 { return INT_MAX }if dividend == INT_MIN && divisor == -1 { return INT_MAX }d := int64(dividend)dv := int64(divisor)neg := (d < 0) != (dv < 0)ad := abs64(d)adv := abs64(dv)var res int64 = 0for i := 31; i >= 0; i-- {if (ad>>i) >= adv {res += 1 << uint(i)ad -= adv << uint(i)}}if neg { res = -res }if res > int64(INT_MAX) { return INT_MAX }if res < int64(INT_MIN) { return INT_MIN }return int(res)
}// divideLinear 線性減法(僅教學/小值)
func divideLinear(dividend int, divisor int) int {if divisor == 0 { return INT_MAX }if dividend == INT_MIN && divisor == -1 { return INT_MAX }if dividend == 0 { return 0 }d := int64(dividend)dv := int64(divisor)neg := (d < 0) != (dv < 0)ad := abs64(d)adv := abs64(dv)var res int64 = 0for ad >= adv { ad -= adv; res++ }if neg { res = -res }if res > int64(INT_MAX) { return INT_MAX }if res < int64(INT_MIN) { return INT_MIN }return int(res)
}func abs64(x int64) int64 { if x < 0 { return -x }; return x }func main() {fmt.Println("兩數相除(不使用乘/除/取余)測試")fmt.Println("=========================")// 用例略,詳見工程 main.go
}
7. 邊界用例與正確性驗證
7.1 必測邊界
INT_MIN / -1
→INT_MAX
INT_MIN / 1
→INT_MIN
0 / 正數
→0
正/負
組合,向零截斷:7 / -3 = -2
;-7 / 3 = -2
- 被除數絕對值小于除數:
5/7=0
,-1/2=0
graph LRA[邊界組] --> B[INT_MIN/-1]A --> C[INT_MIN/1]A --> D[0/x]A --> E[符號混合]A --> F[|a|<|b|]
7.2 樣例(摘自 main.go)
10/3 = 3
、7/-3 = -2
、INT_MIN/-1 = INT_MAX
、INT_MIN/1 = INT_MIN
、INT_MAX/2 = 1073741823
、INT_MIN/-3 = 715827882
等。- 雙實現(
divide
與divideBit
)結果一致,線性減法在小范圍下輔助校驗。
8. 復雜度分析
- 快倍增減法:
- 時間:O(log(|dividend|)),每輪倍增后再一次減法;
- 空間:O(1)。
- 位移長除法:
- 時間:O(32)≈O(1);
- 空間:O(1)。
- 線性減法:
- 時間:O(|商|),僅用于教學。
graph TDA[復雜度對比] --> B[快倍增 O(logN)]A --> C[長除 O(1)]A --> D[線性 O(|商|)]
9. 常見坑位與排錯指南
- 忽略
INT_MIN / -1
上溢:務必提前特判。 - 直接對
INT_MIN
調用abs
(32位)溢出:需轉int64
再取絕對值。 - 符號處理在末尾統一加,過程使用正數比較更簡單。
- 位移時使用
uint(i)
,避免移位負值導致未定義行為。 - 結果最終截斷到
[INT_MIN, INT_MAX]
;雖然理論不會越界(除上述特判),但保持防御性。
10. 測試策略
- 功能測試:
- 隨機正負組合,保證向零截斷;
- 大數場景,特別是
INT_MIN
、INT_MAX
邊界; - 被除數小于除數的結果為 0。
- 一致性測試:
divide
與divideBit
結果一致;- 小范圍同時與
divideLinear
對照。
- 性能測試:
- 大量隨機對,統計耗時分布(快倍增與長除均足夠快)。
11. 代碼實現要點 Checklist
- 統一用
int64
承接中間量 - 先行特判
INT_MIN/-1
- 結果按符號還原并做上下界截斷
- 避免任何
*
、/
、%
- 兩套主力算法 + 線性校驗
12. 小結
- 本題的關鍵在于用「位移 + 減法」重建除法的語義,并在極值與符號上嚴謹處理。
- 快倍增減法與位移長除法都能穩定在 O(logN) 或 O(1) 時間內完成計算,滿足面試與工程要求。
- 牢記唯一溢出點
INT_MIN / -1
,及INT_MIN
絕對值取值細節。
運行:進入
29/
目錄,執行go run main.go
可查看樣例與斷言輸出。
完整題解代碼
package mainimport ("fmt"
)const (INT_MAX = 2147483647INT_MIN = -2147483648
)// divide 使用快倍增(重復加倍減法)實現除法,不使用乘/除/取余
func divide(dividend int, divisor int) int {// 邊界:除數為0(按題意不會發生),但保險起見if divisor == 0 {return INT_MAX}// 溢出邊界:INT_MIN / -1if dividend == INT_MIN && divisor == -1 {return INT_MAX}// 統一轉為 int64 處理,避免中間溢出d := int64(dividend)dv := int64(divisor)// 記錄符號neg := (d < 0) != (dv < 0)// 取絕對值(在 int64 范圍內安全)ad := abs64(d)adv := abs64(dv)// 快倍增:每次找到不超過 ad 的 adv 的最大 2^k 倍var res int64 = 0for ad >= adv {tmp := advmul := int64(1)for ad >= (tmp << 1) {tmp <<= 1mul <<= 1}ad -= tmpres += mul}if neg {res = -res}// 截斷到 32 位范圍if res > int64(INT_MAX) {return INT_MAX}if res < int64(INT_MIN) {return INT_MIN}return int(res)
}// divideBit 位移長除法:從高位到低位構造結果
func divideBit(dividend int, divisor int) int {if divisor == 0 {return INT_MAX}if dividend == INT_MIN && divisor == -1 {return INT_MAX}d := int64(dividend)dv := int64(divisor)neg := (d < 0) != (dv < 0)ad := abs64(d)adv := abs64(dv)var res int64 = 0// 從 31 到 0 嘗試(32位)for i := 31; i >= 0; i-- {if (ad >> i) >= adv {res += 1 << uint(i)ad -= adv << uint(i)}}if neg {res = -res}if res > int64(INT_MAX) {return INT_MAX}if res < int64(INT_MIN) {return INT_MIN}return int(res)
}// divideLinear 線性減法(僅作教學/小數值驗證,不建議大數據)
func divideLinear(dividend int, divisor int) int {if divisor == 0 {return INT_MAX}if dividend == INT_MIN && divisor == -1 {return INT_MAX}if dividend == 0 {return 0}d := int64(dividend)dv := int64(divisor)neg := (d < 0) != (dv < 0)ad := abs64(d)adv := abs64(dv)var res int64 = 0for ad >= adv {ad -= advres++}if neg {res = -res}if res > int64(INT_MAX) {return INT_MAX}if res < int64(INT_MIN) {return INT_MIN}return int(res)
}func abs64(x int64) int64 {if x < 0 {return -x}return x
}func main() {fmt.Println("兩數相除(不使用乘/除/取余)測試")fmt.Println("=========================")tests := []struct {dividend intdivisor intexpect intname string}{{10, 3, 3, "10/3"},{7, -3, -2, "7/-3"},{INT_MIN, -1, INT_MAX, "INT_MIN/-1 溢出"},{INT_MIN, 1, INT_MIN, "INT_MIN/1"},{0, 1, 0, "0/1"},{1, 1, 1, "1/1"},{-1010369383, -2147483648, 0, "小于1的絕對值商"},{INT_MAX, 2, 1073741823, "INT_MAX/2"},{INT_MIN, -3, 715827882, "INT_MIN/-3"},{-2147483647, 2, -1073741823, "-2147483647/2"},}for _, tc := range tests {fmt.Printf("\n用例: %s dividend=%d divisor=%d\n", tc.name, tc.dividend, tc.divisor)ans1 := divide(tc.dividend, tc.divisor)ans2 := divideBit(tc.dividend, tc.divisor)// 線性法只在小值時驗證,避免長時間var ans3 intif abs64(int64(tc.dividend)) < 1000 && abs64(int64(tc.divisor)) > 0 {ans3 = divideLinear(tc.dividend, tc.divisor)fmt.Printf("divideLinear: %d\n", ans3)}fmt.Printf("divide : %d\n", ans1)fmt.Printf("divideBit : %d\n", ans2)fmt.Printf("期望 : %d\n", tc.expect)}
}