用 C++ 实现大整数的加减，思路是什么？第1页

miloyip 网友的相关建议:

首先，这个问题可归类为

（任意精度计算），一般会包含任意精度的整数（或定点数）、有理数及浮点数。

许多答案提及到使用10进制（或是10进制的字符串）进行运算，但这并不是唯一的方法，而且比较慢。

如果程序有大量的计算，而把结果转换成10进制显示并非程序的主要功能，那么可以考虑使用2^n进制。例如在32位架构下，使用vector<uint32_t>及去代表一个任意精度的无号整数。

我们首先要实现n位全加器，用2^n进制的话可以使用机器本身的算术指令，例如以下的 C++实现：

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

一些编译器提供带进位的加法，例如VC x86中有_addcarry_u32()和addcarry_u64()指令。

任意精度的无号整数的加法和减法可以使用简单的漣波进位加法器（ripple carry adder）实现，也可考虑使用并行的超前进位加法器（carry-lookahead adder）。

       // 最低位在A.front()，最高位在A.back()。 void RippleCarryAdder(     const vector<uint32_t>& A     const vector<uint32_t>& B     vector<uint32_t>* 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）和其他更快的算法。

用 C++ 实现大整数的加减，思路是什么？的其他答案点击这里