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