最近在做支付相關(guān)的回調(diào)校驗(yàn)對(duì)接方返回的流水號(hào)里有一段需要反轉(zhuǎn)后參與驗(yàn)簽。我隨手寫了個(gè)數(shù)字反轉(zhuǎn)的函數(shù)測(cè)了幾個(gè)用例看著沒問題結(jié)果真數(shù)據(jù)一跑數(shù)字稍微大一點(diǎn)直接溢出變成負(fù)值簽名自然也對(duì)不上。排查了半天最后發(fā)現(xiàn)不是算法寫錯(cuò)而是忽略了反轉(zhuǎn)后數(shù)值的類型邊界。這個(gè)場(chǎng)景讓我意識(shí)到數(shù)字反轉(zhuǎn)這種看起來入門到不能再入門的題目其實(shí)藏著不少工程上的坑。不管你是剛接觸編程準(zhǔn)備筆試還是已經(jīng)寫了幾年業(yè)務(wù)代碼偶爾會(huì)碰到數(shù)據(jù)格式轉(zhuǎn)換這篇內(nèi)容都適合你——我會(huì)從數(shù)值邊界、實(shí)現(xiàn)路線、溢出防護(hù)和工程擴(kuò)展幾個(gè)角度把數(shù)字反轉(zhuǎn)這個(gè)主題徹底講透。1. 數(shù)字反轉(zhuǎn)的第一道坎邊界條件比算法本身更重要1.1 面試?yán)镒畛Ｒ姷摹凹偻ㄟ^”案例很多人在做數(shù)字反轉(zhuǎn)時(shí)會(huì)先寫一個(gè)“看起來正確”的版本把數(shù)字轉(zhuǎn)成字符串反轉(zhuǎn)字符串再轉(zhuǎn)回?cái)?shù)字。比如def reverse_number(n): sign -1 if n 0 else 1 n abs(n) reversed_str str(n)[::-1] return sign * int(reversed_str)這個(gè)版本在輸入為 123 時(shí)返回 321輸入為 -456 時(shí)返回 -654看起來挺對(duì)。但你要是在力扣或面試現(xiàn)場(chǎng)跑一下邊界用例比如 2147483647在某些語言里就會(huì)得到意想不到的結(jié)果。問題出在哪當(dāng)輸入是 2147483647Int32 最大值反轉(zhuǎn)后是 7463847412這個(gè)數(shù)字已經(jīng)遠(yuǎn)超出 Int32 能表示的范圍。在像 Java、C#、C 這種有固定整數(shù)類型的語言里它會(huì)被截?cái)嗷蛘邎?bào)錯(cuò)在 JavaScript 里超過安全整數(shù)范圍后數(shù)值精度會(huì)丟失。如果代碼不做顯式檢查這一層風(fēng)險(xiǎn)很容易被忽略。所以數(shù)字反轉(zhuǎn)這道題真正考察的不是你會(huì)不會(huì)用字符串反轉(zhuǎn) API而是你知不知道整數(shù)在計(jì)算機(jī)內(nèi)存里是有邊界的以及如何在這種邊界約束下保持結(jié)果正確。1.2 邊界情況的完整清單我梳理了數(shù)字反轉(zhuǎn)必須考慮的幾類邊界輸入這些我在實(shí)際測(cè)試中反復(fù)踩過輸入類型示例輸入反轉(zhuǎn)結(jié)果說明正數(shù)普通1234554321基礎(chǔ)場(chǎng)景負(fù)數(shù)-123-321負(fù)號(hào)保留只反轉(zhuǎn)數(shù)字部分尾隨零120021反轉(zhuǎn)后高位的零要舍棄中間含零1000110001零位于中間則正常保留最小負(fù)數(shù)-2147483648溢出絕對(duì)值反轉(zhuǎn)后遠(yuǎn)超上限最大正數(shù)2147483647溢出反轉(zhuǎn)后 7463847412超界個(gè)位數(shù)77反轉(zhuǎn)后不變尾隨零這個(gè)點(diǎn)最容易出問題比如 1200 反轉(zhuǎn)以后應(yīng)該是 21不是 0021。字符串反轉(zhuǎn)方案天然處理了這一點(diǎn)因?yàn)?int(0021) 會(huì)解析成 21但如果你的實(shí)現(xiàn)里直接把字符數(shù)組拼回字符串然后返回字符串類型那就可能會(huì)把 0021 給返回出去導(dǎo)致后續(xù)流程出錯(cuò)。1.3 為什么這些邊界在真實(shí)業(yè)務(wù)中會(huì)突然冒出來有人可能會(huì)說我的業(yè)務(wù)數(shù)字都很小不會(huì)碰到這么極端的輸入。這話我當(dāng)年也信過后來被坑了。有一次做數(shù)據(jù)遷移存量數(shù)據(jù)里的某張表用了一個(gè)短整型字段存序號(hào)遷移到新系統(tǒng)時(shí)字段類型變成了長(zhǎng)整型。有一個(gè)較真的下游系統(tǒng)要求反轉(zhuǎn)序號(hào)再做奇偶判斷結(jié)果有一個(gè)序號(hào)的末幾位恰好是零反轉(zhuǎn)后位數(shù)直接少了幾位下游針對(duì)位數(shù)的校驗(yàn)就報(bào)警了。這類問題不是算法邏輯問題而是對(duì)輸入域的假設(shè)過于樂觀。所以設(shè)計(jì)數(shù)字反轉(zhuǎn)函數(shù)或工具時(shí)至少要在入口處明確聲明支持的范圍是多少、溢出的行為是拋異常還是返回特殊值、是否接受前導(dǎo)零輸入。這些決策會(huì)直接影響復(fù)用這個(gè)函數(shù)的所有調(diào)用方。2. 兩種實(shí)現(xiàn)路線對(duì)比數(shù)學(xué)法為什么在多數(shù)場(chǎng)景下更可靠2.1 字符串反轉(zhuǎn)方案的適用場(chǎng)景與隱藏開銷字符串方案的思路很直觀代碼也短public int reverse(int x) { String s String.valueOf(x); String reversed new StringBuilder(s).reverse().toString(); if (reversed.endsWith(-)) { reversed - reversed.substring(0, reversed.length() - 1); } return Integer.parseInt(reversed); }代碼是很短但它有幾個(gè)隱藏問題第一字符串是不可變對(duì)象反復(fù)拼接和遍歷會(huì)帶來額外的內(nèi)存分配與拷貝開銷第二語言特性會(huì)介入進(jìn)來——Java 里Integer.parseInt遇到超范圍字符串會(huì)拋NumberFormatException這個(gè)異常得靠外部 try-catch 捕獲才能轉(zhuǎn)換成溢出判斷第三負(fù)號(hào)反轉(zhuǎn)后的位置需要單獨(dú)處理容易出錯(cuò)。字符串方案并不是一無是處。如果你的目標(biāo)是處理任意長(zhǎng)度的數(shù)字比如 Python 里的超大整數(shù)或者你反轉(zhuǎn)的不是數(shù)值而是“數(shù)字字符串”那字符串方案就是對(duì)的。比如處理短信驗(yàn)證碼里的逆序數(shù)字串、或者反轉(zhuǎn)訂單號(hào)的前綴這時(shí)候語義本來就是文本而非數(shù)值強(qiáng)行走數(shù)值方案反而繞遠(yuǎn)。2.2 數(shù)學(xué)法的核心邏輯逐位彈出與推入數(shù)學(xué)法的邏輯更適合描述為“逐位彈出再推入”每次取原數(shù)字的最低位取余把它推入新數(shù)字的最高位原新數(shù)乘 10 再加該位然后原數(shù)字除以 10 丟掉這一位。偽代碼是這樣while (x ! 0) { 位 x % 10 結(jié)果 結(jié)果 * 10 位 x x / 10 }寫成 Java 版本public int reverse(int x) { int result 0; while (x ! 0) { int digit x % 10; // 溢出檢查見下一節(jié) result result * 10 digit; x / 10; } return result; }這個(gè)方案的復(fù)雜度是 O(log10(n))也就是按位數(shù)循環(huán)。對(duì)于 Int32 范圍來說最多循環(huán) 10 次幾乎可以忽略不計(jì)。它不依賴任何字符串庫函數(shù)也不用管負(fù)號(hào)因?yàn)?Java、C 里負(fù)整數(shù)取余正負(fù)號(hào)和被除數(shù)保持一致-123 % 10 得到的是 -3乘加后結(jié)果自然就是負(fù)數(shù)前綴這部分語義非常干凈。2.3 為什么不直接推薦 BigInt 或高精度類型很多語言提供高精度整數(shù)類型比如 Python 的 int 無限長(zhǎng)、Java 的 BigInteger、JavaScript 的 BigInt。用高精度類型做反轉(zhuǎn)從結(jié)果正確性上當(dāng)然沒問題def reverse_bigint(n): sign -1 if n 0 else 1 return sign * int(str(abs(n))[::-1])但工程上還要考慮下游和邊界約束。如果調(diào)用方定義接口返回的是 Int32 或 Long那你用高精度算出來還得再轉(zhuǎn)回去轉(zhuǎn)回去的時(shí)候溢出問題照樣回來。如果我寫一個(gè)通用工具函數(shù)我傾向先明確接口語義如果業(yè)務(wù)要求“結(jié)果必須在原類型范圍內(nèi)”那必須做溢出檢查如果業(yè)務(wù)允許結(jié)果升格為更寬類型那直接返回高精度類型更簡(jiǎn)單。這兩種決策對(duì)應(yīng)完全不同的代碼實(shí)現(xiàn)沒有誰絕對(duì)更優(yōu)。3. 實(shí)戰(zhàn)手寫帶溢出防護(hù)的通用反轉(zhuǎn)函數(shù)完整實(shí)現(xiàn)3.1 溢出防護(hù)的數(shù)學(xué)原理這一節(jié)是全文最核心的干貨。先看一個(gè)事實(shí)在 Java 中int的范圍是 -2147483648 到 2147483647。反轉(zhuǎn)后超出這個(gè)范圍就出問題。問題在于我們沒法等到 result 已經(jīng)溢出后再補(bǔ)救因?yàn)橐绯龊蟮臄?shù)值已經(jīng)截?cái)酂o從判斷“原始值”到底是不是溢出。解決辦法是在每次乘 10 加位之前判斷這一步操作是否會(huì)導(dǎo)致溢出。假設(shè)當(dāng)前結(jié)果值為 result下一位數(shù)字為 digit如果我執(zhí)行result * 10 digit那結(jié)果必然落在某個(gè)范圍里。通過移項(xiàng)可以得到安全條件如果 result (上限 - digit) / 10那么 result * 10 digit 必然超過上限這個(gè)不等式來自對(duì)result * 10 digit 上限的等價(jià)變形。上限為 2147483647 時(shí)if (result (Integer.MAX_VALUE - digit) / 10) { // 即將溢出 }負(fù)數(shù)方向同理用 Integer.MIN_VALUE 做判斷if (result (Integer.MIN_VALUE - digit) / 10) { // 即將溢出 }這個(gè)檢查不需要引入任何額外的庫或類型幾個(gè)整數(shù)比較運(yùn)算就完成性能損耗極小。3.2 Java 版的完整實(shí)現(xiàn)與測(cè)試用例結(jié)合上面的檢查邏輯帶溢出防護(hù)的 Java 實(shí)現(xiàn)如下public class DigitReverse { public int reverse(int x) { int result 0; while (x ! 0) { int digit x % 10; // 正數(shù)溢出檢查 if (result (Integer.MAX_VALUE - digit) / 10) { return 0; // 溢出時(shí)返回0或按業(yè)務(wù)約定拋異常 } // 負(fù)數(shù)溢出檢查 if (result (Integer.MIN_VALUE - digit) / 10) { return 0; } result result * 10 digit; x / 10; } return result; } }這里溢出行為我選擇返回 0這是力扣這類題目的標(biāo)準(zhǔn)約定。真實(shí)項(xiàng)目里我更推薦拋一個(gè)帶上下文的業(yè)務(wù)異常比如ReversedValueOverflowException把原始值、反轉(zhuǎn)后的估算方向一起帶出去方便排查。測(cè)試用例設(shè)計(jì)如下輸入期望輸出說明123321正數(shù)基本路徑-123-321負(fù)數(shù)路徑符號(hào)保留120021尾隨零被舍棄00零的特殊情況循環(huán)不進(jìn)10001多個(gè)尾隨零21474836470正數(shù)溢出超出 Int32 上限-21474836480負(fù)數(shù)溢出絕對(duì)值超界15342364690反轉(zhuǎn)后 9646324351溢出為什么 1534236469 這個(gè)輸入值得單測(cè)因?yàn)橹粦{直覺很難看出它會(huì)溢出。我實(shí)際測(cè)過很多“粗看沒問題、跑起來溢出”的數(shù)字它就是典型代表反轉(zhuǎn)前還在 Int32 范圍內(nèi)反轉(zhuǎn)后卻超了。這類數(shù)字最適合作為回歸測(cè)試用例防止后續(xù)重構(gòu)時(shí)把溢出檢查改沒了。3.3 移植到 Python 時(shí)的一個(gè)關(guān)鍵差異Python 的 int 不限長(zhǎng)度直接使用數(shù)學(xué)法不會(huì)溢出def reverse_int_math(n: int) - int: result 0 x abs(n) sign -1 if n 0 else 1 while x ! 0: digit x % 10 result result * 10 digit x // 10 return sign * result但注意Python 里-123 % 10的結(jié)果是 7和 Java 的 -3 不一樣。因?yàn)?Python 的取模運(yùn)算保證結(jié)果符號(hào)與除數(shù)一致而不是與被除數(shù)一致。這就是為什么 Python 版本需要先取絕對(duì)值、單獨(dú)記錄符號(hào)。很多人把 Java 代碼直接翻譯成 Python在這一步就會(huì)踩坑。如果你需要 Python 版本也做“模擬 32 位溢出”檢查可以引入一個(gè)常量上限并同樣做預(yù)判INT_MAX 2**31 - 1 INT_MIN -2**31 def reverse_checked(n: int) - int: result 0 x abs(n) sign -1 if n 0 else 1 while x ! 0: digit x % 10 if sign 1 and result (INT_MAX - digit) // 10: return 0 if sign -1 and result (INT_MIN digit) // -10: return 0 result result * 10 digit x // 10 return sign * result這條代碼里負(fù)數(shù)側(cè)的判斷要特別小心用result (INT_MIN digit) // -10作比較本質(zhì)是把負(fù)數(shù)溢出變形為正數(shù)比較。它和 Java 版寫法完全不等價(jià)我在本地跑用例時(shí)發(fā)現(xiàn)很多移植版本在這里寫錯(cuò)符號(hào)導(dǎo)致負(fù)數(shù)輸入永遠(yuǎn)溢出不溢出。4. 反轉(zhuǎn)之后的工程擴(kuò)展從單題到一批實(shí)用場(chǎng)景4.1 用反轉(zhuǎn)思路解決回文數(shù)判斷數(shù)字反轉(zhuǎn)最常見的衍生應(yīng)用就是回文數(shù)判斷。回文數(shù)就是正著讀和反著讀都一樣的數(shù)比如 12321、45654。你不必真的把整個(gè)數(shù)字反轉(zhuǎn)出來再比較一個(gè)更高效的做法是只反轉(zhuǎn)后半部分和前半部分比較。以 12321 為例先把 12321 的后半部分 12 逐位反轉(zhuǎn)成 12然后和前半部分 123 比較。由于位數(shù)是奇數(shù)中間位 3 可以舍棄比較條件變成后半部分 前半部分 // 10。Java 實(shí)現(xiàn)public boolean isPalindrome(int x) { if (x 0 || (x % 10 0 x ! 0)) { return false; } int reversedHalf 0; while (x reversedHalf) { reversedHalf reversedHalf * 10 x % 10; x / 10; } return x reversedHalf || x reversedHalf / 10; }這個(gè)方案只反轉(zhuǎn)一半循環(huán)次數(shù)減半而且天然避免了溢出問題因?yàn)榉崔D(zhuǎn)后的數(shù)字不會(huì)超過原數(shù)字的一半長(zhǎng)度。這個(gè)技巧在做大數(shù)據(jù)量判斷時(shí)很管用。4.2 反轉(zhuǎn)思想在數(shù)據(jù)校驗(yàn)場(chǎng)景中的實(shí)戰(zhàn)案例我實(shí)際遇到過的場(chǎng)景是 ISBN-10 校驗(yàn)碼的生成與校驗(yàn)。ISBN-10 的校驗(yàn)規(guī)則是將前 9 位數(shù)字分別乘以 10 到 2 的權(quán)重求和后對(duì) 11 取模用 11 減去余數(shù)得到校驗(yàn)碼。這段邏輯里就需要對(duì)數(shù)字串進(jìn)行加權(quán)求和而加權(quán)順序正好和“從低位到高位逐位處理”是一致的。處理這類場(chǎng)景時(shí)反轉(zhuǎn)算法中“從低位逐位彈出”的思想可以直接遷移def isbn10_check_digit(digits: str) - str: total 0 for i, ch in enumerate(digits): weight 10 - i total int(ch) * weight check (11 - total % 11) % 11 return X if check 10 else str(check)這個(gè)例子說明所謂數(shù)字反轉(zhuǎn)本質(zhì)上是一種“調(diào)整數(shù)字遍歷方向”的能力。很多校驗(yàn)、加密、格式轉(zhuǎn)換邏輯都需要從最低位開始處理數(shù)學(xué)法的逐位彈出能力比一次反轉(zhuǎn)更有用。4.3 不同語言里的坑和差異性速查我在不同語言里實(shí)現(xiàn)過數(shù)字反轉(zhuǎn)遇到的差異點(diǎn)整理成表方便你用的時(shí)候快速對(duì)照語言整數(shù)取模行為負(fù)數(shù)默認(rèn)整數(shù)類型是否自動(dòng)溢出Java-123 % 10 -3int32位靜默溢出需手動(dòng)檢查C-123 % 10 -3int通常32位未定義行為體現(xiàn)在截?cái)郟ython-123 % 10 7int任意精度永不溢出JavaScript-123 % 10 -3Number雙精度超出安全整數(shù)后精度損失Go-123 % 10 -3int平臺(tái)相關(guān)靜默溢出這里我想特別提到 Go。很多人以為 Go 的 int 在 64 位機(jī)器上就是 64 位反轉(zhuǎn) Long 范圍不會(huì)溢出。但 Go 的int類型在 32 位平臺(tái)上只有 32 位同樣的代碼在不同架構(gòu)上行為不一致。如果寫跨平臺(tái)庫最好顯式聲明用int32還是int64并在代碼里用對(duì)應(yīng)類型的 Max/Min 常量做判斷。4.4 反轉(zhuǎn)的邊界這個(gè)思路還能往哪延伸數(shù)字反轉(zhuǎn)的思路再往外延伸還能覆蓋這些場(chǎng)景字符串倒序輸出比如日志里反查某一串字符二進(jìn)制位反轉(zhuǎn)比如某些哈希算法里的位序調(diào)整矩陣或數(shù)組的逆序排列比如二維數(shù)組轉(zhuǎn)置時(shí)間格式里的倒序規(guī)則比如某些協(xié)議里的時(shí)間戳倒排以二進(jìn)制位反轉(zhuǎn)為例比如把 0b1101 反轉(zhuǎn)為 0b1011核心邏輯同樣是“逐位彈出、逐位推入”只不過彈出的是二進(jìn)制位def reverse_bits(n: int) - int: result 0 for _ in range(32): result (result 1) | (n 1) n 1 return result這和十進(jìn)制數(shù)字反轉(zhuǎn)是一模一樣的骨架只是把乘 10 換成了左移一位取模 10 換成了按位與 1。理解了數(shù)字反轉(zhuǎn)這一類位操作題就都通了。我個(gè)人在使用中最大的體會(huì)是反轉(zhuǎn)數(shù)字這道題真正的分水嶺不在算法本身而在“邊界感知”。很多開發(fā)者刷題時(shí)靠死記硬背過關(guān)真到項(xiàng)目里寫工具函數(shù)時(shí)既不寫溢出檢查也不對(duì)負(fù)數(shù)和尾隨零做測(cè)試覆蓋最后線上出問題又查不到根因。建議你現(xiàn)在就把自己常用的語言版本寫一遍補(bǔ)上溢出檢查和邊界測(cè)試用例存成常用工具函數(shù)下次再遇到要反轉(zhuǎn)數(shù)字的場(chǎng)景時(shí)直接拿出來復(fù)用能省一大半排查時(shí)間。