用 C++ 實現大整數的加減，思路是什麼？

01-04

首先，這個問題可歸類為Arbitrary-precision arithmetic（任意精度計算），一般會包含任意精度的整數（或定點數）、有理數及浮點數。

許多答案提及到使用10進位（或是10進位的字元串）進行運算，但這並不是唯一的方法，而且比較慢。

如果程序有大量的計算，而把結果轉換成10進位顯示並非程序的主要功能，那麼可以考慮使用2^n進位。例如在32位架構下，使用vector&及去代表一個任意精度的無號整數。

我們首先要實現n位全加器，用2^n進位的話可以使用機器本身的算術指令，例如以下的 C++實現：

uint32_t FullAdder32(uint32_t a, uint32_t b, uint32_t inCarry, uint32_t* outCarry) { uint64_t c = static_cast&(a) + static_cast&(b) + static_cast&(inCarry); *outCarry = static_cast&(c &>&> 32); return static_cast&(c 0xFFFFFFFF); }

一些編譯器提供帶進位的加法，例如VC x86中有_addcarry_u32()和addcarry_u64()指令。

任意精度的無號整數的加法和減法可以使用簡單的漣波進位加法器（ripple carry adder）實現，也可考慮使用並行的超前進位加法器（carry-lookahead adder）。

// 最低位在A.front()，最高位在A.back()。 void RippleCarryAdder( const vector& A const vector& B vector&* R) { assert(!A.empty()); assert(!B.empty()); assert(R != NULL);


    const size_t n = max(A.size(), B.size())

    R-&>clear();

    R-&>reserve(n + 1);

// 為簡單起見，超越範圍的輸入補零。可優化為不同cases的循環，減少inner-loop分支。 uint32_t inCarry = 0u; for (size_t i = 0; i &< n; i++) { uint32_t outCarry; R-&>push_back(FullAdder32( i &< A.size() ? A[i] : 0u, i &< B.size() ? B[i] : 0u, inCarry, outCarry)); inCarry = outCarry; } // 最後的進位 if (inCarry) R-&>push_back(inCarry); } // 注意：隨手寫，未經測試

減法可使用二進位補數記法（two"s complement representation），然後用加法處理。二進位補數記法的取反很簡單，而加一也可以放在開始時設置inCarry=1。但要注意處理負數的結果，要支持負數的話，每個任意精度的數還要多加一個符號標記。

然而，如果需要把結果轉換為十進位，便需要除法或c。每次除10取模可得一個10進位。除以一個常數可以優化為乘數及移位，詳情可看《Hacker"s Delight (豆瓣)》。

另一種方法，是使用接近機器位數的10^n進位作為基數（base），例如32位架構可以使用10^9。優點是可以簡單地轉換為10進位的輸出，缺點是浪費了一些運算能力。

題目沒提及乘法和除法，簡單提一提。乘法要分開低位的乘法和高位的乘法，如VC x86中的__mulh()便是64位乘法結果的高位部分，如果沒有相關指令就要把輸入切為一半一半來計算。然後像豎式計算般把每對輸入相乘然後加總，這稱為長整數乘法（long multiplication）。另外還有一些更快的方法，如Karatsuba algorithm、Toom–Cook multiplication、Sch?nhage–Strassen algorithm。除法的話也有長除法（long division）和其他更快的演算法。

小學學過列豎式吧？

就是豎式計算

加法：

相同數位對齊，若和大於9，則向前進1。

減法：

相同數位對齊，若不夠減，則向前一位借1當10

C++大整數的加法的代碼大概是這樣子：

C.len=max(A.len,B.len); int x=0; // 表示前一位的進位 for (int i=0;i&0) C[C.len++]=1;

補充一下

關於豎式計算的優化，數字分解成數組的做法，最符合人類認知的常規10進位方式，效率低，有較大的優化空間。可以考慮 100進位，1000進位， 10000進位。

由於目前主流編譯器、CPU寄存器、程序員思維還是以32位為基本運算單位，

通用運算可以用一條指令完成。

如果以64位為基準，在32位的編譯器上會被分解成多條CPU指令。

所以出於運算單位的考慮，

32位無符號數的最大值 42億多一點，兩個小於10000的數相乘，

還在取值範圍之內，不會造成溢出。

因此：用10000進位是個不錯的方案。

-----------------------------------------------------------------------------------------------------------

具體細節：

豎式計算的常規方式，就是10進位。

舉個例子：大數A是「12345678902349234947231」

數據結構是一個數組data, data[] = { 1,3,2,7,4,9...3, 2,1}，長度是23.

如果做運算，+ 個大數B 「9123479123498432545」 data[] = {5,4,5,2... 2, 1,9 }, 長度是24.

還是豎式計算，如@智硬的演算法。明顯加減法的演算法複雜度是O(N)，乘法是O( N*N )

如果搞成10000進位，

大數A就被記錄成 {123，4567，8902，3492，3494，7231 }，需要倒序一下。

大數B就被記錄成 {912，3479，1234，9843，2545}，請倒序一下。

還是豎式計算，但加減法的計算量是原來的1/4，乘法是原來的1/16

因為對CPU來說，只要寄存器放得下，

1+5 和 7231 + 2545 的計算量是一樣的，一條CPU指令足矣。

1*5 和 7231 * 2545 也是如此。

-----------------------------------------------------------------------------------------------------------

再次優化：

不考慮CPU指令的純編程技巧的進一步優化，可以用FFT引入虛數計算來優化豎式乘法。

演算法複雜度可以從O(N*N) 優化到 O(NlogN)。

實現細節百度「FFT優化乘法」即可。

數組模擬，最好減之前比較一下大小，接下來就是模擬手動減法過程了

利用數組來模擬一個大數，有一個取巧的方法是倒序存儲，見支持上千位的大整數類BigInt（由於項目中不使用除法，所以沒有實現）

https://github.com/Msr-B/Msr.LibCpp/tree/master/msr/number

初中的方法一般是字元串或者數組模擬一下。。

用字元串儲存大整數，有模擬豎式相乘和使用分治法兩種方法(當然還有別的方法，比如一萬進位等)，相對來說很大的數字後者效率更高。自己編寫代碼完成字元串表示的數字的加、減、乘、進位等運算，最終把結果用字元串的形式輸出。

你也可以做啊！用數組存放每一位數字，模擬人工求解過程

請用boost multiprecision！

如果用戶不知道自己要輸入幾位數，那麼在輸入時改怎樣來存儲這個大整數

用字元串或者數組模擬大數，然後按小學學過的運演算法則寫出來就行了。

大數加減寫起來很簡單的，乘除要稍難一點，其中除比乘更複雜一點。