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