1. 進(jìn)制轉(zhuǎn)換到底在考什么1.1 從一道題看進(jìn)制轉(zhuǎn)換的本質(zhì)藍(lán)橋系統(tǒng)003進(jìn)制轉(zhuǎn)換這個標(biāo)題乍一看像是某個在線評測系統(tǒng)里的第三道練習(xí)題。很多剛接觸編程競賽或者算法訓(xùn)練的朋友第一次看到進(jìn)制轉(zhuǎn)換的題目第一反應(yīng)往往是這不就是除來除去嗎然后隨手寫個循環(huán)取余就交上去了。但真正做過幾道進(jìn)制轉(zhuǎn)換題的人都知道這個看似簡單的知識點坑多得能讓你懷疑人生。我先把這個題目的典型場景說清楚。進(jìn)制轉(zhuǎn)換類題目通常要求你實現(xiàn)以下幾種操作中的一種或多種十進(jìn)制轉(zhuǎn)任意進(jìn)制、任意進(jìn)制轉(zhuǎn)十進(jìn)制、任意進(jìn)制之間的互轉(zhuǎn)甚至還有負(fù)進(jìn)制轉(zhuǎn)換這種進(jìn)階玩法。輸入輸出格式也五花八門有的要求返回字符串有的要求處理大數(shù)有的還要求處理小數(shù)部分。藍(lán)橋系統(tǒng)里的這道003號題從編號來看應(yīng)該是入門級別的第三題大概率是要求實現(xiàn)十進(jìn)制到其他進(jìn)制的基礎(chǔ)轉(zhuǎn)換或者二進(jìn)制與十進(jìn)制之間的互轉(zhuǎn)。為什么進(jìn)制轉(zhuǎn)換這么重要因為它是計算機(jī)科學(xué)的地基。計算機(jī)底層全是二進(jìn)制內(nèi)存地址常用十六進(jìn)制表示權(quán)限管理用八進(jìn)制而我們?nèi)祟惲?xí)慣十進(jìn)制。你在寫代碼的時候只要涉及到數(shù)據(jù)存儲、網(wǎng)絡(luò)傳輸、加密解密、位運算優(yōu)化進(jìn)制轉(zhuǎn)換就無處不在。所以這道題雖然編號靠前但它是后面很多高級題目的前置技能。1.2 這道題適合誰來練如果你剛開始學(xué)編程這道題是檢驗?zāi)阊h(huán)、取模、字符串操作是否熟練的試金石。如果你已經(jīng)有一定基礎(chǔ)這道題可以幫你重新審視邊界條件處理、大數(shù)運算、負(fù)數(shù)處理這些容易被忽略的細(xì)節(jié)。我?guī)н^不少剛?cè)腴T的朋友他們普遍反映進(jìn)制轉(zhuǎn)換一看就會一寫就廢原因就在于沒有系統(tǒng)性地梳理過各種情況。這篇文章我會從題目拆解、算法選型、代碼實現(xiàn)、邊界處理、性能優(yōu)化幾個維度把進(jìn)制轉(zhuǎn)換這件事徹底講透。你跟著走一遍以后遇到任何進(jìn)制轉(zhuǎn)換的變種題都能有一套清晰的解題框架。2. 進(jìn)制轉(zhuǎn)換的核心原理拆解2.1 位權(quán)展開任意進(jìn)制轉(zhuǎn)十進(jìn)制的萬能公式任意進(jìn)制轉(zhuǎn)十進(jìn)制核心就一句話按位權(quán)展開求和。什么意思呢比如一個R進(jìn)制的數(shù)從右往左數(shù)第i位i從0開始上的數(shù)字是d那么這一位代表的實際值就是d乘以R的i次方。把所有位的值加起來就是對應(yīng)的十進(jìn)制數(shù)。舉個例子二進(jìn)制數(shù)1101轉(zhuǎn)十進(jìn)制從右往左第0位是1代表1乘以2的0次方等于1第1位是0代表0乘以2的1次方等于0第2位是1代表1乘以2的2次方等于4第3位是1代表1乘以2的3次方等于8。加起來104813。這就是位權(quán)展開。這個原理適用于任何進(jìn)制。八進(jìn)制數(shù)17轉(zhuǎn)十進(jìn)制7乘以8的0次方等于71乘以8的1次方等于8加起來15。十六進(jìn)制數(shù)1F轉(zhuǎn)十進(jìn)制F代表1515乘以16的0次方等于151乘以16的1次方等于16加起來31。用代碼實現(xiàn)的時候有兩種思路。第一種是從右往左遍歷字符串維護(hù)一個power變量表示當(dāng)前位的權(quán)值每次乘R。第二種是從左往右遍歷用result result * R digit的累加方式。第二種更簡潔也更符合我們手算的習(xí)慣。我個人的經(jīng)驗是從左往右的寫法不容易出錯因為它不需要額外維護(hù)權(quán)值變量也不需要考慮字符串反轉(zhuǎn)。注意處理十六進(jìn)制的時候字母A到F需要映射成10到15。很多人寫代碼時忘記處理大小寫題目如果輸入小寫a你的代碼只判斷了大寫A就會直接報錯。穩(wěn)妥的做法是統(tǒng)一轉(zhuǎn)成大寫或者小寫再判斷。2.2 除基取余十進(jìn)制轉(zhuǎn)任意進(jìn)制的標(biāo)準(zhǔn)解法十進(jìn)制轉(zhuǎn)R進(jìn)制標(biāo)準(zhǔn)做法是除基取余逆序排列。具體操作是用十進(jìn)制數(shù)不斷除以R每次記錄余數(shù)直到商為0然后把所有余數(shù)從后往前讀出來就是R進(jìn)制表示。比如十進(jìn)制13轉(zhuǎn)二進(jìn)制13除以2商6余16除以2商3余03除以2商1余11除以2商0余1。余數(shù)依次是1、0、1、1逆序排列就是1101。和上面位權(quán)展開的結(jié)果對上了。這個算法的正確性可以用數(shù)學(xué)歸納法證明但作為寫代碼的人你只需要記住操作步驟就行。實現(xiàn)的時候用while循環(huán)條件是n 0每次n除以R余數(shù)push到一個數(shù)組或者字符串里最后反轉(zhuǎn)。這里有個細(xì)節(jié)如果原始數(shù)字是0循環(huán)一次都不會執(zhí)行結(jié)果會是空字符串。所以必須特判0的情況直接返回0。這個坑我見過太多人踩了包括我自己早期寫代碼的時候測試用例只測了正數(shù)一提交就掛在0這個用例上。2.3 任意進(jìn)制互轉(zhuǎn)先過十進(jìn)制這道橋如果題目要求你把一個R進(jìn)制數(shù)轉(zhuǎn)成S進(jìn)制數(shù)最穩(wěn)妥的做法是先把R進(jìn)制轉(zhuǎn)成十進(jìn)制再把十進(jìn)制轉(zhuǎn)成S進(jìn)制。雖然理論上可以一步到位但分兩步走邏輯清晰不容易出錯而且代碼可以復(fù)用上面兩個函數(shù)。有人可能會問這樣會不會效率低對于競賽題目來說數(shù)據(jù)范圍通常不會大到需要你優(yōu)化這一步。除非題目明確說輸入長度達(dá)到百萬級別否則分兩步走完全夠用。而且分兩步走的代碼可讀性更好調(diào)試也方便。我在實際做題時除非有明確的性能要求否則一律采用這種橋接法。3. 代碼實現(xiàn)與關(guān)鍵細(xì)節(jié)3.1 任意進(jìn)制轉(zhuǎn)十進(jìn)制的代碼實現(xiàn)先看核心代碼。假設(shè)輸入是一個字符串s和一個整數(shù)base表示s是base進(jìn)制的數(shù)要求返回十進(jìn)制整數(shù)。def to_decimal(s, base): result 0 for ch in s: if 0 ch 9: digit ord(ch) - ord(0) elif A ch F: digit ord(ch) - ord(A) 10 elif a ch f: digit ord(ch) - ord(a) 10 else: raise ValueError(非法字符) result result * base digit return result這段代碼從左往右遍歷每次把之前的結(jié)果乘以base再加上當(dāng)前位的值。比如處理1F十六進(jìn)制第一步result01611第二步result1161531。邏輯非常直觀。這里用ord函數(shù)做字符到數(shù)字的轉(zhuǎn)換比用字典或者if-else鏈更高效。當(dāng)然如果你追求極致的可讀性也可以用一個字典做映射但字典的查找開銷比ord大。對于競賽題目ord是更好的選擇。提示如果題目保證輸入只有數(shù)字和大寫字母你可以省略小寫字母的判斷減少分支。但穩(wěn)妥起見我建議把大小寫都處理了多寫兩行代碼換來的是更強(qiáng)的魯棒性。3.2 十進(jìn)制轉(zhuǎn)任意進(jìn)制的代碼實現(xiàn)def from_decimal(n, base): if n 0: return 0 digits 0123456789ABCDEF result [] while n 0: result.append(digits[n % base]) n // base return .join(reversed(result))這段代碼有幾個關(guān)鍵點。第一特判0直接返回0。第二用digits字符串做余數(shù)到字符的映射比用if-else判斷余數(shù)范圍更簡潔。第三用列表收集字符最后反轉(zhuǎn)拼接比字符串拼接效率高因為Python的字符串是不可變的每次拼接都會創(chuàng)建新對象。如果你要支持更高的進(jìn)制比如36進(jìn)制只需要把digits字符串?dāng)U展到0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ就行。這個技巧在處理短鏈接生成、邀請碼生成之類的場景時特別有用。3.3 負(fù)數(shù)與大數(shù)怎么處理負(fù)數(shù)處理是進(jìn)制轉(zhuǎn)換題目的常見變種。對于十進(jìn)制轉(zhuǎn)R進(jìn)制如果n是負(fù)數(shù)通常的做法是先記錄符號把n取絕對值做轉(zhuǎn)換最后在結(jié)果前面加上負(fù)號。但要注意有些題目要求用補(bǔ)碼表示負(fù)數(shù)那就是另一套邏輯了。大數(shù)處理是另一個坑。如果輸入的數(shù)字超過64位整數(shù)范圍你就不能用int類型直接存了。Python的好處是int是任意精度的天然支持大數(shù)。但如果你用C或者Java就需要用字符串模擬除法或者用大數(shù)庫。藍(lán)橋系統(tǒng)的題目如果涉及大數(shù)通常會明確說明數(shù)據(jù)范圍你看到長度不超過1000之類的描述就要警惕了。我在實際做題時遇到大數(shù)進(jìn)制轉(zhuǎn)換一般會用Python寫因為省去了手寫大數(shù)運算的麻煩。如果必須用C我會把除法過程用字符串模擬每次從高位到低位逐位處理維護(hù)一個余數(shù)變量。4. 常見錯誤與排查實錄4.1 邊界條件速查表問題現(xiàn)象可能原因排查方法解決方案輸入0時輸出空字符串循環(huán)條件寫成n00不進(jìn)入循環(huán)單獨測試n0特判0直接返回0十六進(jìn)制小寫字母報錯只判斷了大寫A-F測試輸入a增加小寫字母判斷或統(tǒng)一轉(zhuǎn)大寫結(jié)果順序反了余數(shù)沒有逆序手算對比用reversed或從后往前讀大數(shù)溢出用了固定長度整數(shù)類型檢查數(shù)據(jù)范圍用Python或字符串模擬負(fù)數(shù)結(jié)果不對沒有處理符號測試負(fù)數(shù)輸入記錄符號取絕對值轉(zhuǎn)換后加回非法字符未報錯沒有校驗輸入輸入G測試增加字符合法性檢查這張表是我自己踩坑總結(jié)出來的基本上覆蓋了進(jìn)制轉(zhuǎn)換題目90%的錯誤場景。你可以把它當(dāng)成一個檢查清單提交代碼前逐項過一遍。4.2 調(diào)試技巧與驗證方法進(jìn)制轉(zhuǎn)換題目的調(diào)試最有效的方法是手算對比。你隨便選幾個數(shù)手算出結(jié)果然后和程序輸出對比。比如十進(jìn)制255轉(zhuǎn)十六進(jìn)制手算應(yīng)該是FF程序輸出如果不是FF那就說明有問題。另一個技巧是用Python的內(nèi)置函數(shù)做交叉驗證。Python的int(s, base)可以把任意進(jìn)制字符串轉(zhuǎn)十進(jìn)制hex()、oct()、bin()可以轉(zhuǎn)十六進(jìn)制、八進(jìn)制、二進(jìn)制。你可以用這些內(nèi)置函數(shù)驗證自己的實現(xiàn)是否正確。但注意比賽的時候不能用內(nèi)置函數(shù)直接交答案那只適合用來調(diào)試。還有一個容易被忽略的點輸入可能有前導(dǎo)零。比如0011作為二進(jìn)制輸入你的代碼能不能正確處理從左往右的累加方式天然支持前導(dǎo)零因為0乘以base還是0不影響結(jié)果。但如果你用其他方式實現(xiàn)就要注意這個問題。注意有些題目會給出帶有前綴的輸入比如0x1F表示十六進(jìn)制0b101表示二進(jìn)制。如果你的代碼沒有處理前綴就會把x或者b當(dāng)成非法字符。遇到這種題目先去掉前綴再處理。5. 進(jìn)階玩法與性能優(yōu)化5.1 短除法與查表法的取舍對于十進(jìn)制轉(zhuǎn)二進(jìn)制這種特例有一種更快的做法叫查表法。因為二進(jìn)制只有0和1你可以預(yù)先算好2的各個冪次然后用減法代替除法。比如轉(zhuǎn)13先找到小于等于13的最大2的冪是813-85記錄一個1再找45-41記錄一個1再找21小于2記錄一個0再找11-10記錄一個1。結(jié)果是1101。查表法在轉(zhuǎn)換大數(shù)時比除法快因為減法比除法開銷小。但它的缺點是只適用于二進(jìn)制而且需要預(yù)先計算冪次表。對于通用進(jìn)制轉(zhuǎn)換除基取余還是最通用的方法。我在實際項目中如果只需要轉(zhuǎn)二進(jìn)制會用查表法如果需要轉(zhuǎn)多種進(jìn)制就用統(tǒng)一的除基取余。5.2 位運算加速二進(jìn)制轉(zhuǎn)換如果你用C或者Java二進(jìn)制轉(zhuǎn)換可以用位運算加速。比如取n的二進(jìn)制表示可以用n 1取最低位然后n 1右移一位循環(huán)直到n為0。這比除以2取余快得多因為位運算直接操作內(nèi)存不需要經(jīng)過除法器。這個技巧在處理位圖、狀態(tài)壓縮、權(quán)限系統(tǒng)的時候特別有用。比如一個32位的整數(shù)表示32個開關(guān)的狀態(tài)你要把它轉(zhuǎn)成二進(jìn)制字符串用位運算就是最優(yōu)解。5.3 進(jìn)制轉(zhuǎn)換在實際項目中的應(yīng)用進(jìn)制轉(zhuǎn)換不只是競賽題目它在實際開發(fā)中隨處可見。比如顏色值#FF5733就是十六進(jìn)制的RGB表示你需要把它轉(zhuǎn)成十進(jìn)制才能傳給圖形庫。比如Unix權(quán)限755是八進(jìn)制表示你需要理解每一位的含義。比如Base64編碼本質(zhì)上是把二進(jìn)制數(shù)據(jù)轉(zhuǎn)成64進(jìn)制字符串方便在網(wǎng)絡(luò)中傳輸。我之前做過一個短鏈接生成的項目就是把自增ID轉(zhuǎn)成62進(jìn)制0-9a-zA-Z這樣ID1000000轉(zhuǎn)成62進(jìn)制只有4位大大縮短了URL長度。這個思路你也可以用在邀請碼、訂單號、優(yōu)惠券碼的生成上。6. 從這道題延伸出的學(xué)習(xí)路徑進(jìn)制轉(zhuǎn)換是算法入門的第一道坎過了這道坎你可以順著往下學(xué)幾個方向。第一個方向是位運算包括與或非、異或、移位這些在狀態(tài)壓縮、哈希、加密算法里大量使用。第二個方向是大數(shù)運算包括大數(shù)加減乘除、大數(shù)進(jìn)制轉(zhuǎn)換這是處理高精度計算的基礎(chǔ)。第三個方向是編碼與壓縮包括Base64、哈夫曼編碼、游程編碼這些本質(zhì)上都是進(jìn)制轉(zhuǎn)換的變種。我的建議是先把這道003題徹底吃透做到不看題解能獨立寫出任意進(jìn)制互轉(zhuǎn)的代碼并且能處理負(fù)數(shù)、大數(shù)、前導(dǎo)零、非法字符這些邊界情況。然后去找?guī)椎雷兎N題練手比如負(fù)進(jìn)制轉(zhuǎn)換、小數(shù)進(jìn)制轉(zhuǎn)換、羅馬數(shù)字轉(zhuǎn)換。練完之后你對進(jìn)制這件事的理解就會上一個臺階。最后分享一個我個人的習(xí)慣每次寫完進(jìn)制轉(zhuǎn)換的代碼我都會用隨機(jī)數(shù)生成器造一批測試數(shù)據(jù)然后用Python內(nèi)置函數(shù)做交叉驗證。這個方法幫我抓出了無數(shù)個邊界bug比手動構(gòu)造測試用例高效得多。你也可以試試寫一個小腳本隨機(jī)生成進(jìn)制和數(shù)字對比自己的實現(xiàn)和內(nèi)置函數(shù)的結(jié)果跑個幾萬次如果全部通過那這道題基本就穩(wěn)了。