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