有的時(shí)候我們需要處理超出int，甚至是int64范圍的數(shù)字，而用浮點(diǎn)型數(shù)字又會(huì)存在精度問(wèn)題，所以就需要設(shè)計(jì)一種可以存儲(chǔ)超大（無(wú)上限）的整數(shù)的數(shù)據(jù)結(jié)構(gòu)。前不久我把整個(gè)庫(kù)寫出來(lái)了，在這里貼一點(diǎn)設(shè)計(jì)思路。
首先，數(shù)字的保存使用int數(shù)組。我們所理解的整數(shù)表達(dá)方式都是10進(jìn)制的，不過(guò)我把進(jìn)制調(diào)整到了10000，就是說(shuō)數(shù)組的每個(gè)元素保存了0～9999的一個(gè)數(shù)字。為什么不用更高的進(jìn)制呢？比如結(jié)合int的上限設(shè)計(jì)到100000000？這是為了防止在乘法中出現(xiàn)溢出。當(dāng)然如果想要節(jié)省空間，那么設(shè)計(jì)1億的上限也還行，不過(guò)在乘法時(shí)就要做一些有技巧性的處理，會(huì)降低效率。因此就只好“空間換時(shí)間”了。^_^
然后，數(shù)字就從高位到地位保存起來(lái)。num[0]保存的相當(dāng)于“個(gè)位”，指標(biāo)越高保存的位數(shù)越高。再用一個(gè)bool標(biāo)識(shí)正負(fù)號(hào)。這樣數(shù)據(jù)結(jié)構(gòu)就差不多了。
接下來(lái)要處理輸入輸出。輸出很簡(jiǎn)單，首先把最高位輸出。注意，開(kāi)頭如果是0的話要跳過(guò)不輸出。但是如果整個(gè)數(shù)字就剛好是0，那么就要特別小心，注意判斷長(zhǎng)度。此外還有“-0”這樣的情況，小心應(yīng)付。輸出高位之后，地位的數(shù)字先轉(zhuǎn)化為字符串（用itoa），然后在前面加0，補(bǔ)足4位。輸出注意處理負(fù)號(hào)。相對(duì)而言，輸出相當(dāng)相當(dāng)容易，小心應(yīng)付各種可能的輸出情況就好了。而輸入是很難的，因?yàn)槲以O(shè)計(jì)的時(shí)候考慮到了使用科學(xué)記數(shù)法輸入的方式，比如7.45E+90等等。這樣的情況太多了，以至于寫了80多行代碼就是為了處理輸入……列舉幾個(gè)比較麻煩的例子：0E0, 0E+0, 0E-0, +0E0, +0E-0, 7.80000000000000e0000000008,000009.6767E89, 988000000e-3……
加減法也很簡(jiǎn)單，注意進(jìn)位借位就行了。其實(shí)只要把加法寫好了，減法就是a+(-b)而已。
核心是乘法。我們小學(xué)時(shí)用的乘法是O(n^2)時(shí)間的，如果數(shù)字位數(shù)比較大就很慢了，我曾經(jīng)試過(guò)1千位的兩個(gè)數(shù)字相乘，大約花了10秒鐘，已經(jīng)很慢了。曾經(jīng)有高手提起過(guò)FFT（Fast Fourier Transformation， 快速傅立葉變換），這種算法可以在O(nlogn)時(shí)間內(nèi)完成，也就是說(shuō)兩個(gè)1千位的數(shù)字相乘可以在毫秒級(jí)別完成，相當(dāng)理想的算法！但是我知道現(xiàn)在還是沒(méi)有找到這個(gè)算法的詳細(xì)內(nèi)容，如果看此貼的朋友了解的話，麻煩傳授一下，謝了 ！我現(xiàn)在用的是Divide and Conquer（分治）， 時(shí)間復(fù)雜度O（n^1.58），相對(duì)傳統(tǒng)算法快了一點(diǎn)點(diǎn)，1千位數(shù)的乘法可以在500毫秒內(nèi)完成，還算湊合吧……
除法（還有求余數(shù)）， 則是在乘法的基礎(chǔ)上發(fā)展的。其實(shí)就是“猜測(cè)”的辦法。從位數(shù)估計(jì)出商的上下限，然后用2分。復(fù)雜度比乘法高logn量級(jí)。注意可以先判斷一下除數(shù)是不是10的整數(shù)次冪，如果是的話直接移動(dòng)數(shù)組元素即可。10整數(shù)次冪的乘法也應(yīng)當(dāng)用移位實(shí)現(xiàn)，O(n)時(shí)間，最快。