【LeetCode】29. 兩數相除(Divide Two Integers)

文章目錄

  • 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 / -1INT_MAX
  • INT_MIN / 1INT_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 = 37/-3 = -2INT_MIN/-1 = INT_MAXINT_MIN/1 = INT_MININT_MAX/2 = 1073741823INT_MIN/-3 = 715827882 等。
  • 雙實現(dividedivideBit)結果一致,線性減法在小范圍下輔助校驗。

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_MININT_MAX 邊界;
    • 被除數小于除數的結果為 0。
  • 一致性測試:
    • dividedivideBit 結果一致;
    • 小范圍同時與 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)}
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/920420.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/920420.shtml
英文地址,請注明出處:http://en.pswp.cn/news/920420.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

智能物聯網(AIoT)核心技術落地路徑與企業數字化轉型適配方案

一、行業現狀&#xff1a;AIoT 落地潛力與企業轉型痛點并存根據中國信通院《2023 年中國物聯網發展白皮書》數據&#xff0c;截至 2023 年&#xff0c;我國物聯網設備連接數已突破 300 億&#xff0c;龐大的設備基數為企業數字化轉型奠定了技術基礎。但與之形成鮮明對比的是&am…

前端文件下載的三種方式:URL、二進制與 Base64 的深度解析

前言在 Web 應用開發中&#xff0c;文件下載是一個常見的功能需求。從簡單的圖片保存到復雜的報表導出&#xff0c;前端開發者需要根據后端返回的數據格式選擇合適的處理方式。本文探討三種主流的文件下載方式 —— 基于 URL、二進制數據和 Base64 編碼的實現原理、區別對比及通…

B站 XMCVE Pwn入門課程學習筆記(8)

這個視頻講的比較難&#xff0c;我花了比較長時間來分析&#xff0c;甚至一個點反復很多次&#xff0c;這也是在學PWN的過程中不可避免的&#xff0c;需要堅持和毅力pwn3:沒有system&#xff0c;通過ROP調用write的plt入口&#xff0c;執行write函數&#xff0c;并且將gots里的…

AMGCL介紹和使用

文章目錄一、AMGCL 簡介1.1 什么是 AMG&#xff1f;1.2 AMGCL 特點二、安裝與配置2.1 獲取源碼2.2 編譯依賴&#xff08;可選&#xff09;三、基本使用示例3.1 構造稀疏矩陣&#xff08;以 1D Poisson 為例&#xff09;四、核心組件介紹4.1 后端&#xff08;Backend&#xff09…

AI解決生活小事系列——用AI給我的電腦做一次“深度體檢”

哈嘍&#xff0c;大家好&#xff0c;這里是Ai極客團長&#xff0c;我打算做一個用AI解決生活實際問題的系列專欄。 決定做這個系列的初衷很簡單&#xff1a;現在打開手機、電腦&#xff0c;到處都是 "AI 改變世界" 的宏大敘事&#xff0c;但對普通人來說&#xff0c…

JavaWeb 30 天入門:第二十一天 ——AJAX 異步交互技術

在前二十天的學習中&#xff0c;我們掌握了 JavaWeb 開發的核心技術&#xff0c;包括 Servlet、JSP、會話管理、過濾器、監聽器、文件操作、數據庫交互、連接池、分頁與排序等。今天我們將學習一項徹底改變 Web 應用交互方式的技術 ——AJAX&#xff08;Asynchronous JavaScrip…

從枯燥C++到趣味音樂:我的Windows系統底層探索之旅

一段穿越計算機抽象層次的旅程&#xff0c;從高級語言到底層硬件&#xff0c;探索代碼如何創造美妙旋律第一章&#xff1a;初學C的枯燥與靈感閃現 當我第一次打開《C Primer Plus》這本厚重的教程時&#xff0c;面對那些晦澀的語法規則和抽象概念&#xff0c;確實感到有些枯燥乏…

taro+vue3+vite項目 tailwind 踩坑記,附修復后的模板源碼地址

tailwind 踩坑記 這&#xff0c;是taro官網地址&#xff1a;taro引入tailwind的教程 我完全按照上面的步驟來&#xff0c;結果根本無效&#xff08;文檔太過時了&#xff09; 我后來又按照 weapp-tailwindcss 的官方文檔做了一番修正&#xff1a; weapp-tailwindcss Taro (所…

LCEDA電氣規則

MARK點普通問題 鋪銅太靠近MARK點放置一個禁止區域&#xff0c;圓形編輯封裝

無人機Remote ID:天空中的數字車牌與未來空域管理

一架沒有牌照的汽車上路會被交管部門處罰,那么一架沒有“數字車牌”的無人機升空呢?隨著無人機Remote ID技術的推廣,未來天空中的每架無人機都將擁有自己的身份標識。 近年來,無人機呈爆炸式增長,從航拍攝影到物流配送,從農業植保到應急救援,應用場景不斷拓展。但隨著無…

自下而上的樹形dp

最大獨立集 1.藍橋舞會 link:1.藍橋舞會 - 藍橋云課 分析&#xff1a; code #include <bits/stdc.h> using namespace std; using ll long long; const ll MAXN 1e5 7; ll hpy[MAXN], fa[MAXN], dp[MAXN][2]; vector<ll> sons[MAXN];void dfs(ll u, ll fa) {…

Docker 詳解+示例

介 紹Docker 是一個開源的容器化平臺&#xff0c;它的核心目標是解決 “軟件在不同環境下運行不一致” 的問題&#xff0c;實現 “一次構建&#xff0c;到處運行” 。它基于 Linux 內核的底層技術&#xff0c;將應用程序及其依賴&#xff08;如庫文件、配置、運行環境等&#x…

洛谷 P2568 GCD-提高+/省選?

題目描述 給定正整數 nnn&#xff0c;求 1≤x,y≤n1\le x,y\le n1≤x,y≤n 且 gcd?(x,y)\gcd(x,y)gcd(x,y) 為素數的數對 (x,y)(x,y)(x,y) 有多少對。 輸入格式 只有一行一個整數&#xff0c;代表 nnn。 輸出格式 一行一個整數表示答案。 輸入輸出樣例 #1 輸入 #1 4輸…

軟件測試覆蓋率與質量保障專業經驗分享報告

測試覆蓋率的核心維度與評估標準 多維度定義與核心內涵 測試覆蓋率是衡量軟件測試完整性的關鍵指標體系,分為測試覆蓋率(黑盒視角:需求驗證程度)和代碼覆蓋率(白盒視角:代碼執行占比)兩大基礎類型。現代測試覆蓋體系已擴展至產品覆蓋、風險覆蓋、平臺/設備覆蓋、數據覆…

使用CCProxy搭建http/https代理服務器

下載 https://user.youngzsoft.com/ccproxy/update/ccproxysetup.exe 我們使用免費的即可&#xff0c;3個人。 啟動軟件 設置 更改局域網IP 我的電腦有多個IP&#xff0c;所以要手工指定。

ICCV 2025|TRACE:無需標注,用3D高斯直接學習物理參數,從視頻“預知”未來!

論文鏈接&#xff1a;https://arxiv.org/pdf/2507.01484導讀 準確預測道路智能體的運動對于自動駕駛的安全性至關重要。當前&#xff0c;現有的數據驅動方法直接預測未來軌跡&#xff0c;缺乏對駕駛行為的充分考慮&#xff0c;限制了可解釋性和可靠性。為此&#xff0c;本文引入…

TypeScript:symbol類型

symbol是TypeScript和JavaScript中的一種基本數據類型&#xff0c;表示唯一的、不可變的標識符。作為專業的前端工程師&#xff0c;理解symbol的特性對于構建安全可靠的代碼至關重要。1. symbol的核心特性唯一性&#xff1a;每個symbol值都是唯一的&#xff0c;即使創建時使用相…

【深度學習新浪潮】顯著性檢測最新研究進展(2022-2025)

1. 弱監督與主動學習 ASTE-AL框架(TPAMI 2024):提出對抗性時空集成主動學習方法,通過點標記數據集(每張圖像僅需10個標注點)達到全監督模型98%-99%的性能。其核心模塊包括: FPGD-PA對抗攻擊:通過無額外計算成本的自由梯度下降攻擊定位不確定像素。 時空集成策略:減少模…

Intern-S1-mini模型結構

模型介紹 Intern-S1-mini基于一個8B密集語言模型&#xff08;Qwen3&#xff09;和一個0.3B視覺編碼器&#xff08;InternViT&#xff09;&#xff0c;Intern-S1-mini 在5萬億個標記的多模態數據上進行了進一步預訓練&#xff0c;其中包括超過2.5萬億個科學領域的標記。這使得該…

linux 100個問答(持續更新)

1.常用命令 2.rsync常用命令rsync 是?個強?的?件同步和復制?具&#xff0c;?于在本地和遠程系統之間同步?件和目錄。以下是?些常用的 rsync 命令和選項&#xff1a;1. 基本的 rsync rsync 命令格式&#xff1a; bashCopy code rsync [options] source destination● sou…