1. 從一道禁用除模的題說起它到底在考什么給定兩個(gè)整數(shù) A 和 B要求在不使用除法/和取模%運(yùn)算的前提下求出 A 除以 B 的商和余數(shù)。這道題第一次看到的時(shí)候很多人的第一反應(yīng)是這不是故意為難人嗎——明明一行A / B和A % B就能搞定的事為什么要繞這么大一圈但如果你真的在底層開發(fā)、嵌入式、算法競(jìng)賽或者面試場(chǎng)景里摸爬滾打過一段時(shí)間就會(huì)明白這類題目從來不是為了讓你重新發(fā)明除法而是在考察幾件非常實(shí)在的能力對(duì)整數(shù)運(yùn)算邊界的敏感度、對(duì)二進(jìn)制位運(yùn)算的熟練程度、以及對(duì)效率這件事的量化判斷。我自己第一次遇到這個(gè)題是在準(zhǔn)備一場(chǎng)技術(shù)面試的時(shí)候當(dāng)時(shí)腦子里只有最樸素的減法循環(huán)思路寫出來之后面試官追問了一句如果 A 是 20 億、B 是 1你這個(gè)循環(huán)要跑多少次我當(dāng)場(chǎng)就意識(shí)到問題的嚴(yán)重性了。后來我把這道題反復(fù)拆解、用不同的思路實(shí)現(xiàn)、做了性能對(duì)比才真正把它吃透。這篇文章就把我踩過的坑、試過的方案、以及每種方案背后的取舍邏輯完整地分享出來不管你是剛學(xué)編程的新手還是想復(fù)習(xí)位運(yùn)算的老手應(yīng)該都能從中拿到點(diǎn)東西。需要先明確幾個(gè)前提因?yàn)檫@道題的坑很大一部分藏在邊界條件里。第一A 和 B 都是整數(shù)但具體是正整數(shù)、還是包含負(fù)數(shù)會(huì)直接決定實(shí)現(xiàn)的復(fù)雜度第二B 不能為 0這是除法的基本前提實(shí)際寫代碼時(shí)必須處理第三所謂不使用除法和取模通常也包括不能調(diào)用庫(kù)函數(shù)里封裝好的除法比如某些語言里的divmod之類。把這三點(diǎn)想清楚后面的方案設(shè)計(jì)才有意義。這道題的核心價(jià)值在于它逼著你去理解除法到底是什么。除法的本質(zhì)其實(shí)是減法的一種加速形式——A 除以 B 的商就是從 A 里最多能減去多少個(gè) B。理解了這一點(diǎn)所有的優(yōu)化思路其實(shí)都是在回答同一個(gè)問題如何更快地?cái)?shù)出這個(gè)多少個(gè)。樸素減法是一個(gè)一個(gè)數(shù)太慢二進(jìn)制移位是一次數(shù)一大批快得多。這就是整篇文章的主線。2. 最樸素的減法循環(huán)能跑通但別高興太早2.1 減法思路的直覺來源先從最符合直覺的方案講起因?yàn)樗抢斫夂罄m(xù)所有優(yōu)化的地基。既然除法的本質(zhì)是從被除數(shù)里反復(fù)減去除數(shù)那最直接的做法就是用一個(gè)計(jì)數(shù)器記錄減了多少次每次從 A 里減去 B直到剩下的數(shù)小于 B 為止。這時(shí)候計(jì)數(shù)器的值就是商剩下的那個(gè)數(shù)就是余數(shù)。用生活化的類比來說這就像你有一堆糖果A 顆要平均分給若干個(gè)小朋友每個(gè)小朋友分 B 顆。你不知道能分給幾個(gè)小朋友于是一個(gè)一個(gè)地分給第一個(gè)小朋友 B 顆剩下的還夠不夠再分一份夠就繼續(xù)不夠就停。最后分出去的小朋友數(shù)量就是商手里剩下的糖果就是余數(shù)。這個(gè)類比雖然簡(jiǎn)單但它精確地對(duì)應(yīng)了減法循環(huán)的每一步。寫成代碼大概是這樣def div_subtract(a, b): if b 0: raise ValueError(除數(shù)不能為 0) quotient 0 # 處理同號(hào)/異號(hào)的情況這里先假設(shè)都是正數(shù) while a b: a - b quotient 1 remainder a return quotient, remainder這段代碼邏輯上完全正確對(duì)于 A17、B5 這種情況循環(huán)會(huì)執(zhí)行 3 次得到商 3、余數(shù) 2答案沒問題。很多初學(xué)者寫到這里就覺得搞定了但如果只停在這一步那這道題就白做了。2.2 時(shí)間復(fù)雜度是致命傷問題出在效率上。上面這個(gè)循環(huán)的執(zhí)行次數(shù)等于商的大小也就是大約 A/B 次。當(dāng) A 很大而 B 很小時(shí)這個(gè)次數(shù)會(huì)爆炸。舉個(gè)極端的例子A 2,000,000,00020 億B 1。這時(shí)候循環(huán)要執(zhí)行 20 億次哪怕每次循環(huán)只花 1 納秒總共也要 2 秒。而如果用普通的除法運(yùn)算這個(gè)過程是常數(shù)時(shí)間完成的幾乎瞬間出結(jié)果。我在自己的機(jī)器上實(shí)測(cè)過用 Python 跑這個(gè)減法循環(huán)當(dāng) A 是 10 的 8 次方、B 是 1 的時(shí)候耗時(shí)已經(jīng)肉眼可見地到了秒級(jí)而同樣的輸入用內(nèi)置除法耗時(shí)在微秒級(jí)別。這個(gè)差距不是優(yōu)化一下能彌補(bǔ)的而是算法復(fù)雜度層面的鴻溝——一個(gè)是 O(A/B)一個(gè)是 O(1)。提示面試?yán)锶绻粚懗鰷p法循環(huán)通常會(huì)被追問能不能優(yōu)化。這時(shí)候你要能立刻說出循環(huán)次數(shù)等于商最壞情況是 O(A/B)當(dāng) B 很小時(shí)會(huì)退化這句話本身就是加分項(xiàng)說明你有復(fù)雜度意識(shí)。2.3 減法方案里藏著的邊界坑即便不考慮效率減法方案在邊界處理上也有一堆細(xì)節(jié)。首先是負(fù)數(shù)如果 A 或 B 是負(fù)數(shù)while a b這個(gè)條件就不成立了。比如 A -17、B 5按數(shù)學(xué)定義商應(yīng)該是 -4、余數(shù)應(yīng)該是 3因?yàn)?-17 5 × (-4) 3但你的循環(huán)條件-17 5直接為假一次都不執(zhí)行結(jié)果全錯(cuò)。其次是余數(shù)的符號(hào)這個(gè)容易被忽略的問題。不同的語言、不同的數(shù)學(xué)約定對(duì)余數(shù)符號(hào)的處理是不一樣的。有的約定余數(shù)符號(hào)跟被除數(shù)一致截?cái)喑–、Java、Python 的//和%在正數(shù)下一致但負(fù)數(shù)下不同有的約定余數(shù)永遠(yuǎn)非負(fù)地板除法。這道題如果沒有明確約定你必須自己先定一個(gè)規(guī)則并在代碼里貫徹到底。我個(gè)人的建議是先把 A 和 B 都轉(zhuǎn)成正數(shù)處理記錄下符號(hào)最后再根據(jù)約定調(diào)整商和余數(shù)的符號(hào)這樣能把最復(fù)雜的符號(hào)邏輯隔離出來主循環(huán)只處理正數(shù)清爽很多。3. 二進(jìn)制長(zhǎng)除法把一個(gè)一個(gè)減升級(jí)成一批一批減3.1 核心洞察移位就是乘 2要真正優(yōu)化這道題必須借助二進(jìn)制。這里有一個(gè)關(guān)鍵事實(shí)在二進(jìn)制下左移一位等于乘以 2右移一位等于除以 2。這個(gè)性質(zhì)是后面所有優(yōu)化的基石。既然除法是減法的加速那我們能不能一次減去一大塊而不是一次只減一個(gè) B答案是能。思路是這樣的與其每次減 B不如先找到B 乘以 2 的多少次方仍然不超過 A。比如 A 100、B 3我們先看 3×26、3×412、3×824、3×1648、3×329696 不超過 100但 3×64192 超過了。于是我們知道商里至少有 32 這一份。先減去 96商加上 32剩下 4然后對(duì)剩下的 4 重復(fù)這個(gè)過程找到 3×13 不超過 4減去 3商加上 1剩下 1。最終商 32 1 33余數(shù) 1。驗(yàn)證一下33 × 3 1 100完全正確。這個(gè)過程的本質(zhì)就是二進(jìn)制長(zhǎng)除法和我們小學(xué)學(xué)的十進(jìn)制豎式除法是同一個(gè)道理只不過換成了二進(jìn)制。十進(jìn)制豎式里我們一位一位地試商二進(jìn)制里每一位只有 0 和 1 兩種可能試起來更簡(jiǎn)單。3.2 用移位實(shí)現(xiàn)找最大倍數(shù)上面那個(gè)找 B 乘以 2 的多少次方不超過 A的過程用移位實(shí)現(xiàn)非常自然。核心代碼長(zhǎng)這樣def div_binary(a, b): if b 0: raise ValueError(除數(shù)不能為 0) # 先統(tǒng)一轉(zhuǎn)成正數(shù)處理符號(hào)最后再補(bǔ) sign 1 if a 0: a -a sign -sign if b 0: b -b sign -sign quotient 0 # 從高位往低位試 for shift in range(31, -1, -1): # 檢查 b shift 是否不超過 a if (b shift) a: a - (b shift) quotient (1 shift) # 根據(jù)符號(hào)約定調(diào)整 if sign 0: quotient -quotient remainder a # 這里余數(shù)取非負(fù)約定 return quotient, remainder這段代碼的關(guān)鍵在于那個(gè)從 31 到 0 的循環(huán)。為什么是 31因?yàn)閷?duì)于 32 位整數(shù)來說商最大不會(huì)超過 2 的 31 次方考慮符號(hào)位所以從最高位開始試就夠了。每一輪我們檢查b shift也就是 b 乘以 2 的 shift 次方是否還小于等于當(dāng)前的 a如果是就把它減掉并在商的對(duì)應(yīng)二進(jìn)制位上置 1。3.3 為什么這個(gè)方案快得多復(fù)雜度上這個(gè)方案是 O(32)也就是常數(shù)級(jí)別對(duì)于固定位寬的整數(shù)。不管 A 是 100 還是 20 億循環(huán)次數(shù)都是固定的 32 次或者 64 次取決于整數(shù)位寬。這就把前面減法方案的 O(A/B) 直接降到了 O(位數(shù))是質(zhì)的飛躍。我用同樣的測(cè)試數(shù)據(jù)對(duì)比過A 10 的 8 次方、B 1 的情況下減法方案要跑上億次循環(huán)而二進(jìn)制長(zhǎng)除法只需要 32 次循環(huán)耗時(shí)從秒級(jí)降到微秒級(jí)。這個(gè)差距在真實(shí)系統(tǒng)里是決定性的——比如你在寫一個(gè)嵌入式程序CPU 主頻只有幾十兆一次除法如果耗時(shí)幾毫秒整個(gè)系統(tǒng)的實(shí)時(shí)性就崩了。注意b shift這個(gè)操作在 shift 很大時(shí)可能會(huì)溢出。比如 b 本身已經(jīng)接近整數(shù)上限再左移 31 位就直接溢出了結(jié)果變成負(fù)數(shù)比較就失效了。穩(wěn)妥的做法是先用一個(gè)循環(huán)把 b 左移到剛好不超過 a的最大位置或者用更寬的整數(shù)類型比如 Python 天然支持大整數(shù)但 C/Java 里要小心。這個(gè)坑我在 C 語言里踩過調(diào)試了半天才發(fā)現(xiàn)是溢出導(dǎo)致的比較錯(cuò)誤。3.4 一個(gè)更省事的變體先對(duì)齊最高位上面那個(gè)從 31 開始逐位試的寫法雖然正確但每一輪都要做一次移位和比較稍微有點(diǎn)浪費(fèi)。一個(gè)常見的優(yōu)化是先找到 b 需要左移多少位才能夠得著 a 的最高位然后從這個(gè)位置開始往下試。這樣能跳過前面一堆必然失敗的比較。def div_binary_v2(a, b): if b 0: raise ValueError(除數(shù)不能為 0) sign 1 if a 0: a -a sign -sign if b 0: b -b sign -sign # 找到最大的 shift使得 b shift a shift 0 while (b (shift 1)) a: shift 1 quotient 0 while shift 0: if (b shift) a: a - (b shift) quotient (1 shift) shift - 1 if sign 0: quotient -quotient return quotient, a這個(gè)版本和前面那個(gè)本質(zhì)一樣只是起點(diǎn)更聰明。實(shí)測(cè)下來對(duì)于 A 遠(yuǎn)大于 B 的情況它能少做十幾次無用的比較雖然提升幅度不大但在追求極致性能的場(chǎng)景里這種細(xì)節(jié)是值得摳的。4. 符號(hào)、溢出與邊界那些真正讓代碼翻車的地方4.1 負(fù)數(shù)處理先轉(zhuǎn)正再算最后補(bǔ)符號(hào)前面反復(fù)提到先轉(zhuǎn)正再算這里展開講講為什么。整數(shù)除法最麻煩的地方就是符號(hào)。如果主循環(huán)里同時(shí)處理正負(fù)號(hào)條件判斷會(huì)變得極其復(fù)雜容易出錯(cuò)。而如果把 A 和 B 都取絕對(duì)值主循環(huán)就只需要處理正數(shù)邏輯干凈得多。符號(hào)的處理可以推遲到最后商的符號(hào)由 A 和 B 的符號(hào)共同決定同號(hào)為正、異號(hào)為負(fù)余數(shù)的符號(hào)則取決于你采用的約定。這里有個(gè)細(xì)節(jié)要注意取絕對(duì)值的時(shí)候如果 A 是最小的負(fù)數(shù)比如 32 位有符號(hào)整數(shù)的 -2147483648取絕對(duì)值會(huì)溢出因?yàn)檎龜?shù)最大只能表示到 2147483647。這個(gè)坑非常隱蔽很多標(biāo)準(zhǔn)庫(kù)的abs函數(shù)在這個(gè)輸入上都會(huì)出問題。穩(wěn)妥的做法是先把 A 和 B 轉(zhuǎn)成無符號(hào)類型或者更寬的類型再處理或者用 Python 這種天然支持大整數(shù)的語言來規(guī)避。4.2 余數(shù)符號(hào)的兩種約定關(guān)于余數(shù)的符號(hào)業(yè)界主要有兩種約定理解它們的區(qū)別很重要約定類型余數(shù)符號(hào)例子A-17, B5常見語言截?cái)喑ㄅc被除數(shù)相同商 -3余 -2C、Java、Go地板除法永遠(yuǎn)非負(fù)商 -4余 3Python//和%兩種約定都自洽區(qū)別在于商向零取整還是商向下取整。截?cái)喑ㄊ窍蛄闳≌匕宄ㄊ窍蛳氯≌?。這道題如果沒有明確要求你需要自己選一種并說明。我個(gè)人的習(xí)慣是默認(rèn)采用截?cái)喑ㄒ驗(yàn)樗痛蠖鄶?shù)系統(tǒng)級(jí)語言的默認(rèn)行為一致遷移成本低。但如果題目來自 Python 背景那可能期望的是地板除法這時(shí)候就要在最后調(diào)整如果余數(shù)為負(fù)就把余數(shù)加上 |B|同時(shí)商減 1。4.3 除零和特殊輸入的防御B 為 0 是必須攔截的這個(gè)不用多說。但還有一些邊界值得注意A 為 0 時(shí)商和余數(shù)都是 0主循環(huán)一次都不執(zhí)行結(jié)果自然正確不用特殊處理。B 為 1 時(shí)商就是 A余數(shù)是 0二進(jìn)制長(zhǎng)除法也能正確處理。B 為 -1 時(shí)如果 A 是最小負(fù)數(shù)商又會(huì)溢出這個(gè)和前面取絕對(duì)值溢出是同一類問題。我在實(shí)際項(xiàng)目里總結(jié)出一條經(jīng)驗(yàn)凡是涉及整數(shù)除法的代碼都要在函數(shù)入口處做一次完整的邊界檢查把 B0、A 或 B 為極值這些情況提前攔掉主邏輯只處理正常范圍的輸入。這樣代碼的可讀性和可維護(hù)性都會(huì)好很多出 bug 的時(shí)候也容易定位。5. 不同實(shí)現(xiàn)方案的橫向?qū)Ρ扰c選型建議5.1 三種方案的性能與適用場(chǎng)景把前面講的方案整理成一張表方便你根據(jù)場(chǎng)景選型方案時(shí)間復(fù)雜度代碼復(fù)雜度適用場(chǎng)景減法循環(huán)O(A/B)極低教學(xué)演示、A/B 很小的場(chǎng)景二進(jìn)制長(zhǎng)除法逐位試O(位數(shù))中等通用場(chǎng)景、面試答題二進(jìn)制長(zhǎng)除法先對(duì)齊O(位數(shù))中等偏高追求性能的底層實(shí)現(xiàn)從工程角度看二進(jìn)制長(zhǎng)除法是性價(jià)比最高的選擇復(fù)雜度是常數(shù)級(jí)代碼量也不大邏輯清晰可驗(yàn)證。減法循環(huán)雖然簡(jiǎn)單但只適合用來講清楚除法是減法這個(gè)直覺真拿去做生產(chǎn)代碼是要出事的。5.2 語言層面的差異不同語言實(shí)現(xiàn)這道題時(shí)有幾個(gè)點(diǎn)需要特別注意。Python 天然支持任意精度整數(shù)不用擔(dān)心溢出寫起來最省心但要注意 Python 的//是地板除法和 C 系的截?cái)喑ú灰粯?。C 和 Java 里整數(shù)位寬固定移位溢出是真實(shí)存在的風(fēng)險(xiǎn)必須用更寬的類型或者提前判斷。JavaScript 的位運(yùn)算會(huì)把操作數(shù)轉(zhuǎn)成 32 位有符號(hào)整數(shù)超過范圍會(huì)出問題處理大數(shù)時(shí)得用BigInt。我在用 JavaScript 實(shí)現(xiàn)的時(shí)候就被這個(gè)坑絆過A 和 B 稍微大一點(diǎn)位運(yùn)算的結(jié)果就莫名其妙變成負(fù)數(shù)查了半天才發(fā)現(xiàn)是 32 位截?cái)鄬?dǎo)致的。后來改用BigInt才正常。所以選語言的時(shí)候一定要先搞清楚它的整數(shù)模型。5.3 面試場(chǎng)景下的答題策略如果這道題出現(xiàn)在面試?yán)镂业慕ㄗh是分三步走。第一步先說出最樸素的減法思路表明你理解了除法的本質(zhì)第二步主動(dòng)指出減法方案的性能問題引出二進(jìn)制長(zhǎng)除法的優(yōu)化第三步寫出二進(jìn)制長(zhǎng)除法的代碼并主動(dòng)討論符號(hào)、溢出、除零這些邊界。這樣一套下來面試官能看到你的思維層次比一上來就寫最優(yōu)解但講不清為什么要有說服力得多。提示面試時(shí)如果時(shí)間緊張可以先把正數(shù)版本的二進(jìn)制長(zhǎng)除法寫對(duì)然后口頭說明負(fù)數(shù)我會(huì)先取絕對(duì)值、最后補(bǔ)符號(hào)除零會(huì)在入口攔截這樣既保證了代碼正確性又展示了邊界意識(shí)。6. 我在實(shí)際動(dòng)手過程中踩過的幾個(gè)坑6.1 移位溢出最隱蔽的 bug前面提過移位溢出這里再?gòu)?qiáng)調(diào)一次因?yàn)樗娴奶菀撞攘?。?C 語言里b shift當(dāng) shift 接近 31 時(shí)如果 b 不是 1結(jié)果幾乎必然溢出。溢出后的值是未定義行為undefined behavior可能變成負(fù)數(shù)、可能變成 0取決于編譯器和平臺(tái)。我第一次寫的時(shí)候沒注意測(cè)試用例里 A 和 B 都比較小跑得好好的一換成大數(shù)就出錯(cuò)而且錯(cuò)誤結(jié)果毫無規(guī)律排查了很久。解決辦法有兩個(gè)一是用long long或者unsigned類型來承載移位結(jié)果擴(kuò)大表示范圍二是在移位前先判斷b是否已經(jīng)大于a shift用右移代替左移來避免溢出。第二種更優(yōu)雅但可讀性稍差。我現(xiàn)在的習(xí)慣是能用更寬類型就用更寬類型簡(jiǎn)單直接不容易出錯(cuò)。6.2 循環(huán)邊界差一錯(cuò)誤的重災(zāi)區(qū)二進(jìn)制長(zhǎng)除法里循環(huán)的起止位置很容易寫錯(cuò)。比如從 31 開始還是從 30 開始到 0 結(jié)束還是到 1 結(jié)束這些差一錯(cuò)誤off-by-one會(huì)導(dǎo)致結(jié)果差一個(gè) 2 的冪次非常隱蔽。我的經(jīng)驗(yàn)是先用小數(shù)據(jù)手工驗(yàn)證循環(huán)邊界比如 A5、B2手工推一遍每一位的情況確認(rèn)循環(huán)覆蓋了所有可能的位。確認(rèn)無誤后再跑大數(shù)據(jù)測(cè)試。6.3 符號(hào)調(diào)整的時(shí)機(jī)還有一個(gè)坑是符號(hào)調(diào)整的時(shí)機(jī)。我一開始把符號(hào)調(diào)整寫在循環(huán)里面每減一次就判斷一次符號(hào)代碼又亂又慢。后來改成循環(huán)里只處理正數(shù)循環(huán)結(jié)束后統(tǒng)一調(diào)整代碼立刻清爽了。這個(gè)經(jīng)驗(yàn)其實(shí)很通用把變化的部分和不變的部分分開處理主循環(huán)只做最核心的減法符號(hào)、邊界這些外圍邏輯放到循環(huán)外是寫出干凈代碼的關(guān)鍵。7. 從這道題延伸出去位運(yùn)算還能做什么這道題表面上是在考除法實(shí)際上是在考位運(yùn)算的運(yùn)用能力。把這道題吃透之后你會(huì)發(fā)現(xiàn)位運(yùn)算在很多地方都能派上用場(chǎng)。比如判斷一個(gè)數(shù)是不是 2 的冪可以用n (n - 1) 0求一個(gè)數(shù)的二進(jìn)制里有多少個(gè) 1可以用n (n - 1)反復(fù)消掉最低位的 1交換兩個(gè)數(shù)不用臨時(shí)變量可以用異或三次。這些技巧和二進(jìn)制長(zhǎng)除法是同一套思維方式的產(chǎn)物——把整數(shù)看成二進(jìn)制位的組合而不是一個(gè)抽象的數(shù)量。我個(gè)人覺得這道題最大的收獲不是學(xué)會(huì)了怎么寫除法而是養(yǎng)成了遇到運(yùn)算先想想二進(jìn)制層面發(fā)生了什么的習(xí)慣。這個(gè)習(xí)慣一旦建立起來很多看似復(fù)雜的問題都會(huì)變得清晰。比如你以后再看到不用乘法實(shí)現(xiàn)乘法不用加法實(shí)現(xiàn)加法這類題思路其實(shí)是相通的都是把基本運(yùn)算拆解成位操作再用循環(huán)或遞歸組合起來。最后分享一個(gè)我自己的練習(xí)方法把這道題的每種實(shí)現(xiàn)都手寫一遍然后用隨機(jī)數(shù)據(jù)和大數(shù)據(jù)分別測(cè)試對(duì)比結(jié)果和性能。手寫能幫你記住細(xì)節(jié)測(cè)試能幫你發(fā)現(xiàn)邊界問題對(duì)比能幫你建立性能直覺。這三件事做下來這道題才算真正變成你自己的東西。