簡(jiǎn)介一份用于數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的大數(shù)運(yùn)算完整工程面向高校學(xué)生、算法初學(xué)者以及需要完成同類(lèi)課題的開(kāi)發(fā)者。資源以 C 實(shí)現(xiàn)為主同時(shí)支持十進(jìn)制與二進(jìn)制大數(shù)的加法、減法、乘法、除法、乘方、取模六類(lèi)運(yùn)算包含快速冪、長(zhǎng)除法、逐位進(jìn)位與借位等典型算法思路可直接作為課設(shè)源碼、算法學(xué)習(xí)素材或二次開(kāi)發(fā)基礎(chǔ)。包體共 35 個(gè)文件壓縮包大小 22.24MB主要包含 C 源文件與頭文件、Python 驗(yàn)證腳本、txt 輸入輸出樣例、data 數(shù)據(jù)文件以及可執(zhí)行程序從核心算法到測(cè)試驗(yàn)證形成完整鏈條目前已有 1351 人學(xué)習(xí)下載適合數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)、期末項(xiàng)目及算法進(jìn)階練習(xí)。通過(guò)閱讀源碼可以理解大數(shù)在數(shù)組/字符串存儲(chǔ)下的逐位運(yùn)算、商與余數(shù)的迭代生成、快速冪減少乘法次數(shù)等關(guān)鍵實(shí)現(xiàn)配套的多種測(cè)試數(shù)據(jù)與 Python 對(duì)照結(jié)果便于自查正確性并生成實(shí)驗(yàn)報(bào)告。工程內(nèi)模塊劃分清晰按運(yùn)算類(lèi)型即可快速定位對(duì)應(yīng)代碼實(shí)用性較強(qiáng)。1. 大數(shù)運(yùn)算課程設(shè)計(jì)先想清楚“大”在哪再寫(xiě)第一行代碼大數(shù)運(yùn)算課程設(shè)計(jì)是數(shù)據(jù)結(jié)構(gòu)課里最容易被低估的一道題題目就六個(gè)大字“大數(shù)加法大數(shù)減法”可真上手就會(huì)發(fā)現(xiàn)int 連 21 億都裝不下隨便喂一個(gè) 30 位的輸入數(shù)組、鏈表、進(jìn)位借位這些基礎(chǔ)結(jié)構(gòu)立刻被逼出原形。我見(jiàn)過(guò)太多人把六個(gè)運(yùn)算寫(xiě)成六個(gè)互相獨(dú)立的字符串處理函數(shù)代碼跑通了卻講不清每條復(fù)雜度答辯一追問(wèn)就翻車(chē)。這份資源把減法先比較大小、乘法先乘后進(jìn)位、除法按位試商、乘方用二進(jìn)制擴(kuò)展法、取模直接復(fù)用除法結(jié)果以及十進(jìn)制和二進(jìn)制兩種輸入的解析封裝串在了一條完整的鏈路上適合期末課程設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)與算法自測(cè)也想用一道題把線性表玩透的 408 考研黨。2. 大數(shù)存儲(chǔ)與加減法數(shù)組逆序存放是實(shí)現(xiàn)高精度的第一課2.1 存儲(chǔ)設(shè)計(jì)為什么逆序存低位、為什么不用鏈表大數(shù)運(yùn)算的第一步不是寫(xiě)加法而是決定“一個(gè)超長(zhǎng)整數(shù)在內(nèi)存里長(zhǎng)什么樣”。最經(jīng)典的做法是用 int 數(shù)組每個(gè)元素存一位十進(jìn)制數(shù)字下標(biāo) 0 存?zhèn)€位下標(biāo) 1 存十位依此類(lèi)推。這么做的理由很實(shí)在加法進(jìn)位是從低位往高位傳播的逆序存儲(chǔ)后進(jìn)位方向正好和數(shù)組下標(biāo)增長(zhǎng)方向一致循環(huán)寫(xiě)起來(lái)就是正向遍歷不需要從尾巴往頭倒著摸。鏈表也能做嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)C 語(yǔ)言版》里不少習(xí)題也鼓勵(lì)用鏈表表達(dá)多項(xiàng)式和大整數(shù)。但我的建議是課程設(shè)計(jì)如果沒(méi)有額外要求優(yōu)先用定長(zhǎng)數(shù)組。原因是鏈表每個(gè)節(jié)點(diǎn)額外帶一個(gè) next 指針內(nèi)存不連續(xù)遍歷時(shí) cache 命中率差而且大數(shù)運(yùn)算的瓶頸在進(jìn)位和借位的連續(xù)掃描數(shù)組的隨機(jī)訪問(wèn)比鏈表快得多。鏈表更適合展示“插入刪除”的場(chǎng)景大數(shù)運(yùn)算這種高頻遍歷場(chǎng)景數(shù)組天然更合適。#define MAX_DIGITS 1024 typedef struct { int digits[MAX_DIGITS]; // 下標(biāo)0存?zhèn)€位digits[i] 取值范圍 0~9 int len; // 當(dāng)前有效位數(shù)digits[0]~digits[len-1] int sign; // 1 表示正-1 表示負(fù)0 表示數(shù)值為 0 } BigInt;說(shuō)明MAX_DIGITS設(shè)成 1024 意味著最大支持 1024 位十進(jìn)制數(shù)課程設(shè)計(jì)夠用如果題目要求 10000 位直接改宏即可。len是有效長(zhǎng)度比如數(shù)字 100 存下來(lái)是 digits[0]0、digits[1]0、digits[2]1len3。sign單獨(dú)存符號(hào)避免把負(fù)號(hào)揉進(jìn)數(shù)字位里后面做減法比較時(shí)省很多事。這里每個(gè)元素只存一位十進(jìn)制是“一位一存”的樸素方案代碼最好懂、進(jìn)位最好寫(xiě)缺點(diǎn)是空間利用率低真正追求性能的版本會(huì)每個(gè)元素存 9 位也就是“萬(wàn)進(jìn)制”這個(gè)放到最后一章說(shuō)。2.2 大數(shù)加法進(jìn)位傳播與結(jié)果長(zhǎng)度修正加法是最不需要思考的運(yùn)算但也是第一個(gè)容易出細(xì)節(jié)問(wèn)題的地方。兩個(gè)數(shù)相加每一位上最多出現(xiàn)99119所以進(jìn)位 carry 只可能是 0 或 1。很多初版代碼喜歡在每一位算完立刻把 carry 寫(xiě)進(jìn)下一位這沒(méi)問(wèn)題但要注意循環(huán)結(jié)束后如果還有 carry結(jié)果長(zhǎng)度必須加一否則 999 1 會(huì)算成 000。void addBigInt(BigInt *a, BigInt *b, BigInt *res) { int maxLen (a-len b-len) ? a-len : b-len; int carry 0; for (int i 0; i maxLen; i) { int sum carry; if (i a-len) sum a-digits[i]; if (i b-len) sum b-digits[i]; res-digits[i] sum % 10; carry sum / 10; } if (carry 0) { res-digits[maxLen] carry; res-len maxLen 1; } else { res-len maxLen; } }邏輯說(shuō)明循環(huán)從低位到高位逐位累加短的那個(gè)數(shù)下標(biāo)越界后自動(dòng)補(bǔ) 0這樣 123 45678 也能正確算出 45801。sum % 10留下當(dāng)前位sum / 10作為進(jìn)位傳給下一位。參數(shù)說(shuō)明a、b是輸入res是輸出允許res和a指向同一個(gè)變量函數(shù)內(nèi)部逐位寫(xiě)入不會(huì)讀到臟數(shù)據(jù)。唯一要注意的是函數(shù)調(diào)用前最好把res-len清 0避免舊數(shù)據(jù)殘留。這個(gè)實(shí)現(xiàn)的時(shí)間復(fù)雜度是 O(n)n 是較長(zhǎng)的那個(gè)數(shù)的位數(shù)和手算加法完全一致。2.3 大數(shù)減法先比較再相減符號(hào)用 sign 字段兜底減法比加法麻煩一個(gè)量級(jí)麻煩不在借位而在“誰(shuí)減誰(shuí)”。如果直接拿小數(shù)減大數(shù)借位會(huì)借到天上去。正確的套路是先比較兩個(gè)數(shù)的絕對(duì)值大小保證大數(shù)在前、小數(shù)在后只算“大減小”再把符號(hào)記在 sign 字段里。這也是為什么我在結(jié)構(gòu)體里單獨(dú)留了sign。int compareBigInt(BigInt *a, BigInt *b) { if (a-len ! b-len) return a-len - b-len; for (int i a-len - 1; i 0; i--) { if (a-digits[i] ! b-digits[i]) return a-digits[i] - b-digits[i]; } return 0; // 完全相等 } void subBigInt(BigInt *a, BigInt *b, BigInt *res) { int neg 0; if (compareBigInt(a, b) 0) { BigInt *tmp a; a b; b tmp; // 交換指針保證 a b neg 1; } int borrow 0; for (int i 0; i a-len; i) { int dif a-digits[i] - borrow; if (i b-len) dif - b-digits[i]; if (dif 0) { dif 10; borrow 1; } else { borrow 0; } res-digits[i] dif; } res-len a-len; while (res-len 1 res-digits[res-len - 1] 0) { res-len--; // 去掉高位多余的 0比如 100-99001要變成 1 } res-sign neg ? -1 : 1; }邏輯說(shuō)明compareBigInt先比長(zhǎng)度再比高位長(zhǎng)度長(zhǎng)的絕對(duì)值一定大長(zhǎng)度相同就從最高位往低位逐位比。減法主循環(huán)里borrow表示上一位有沒(méi)有借位當(dāng)前位不夠減就10并把borrow置 1。每次用a-len作為循環(huán)上限是因?yàn)槲覀儽ＷCa是較大的那個(gè)。參數(shù)說(shuō)明兩個(gè)指針a、b的交換用的是指針交換不復(fù)制數(shù)組內(nèi)容效率高。注意這里只處理了“絕對(duì)值比較后大減小”如果輸入本身就帶符號(hào)比如負(fù)數(shù)減正數(shù)需要在調(diào)用層額外處理符號(hào)疊加課程設(shè)計(jì)通常可以約定輸入都是非負(fù)數(shù)或者在 main 里先統(tǒng)一轉(zhuǎn)成正數(shù)再調(diào)用。3. 大數(shù)乘法與除法豎式算法的兩個(gè)落地方向3.1 大數(shù)乘法先累加后進(jìn)位避免每輪都處理進(jìn)位大數(shù)乘法最直觀的寫(xiě)法是模擬小學(xué)豎式a的第 i 位乘以b的第 j 位結(jié)果放在結(jié)果的第ij位。第一次寫(xiě)的時(shí)候很容易寫(xiě)成“每乘一位就立刻把進(jìn)位加到下一位”這樣也能跑通但進(jìn)位處理會(huì)和下一輪累加糾纏在一起代碼極易出錯(cuò)。我常用的做法是分兩步第一步只做乘法和累加先讓tmp[ij]把該加的都加上第二步再統(tǒng)一處理進(jìn)位。void mulBigInt(BigInt *a, BigInt *b, BigInt *res) { int tmp[MAX_DIGITS * 2] {0}; for (int i 0; i a-len; i) { for (int j 0; j b-len; j) { tmp[i j] a-digits[i] * b-digits[j]; } } int carry 0; res-len a-len b-len; // 兩個(gè) n 位、m 位數(shù)相乘最多 nm 位 for (int i 0; i res-len; i) { int value tmp[i] carry; res-digits[i] value % 10; carry value / 10; } while (res-len 1 res-digits[res-len - 1] 0) { res-len--; // 比如 0 * 999 的結(jié)果應(yīng)該是 0不是 000 } }邏輯說(shuō)明tmp[ij]累加的是所有能貢獻(xiàn)到第ij位的乘積累加和。舉個(gè)例子a123、b456那么tmp[2]會(huì)收到a[0]*b[2] a[1]*b[1] a[2]*b[0]也就是3*4 2*5 1*6 28。第二步統(tǒng)一進(jìn)位carry從低位往高位滾最終每個(gè)元素都變成 0~9。參數(shù)說(shuō)明tmp數(shù)組長(zhǎng)度取MAX_DIGITS*2是因?yàn)閮蓚€(gè) 1024 位數(shù)相乘最多 2048 位定成兩倍最大長(zhǎng)度能防越界如果實(shí)際位數(shù)更短循環(huán)也只遍歷到a-len b-len。時(shí)間復(fù)雜度是 O(n*m)n 和 m 是兩個(gè)數(shù)的位數(shù)這也是樸素乘法的理論下限之內(nèi)的常見(jiàn)實(shí)現(xiàn)如果追求更快可以上 Karatsuba但課程設(shè)計(jì)階段豎式足夠。3.2 大數(shù)除法按位試商二進(jìn)制大數(shù)每商位只有 0/1除法是六個(gè)運(yùn)算里最容易寫(xiě)崩的。手算除法的本質(zhì)是從被除數(shù)最高位開(kāi)始每次“取一部分不夠除就往后拼一位”夠除就試商。放到大數(shù)里就是維護(hù)一個(gè)余數(shù)累加器cur每次把cur整體乘 10相當(dāng)于左移一位再拼上被除數(shù)的下一位然后看cur最多能減幾個(gè)除數(shù)這個(gè)次數(shù)就是商的當(dāng)前位。void trimZero(BigInt *x) { while (x-len 1 x-digits[x-len - 1] 0) { x-len--; } } void divBigInt(BigInt *a, BigInt *b, BigInt *q, BigInt *r) { BigInt cur {0}; // 余數(shù)累加器 q-len a-len; for (int i a-len - 1; i 0; i--) { // 余數(shù)乘 10相當(dāng)于把商位左移一位 mulSmall(cur, 10, cur); addSmall(cur, a-digits[i], cur); int qd 0; while (compareBigInt(cur, b) 0) { subBigInt(cur, b, cur); qd; // 當(dāng)前商位最多減 9 次 } q-digits[i] qd; } trimZero(q); trimZero(cur); *r cur; }邏輯說(shuō)明mulSmall(cur, 10, cur)是給余數(shù)乘一個(gè)一位數(shù) 10實(shí)現(xiàn)上就是從高位逆向進(jìn)位或者直接手寫(xiě)一個(gè)乘小數(shù)的函數(shù)addSmall同理給余數(shù)加上一位數(shù)字。內(nèi)層while每減一次除數(shù)商位加一理論上一位最多減 9 次所以整體復(fù)雜度約等于 O(n*m)n 是被除數(shù)位數(shù)m 是除數(shù)位數(shù)。參數(shù)說(shuō)明q是商r是余數(shù)函數(shù)結(jié)束時(shí)r一定滿(mǎn)足0 r b。這里有個(gè)容易被忽略的點(diǎn)商的長(zhǎng)度初始設(shè)成a-len因?yàn)楸怀龜?shù)有幾位商的位數(shù)最多也就是幾位最后trimZero把高位 0 去掉比如 100/50 的商初始是“002”trim 后是“2”。這個(gè)結(jié)構(gòu)對(duì)二進(jìn)制大數(shù)有個(gè)天然的好處如果內(nèi)部存的是二進(jìn)制位那么試商時(shí)每商位只可能是 0 或 1內(nèi)層while可以直接退化成一次if判斷——cur夠大就減一次、商位置 1不夠大商位直接置 0。這也是為什么很多高精度代碼庫(kù)會(huì)把十進(jìn)制和二進(jìn)制兩條路徑分別實(shí)現(xiàn)二進(jìn)制的除法性能要好得多。3.3 大數(shù)取模直接復(fù)用除法商留著不用也行取模運(yùn)算單獨(dú)寫(xiě)一份算法是典型的重復(fù)勞動(dòng)。取模的定義就是“除法剩下的余數(shù)”所以最省事的做法是調(diào)一次除法把商丟掉把余數(shù)返回。代碼少而且正確性跟著除法走除法測(cè)過(guò)之后取模就不用單獨(dú)測(cè)了。void modBigInt(BigInt *a, BigInt *b, BigInt *res) { BigInt q; divBigInt(a, b, q, res); }邏輯說(shuō)明這里直接讓divBigInt的r參數(shù)指向res商q是個(gè)局部變量運(yùn)行完就被丟棄。要注意divBigInt內(nèi)部最后*r cur是結(jié)構(gòu)體整體賦值只要r不是和q指向同一塊內(nèi)存就不會(huì)互相干擾。參數(shù)說(shuō)明如果后續(xù)要頻繁取模比如快速冪里的模乘建議把divBigInt的商參數(shù)傳一個(gè)臨時(shí)變量而不是每次都聲明新的 BigInt因?yàn)榻Y(jié)構(gòu)體整體賦值也有一份內(nèi)存拷貝開(kāi)銷(xiāo)。另外除數(shù)為 0 要在divBigInt入口做防御返回一個(gè)錯(cuò)誤碼或者直接打印提示不然while會(huì)死循環(huán)。4. 大數(shù)乘方與進(jìn)制轉(zhuǎn)換二進(jìn)制擴(kuò)展法把冪運(yùn)算從線性降到對(duì)數(shù)4.1 快速冪原理把指數(shù)拆成二進(jìn)制位逐位平方大數(shù)乘方最容易踩的性能坑是“老老實(shí)實(shí)乘 n 次”。如果算 a^1000樸素循環(huán)要做 1000 次大數(shù)乘法而大數(shù)乘法本身又是 O(m2)總開(kāi)銷(xiāo)直接起飛。二進(jìn)制擴(kuò)展法也叫快速冪的核心思想是把指數(shù)看成二進(jìn)制數(shù)比如 13 的二進(jìn)制是 1101那么 a^13 a^8 × a^4 × a^1也就是只挑二進(jìn)制位為 1 的那些“a 的 2^k 次方”乘起來(lái)。實(shí)現(xiàn)時(shí)從左到右或從右到左都行課程設(shè)計(jì)里最常見(jiàn)的寫(xiě)法是從最低二進(jìn)制位開(kāi)始指數(shù)右移一位底數(shù)平方一次遇到當(dāng)前位為 1 就把底數(shù)乘進(jìn)結(jié)果。4.2 快速冪實(shí)現(xiàn)平方、乘底、指數(shù)右移三步循環(huán)void powBigInt(BigInt *base, BigInt *exp, BigInt *res) { BigInt b *base; BigInt e *exp; setSmall(res, 1); // res 1 while (e.len 1 || e.digits[0] 0) { if (e.digits[0] % 2 1) { // 當(dāng)前二進(jìn)制最低位是 1 mulBigInt(res, b, res); // res res * b } mulBigInt(b, b, b); // b b * b即底數(shù)平方 divSmall(e, 2, e); // e e / 2二進(jìn)制右移一位 } }邏輯說(shuō)明循環(huán)不變量是“b 始終等于 base 的 2^k 次方”。每輪先看指數(shù)當(dāng)前最低位是 1 就把 b 乘進(jìn) res是 0 就不乘然后無(wú)條件把 b 平方同時(shí)指數(shù)除以 2。以 2^13 為例指數(shù)二進(jìn)制 1101按低位到高位依次是 1、0、1、1res 依次乘上 2^1、2^4、2^8最終得到 2^13。參數(shù)說(shuō)明e.digits[0] % 2能直接判斷整個(gè)大數(shù)的奇偶性是因?yàn)槲覀兊拇鎯?chǔ)是十進(jìn)制位個(gè)位數(shù)字的奇偶決定整個(gè)數(shù)的奇偶。divSmall(e, 2, e)是關(guān)鍵很多人在這里踩坑因?yàn)槊總€(gè)元素存的是十進(jìn)制位不能直接e.digits[0] 1那樣會(huì)把十位的值錯(cuò)誤地挪到個(gè)位。正確寫(xiě)法是模擬一次“除以 2”的豎式從最高位到最低位逐位帶余數(shù)計(jì)算。4.3 十進(jìn)制與二進(jìn)制統(tǒng)一封裝輸入解析與輸出轉(zhuǎn)換題目要求同時(shí)支持十進(jìn)制和二進(jìn)制大數(shù)運(yùn)算這里有個(gè)設(shè)計(jì)選擇內(nèi)部統(tǒng)一存成十進(jìn)制 BigInt輸入輸出時(shí)做進(jìn)制轉(zhuǎn)換。好處是加減乘除的代碼只寫(xiě)一套進(jìn)制只影響解析和打印。二進(jìn)制字符串轉(zhuǎn)內(nèi)部十進(jìn)制數(shù)采用“每讀一位整體乘 2 再加當(dāng)前位”的霍納方法即可。void parseBinary(const char *s, BigInt *out) { setSmall(out, 0); for (int i 0; s[i]; i) { mulSmall(out, 2, out); if (s[i] 1) { addSmall(out, 1, out); } } } void parseDecimal(const char *s, BigInt *out) { setSmall(out, 0); for (int i 0; s[i]; i) { mulSmall(out, 10, out); addSmall(out, s[i] - 0, out); } }邏輯說(shuō)明parseBinary處理“111”的邏輯是先得到 1然后乘 2 得 2、加 1 得 3再乘 2 得 6、加 1 得 7正好是二進(jìn)制 111 對(duì)應(yīng)的十進(jìn)制 7。parseDecimal是同樣的套路只是乘 10。這兩段代碼共用mulSmall和addSmall說(shuō)明存儲(chǔ)層抽象得好上層邏輯可以根本不管進(jìn)制。輸出二進(jìn)制則需要反著來(lái)不斷除以 2、取余數(shù)余數(shù)倒序排列就是二進(jìn)制串。注意純二進(jìn)制輸出天然會(huì)丟前導(dǎo)零如果題目要求按輸入寬度補(bǔ)零打印函數(shù)需要接收一個(gè)最小寬度參數(shù)這個(gè)坑在下一章展開(kāi)。void printBinary(BigInt *a) { BigInt tmp *a; char out[MAX_DIGITS * 8]; int idx 0; while (tmp.len 1 || tmp.digits[0] 0) { out[idx] (tmp.digits[0] % 2) 0; divSmall(tmp, 2, tmp); } for (int i idx - 1; i 0; i--) { putchar(out[i]); } }邏輯說(shuō)明tmp.digits[0] % 2取個(gè)位數(shù)字的奇偶性也就是當(dāng)前最低二進(jìn)制位每取一位就把整個(gè)數(shù)除以 2循環(huán)直到數(shù)變成 0。倒序輸出是因?yàn)橄热〉降氖亲畹臀?。這里divSmall和快速冪里用的是同一個(gè)函數(shù)一次實(shí)現(xiàn)兩處復(fù)用。5. 大數(shù)運(yùn)算常見(jiàn)問(wèn)題排查五個(gè)我真實(shí)踩過(guò)的坑5.1 二進(jìn)制輸入解析時(shí)數(shù)組越界現(xiàn)象解析一個(gè) 500 位的二進(jìn)制字符串“111...111”時(shí)parseBinary跑到一半程序崩潰或者解析出的數(shù)值明顯不對(duì)偶爾結(jié)果是負(fù)數(shù)。原因mulSmall和addSmall的實(shí)現(xiàn)里進(jìn)位循環(huán)只跑到當(dāng)前l(fā)en就停了。比如當(dāng)前值已經(jīng)是 999乘 2 得到 1998長(zhǎng)度從 3 變成 4如果沒(méi)處理這個(gè)新增長(zhǎng)位最高位的 1 就丟了再加 1 的時(shí)候又可能再次進(jìn)位。幾輪下來(lái)要么數(shù)組越界寫(xiě)壞相鄰內(nèi)存要么進(jìn)位丟失數(shù)據(jù)錯(cuò)誤。解決給mulSmall和addSmall加上統(tǒng)一的長(zhǎng)度修正邏輯。乘完或加完后從當(dāng)前l(fā)en開(kāi)始檢查高一位是否非零是就len同時(shí)判斷l(xiāng)en不能超過(guò)MAX_DIGITS。我一般把這段封裝成一個(gè)updateLen函數(shù)所有修改 digits 的運(yùn)算結(jié)束都調(diào)一次。5.2 減法輸出 “-0” 和多余前導(dǎo)零現(xiàn)象1 - 1 輸出“-0”100 - 99 輸出“001”更離譜的是 123 - 123 輸出“-000”。原因兩個(gè)問(wèn)題疊加。第一個(gè)是去前導(dǎo)零時(shí)把循環(huán)條件寫(xiě)成了while (digits[len-1] 0) len--沒(méi)保留最后一位導(dǎo)致 0 被清成空串打印時(shí)亂套。第二個(gè)是符號(hào)處理compareBigInt返回 0兩數(shù)相等時(shí)代碼仍然按neg1走了于是給 0 加了個(gè)負(fù)號(hào)。解決去前導(dǎo)零強(qiáng)制保底一位條件寫(xiě)成while (len 1 digits[len-1] 0) len--;。減法主函數(shù)開(kāi)頭先比較如果compareBigInt(a, b) 0直接res-sign 1并退出不進(jìn)交換邏輯。從那以后我寫(xiě)所有涉及符號(hào)的運(yùn)算都會(huì)先問(wèn)一句“結(jié)果為零時(shí)符號(hào)應(yīng)該是什么”。5.3 除法里商位不進(jìn)位的死循環(huán)現(xiàn)象123 / 12 算出商 1正確答案是 10有時(shí)候程序直接卡死CPU 跑滿(mǎn)不退出。原因按位試商的循環(huán)里cur在拼入被除數(shù)當(dāng)前位之前忘了乘 10。比如被除數(shù)處理到“12”這一位時(shí)cur存的是上一次的余數(shù) 0直接加 1 得到 1而不是 0×1011最后一位 3 進(jìn)來(lái)時(shí) cur 只是從 1 變成 3而不是 1×10313于是商位少算了一輪。死循環(huán)的情況多半是除數(shù)為 0或者compareBigInt寫(xiě)錯(cuò)導(dǎo)致 cur 永遠(yuǎn)不小于除數(shù)。解決每次循環(huán)第一步先mulSmall(cur, 10, cur)再addSmall(cur, a-digits[i], cur)順序不能反。除數(shù)為 0 在函數(shù)入口直接判掉打印“除數(shù)不能為 0”并返回錯(cuò)誤碼。這個(gè)坑我印象最深因?yàn)楸砻嫔峡创a每一行都對(duì)只有把豎式每一步打印出來(lái)才發(fā)現(xiàn) cur 缺了左移。5.4 快速冪的指數(shù)右移寫(xiě)錯(cuò)導(dǎo)致結(jié)果錯(cuò)亂現(xiàn)象2^10 用快速冪算出來(lái)是 2^6或者 2^4打印中間過(guò)程發(fā)現(xiàn)指數(shù)序列變成 10、4、1、0而不是 10、5、2、1、0。原因因?yàn)槲覀兊?BigInt 每個(gè)元素存的是十進(jìn)制位直接寫(xiě)e.digits[0] 1是完全錯(cuò)誤的——十進(jìn)制個(gè)位右移一位只是把個(gè)位數(shù)除以 2不是把整個(gè)大數(shù)除以 2。比如 10 的個(gè)位是 0右移還是 0整個(gè)數(shù)卻應(yīng)該是 5。指數(shù)右移的正確姿勢(shì)是調(diào)用divSmall(e, 2, e)它會(huì)從最高位向最低位逐位帶余數(shù)計(jì)算等價(jià)于對(duì)整個(gè)大數(shù)做一次十進(jìn)制除法。解決把快速冪里的右移統(tǒng)一改走divSmall同時(shí)策略上每次右移前先判斷奇偶再右移保證循環(huán)不變量正確。另外快速冪里mulBigInt(res, b, res)一定要允許res和b是同一個(gè)值我的乘法實(shí)現(xiàn)里是先完整算進(jìn)臨時(shí)數(shù)組再?gòu)?fù)制回 res所以安全如果你的乘法是邊乘邊寫(xiě)這里要格外小心別名問(wèn)題。5.5 二進(jìn)制輸出丟了前導(dǎo)零現(xiàn)象輸入“00001111”轉(zhuǎn)成內(nèi)部大數(shù)再打印變成“1111”和輸入寬度對(duì)不上。如果題目要求按固定字長(zhǎng)輸出這塊直接丟分。原因printBinary的反向取余邏輯天然丟前導(dǎo)零因?yàn)閮?nèi)部 BigInt 只保存數(shù)值不保存“輸入字符串原來(lái)有多長(zhǎng)”這個(gè)信息。解決在解析入口記錄原始字符串長(zhǎng)度或者給打印函數(shù)加一個(gè)minWidth參數(shù)輸出前先補(bǔ)零。我常用的做法是在主程序里保存 raw 輸入字符串的長(zhǎng)度打印二進(jìn)制結(jié)果時(shí)傳入max(minWidth, 實(shí)際位數(shù))手動(dòng)在前面補(bǔ) 0。這個(gè)坑不踩一次很難意識(shí)到因?yàn)榇蠖鄶?shù)自測(cè)用例都會(huì)用不帶前導(dǎo)零的二進(jìn)制串。6. 驗(yàn)證與進(jìn)階用六個(gè)用例把整套大數(shù)運(yùn)算過(guò)一遍6.1 邊界回歸用例與沒(méi)有寫(xiě)在題目里的加分項(xiàng)寫(xiě)完六個(gè)運(yùn)算不要急著交先跑一組能同時(shí)覆蓋“進(jìn)位、借位、截?cái)?、符?hào)、進(jìn)制邊界”的用例。我每次都會(huì)把這幾個(gè)用例固定放在 main 函數(shù)里當(dāng)回歸測(cè)試運(yùn)算輸入期望輸出驗(yàn)證點(diǎn)加法999999999999 11000000000000跨位連續(xù)進(jìn)位長(zhǎng)度加一減法1000000000 - 1999999999連續(xù)借位去掉前導(dǎo)零減法123 - 1230結(jié)果為零時(shí)符號(hào)不能是負(fù)乘法99999 × 999999999800001高位進(jìn)位與長(zhǎng)度修正除法123456789012345 / 123459999747595按位試商、商位補(bǔ)零取模2^100 mod 9718快速冪和取模的聯(lián)合調(diào)用最后一行是我的習(xí)慣用快速冪算乘方時(shí)順手把取模也驗(yàn)一遍。因?yàn)轭}目只要求“大數(shù)乘方”和“大數(shù)取?！狈珠_(kāi)實(shí)現(xiàn)但真正實(shí)戰(zhàn)里這兩者幾乎總是搭配出現(xiàn)。在快速冪的三步循環(huán)里把mulBigInt換成modBigInt(mulBigInt(...), mod)就能得到模冪結(jié)果這其實(shí)是很多密碼學(xué)算法的基礎(chǔ)用法。如果你想把代碼做厚這是最容易的加分點(diǎn)。驗(yàn)證方式上建議把十進(jìn)制和二進(jìn)制各跑一遍同樣的運(yùn)算確認(rèn)結(jié)果一致比如十進(jìn)制輸入13 * 7 91二進(jìn)制輸入1101 * 111也應(yīng)該輸出1011011。這能同時(shí)驗(yàn)證解析、運(yùn)算、打印三段邏輯沒(méi)有互相污染。從那以后我每寫(xiě)完一個(gè)課程設(shè)計(jì)版本都強(qiáng)制自己先把這組用例在 main 里跑一遍再隨機(jī)生成兩個(gè)大數(shù)交叉驗(yàn)證一次最后才敢交給老師。這種“先回歸、再提交”的習(xí)慣幫我在答辯前少改了很多低級(jí)錯(cuò)誤。如果你手頭這份資源里的代碼也出現(xiàn)了類(lèi)似問(wèn)題照著第五章的五個(gè)坑逐條對(duì)照應(yīng)該能省下不少調(diào)試時(shí)間。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取