如何在C ++中实现big int
我想在C ++中实现一个大的int类作为编程练习 – 一个可以处理大于long int的数字的类。 我知道已经有几个开源的实现，但我想写我自己的。 我试图感受一下正确的方法是什么。
我明白，一般的策略是把数字作为一个字符串，然后将其分解成更小的数字（例如单个数字），并将它们放在一个数组中。 在这一点上，实现各种比较操作符应该相对简单。 我主要关心的是如何实现像加法和乘法这样的事情。
我正在寻找一个一般的方法和建议，而不是实际的工作代码。
需要考虑的一个大的int类：
-
数学运算符：+， – ，/，*，％不要忘记你的类可能在操作符的任一侧，操作符可以是链接的，其中一个操作数可以是int，float，double等。
-
I / O操作符：>>，<<这是你如何从用户输入中正确创建你的类，以及如何格式化输出的地方。
-
转换/转换：找出您的大型int类应该转换为什么类型/类，以及如何正确处理转换。 一个快速列表将包括double和float，并可能包括int（具有适当的边界检查）和复杂（假设它可以处理范围）。
一个有趣的挑战。 🙂
我假设你想要任意长度的整数。 我建议采用以下方法：
考虑数据类型“int”的二元性质。 考虑使用简单的二进制操作来模拟CPU中的电路在添加事物时所做的事情。 如果你更深入的感兴趣，可以考虑阅读这个维基百科关于半加器和全加器的文章 。 你会做类似的事情，但是你可以低下去 – 但是很懒，我想我会放弃，找到一个更简单的解决方案。
但在进入有关加法，减法，乘法的任何算法细节之前，让我们找到一些数据结构。 一个简单的方法，当然是将东西存储在一个std :: vector中。
template< class BaseType > class BigInt { typedef typename BaseType BT; protected: std::vector< BaseType > value_; };
您可能要考虑是否要制作一个固定大小的矢量，以及是否预先分配它。 原因是对于不同的操作，你将不得不通过向量的每个元素 – O（n）。 你可能想知道手术有多复杂，固定的n就是这样做的。
但是现在来看一些关于数字操作的算法。 你可以在逻辑上做到这一点，但是我们将使用这个神奇的CPU能力来计算结果。 但是，我们将从“半边天”和“全副本”的逻辑图中接管它是如何处理进位的。 例如，考虑如何实现+ =运算符 。 对于BigInt <> :: value_中的每个数字，您都要添加这些数字，看看结果是否产生某种形式的进位。 我们不会按位进行，而是依赖BaseType的性质（无论是长整型还是短整型）：它会溢出。
当然，如果你添加两个数字，结果必须大于那些数字中较大的一个，对吗？ 如果不是，则结果溢出。
template< class BaseType > BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand) { BT count, carry = 0; for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++) { BT op0 = count < value_.size() ? value_.at(count) : 0, op1 = count < operand.value_.size() ? operand.value_.at(count) : 0; BT digits_result = op0 + op1 + carry; if (digits_result-carry < std::max(op0, op1) { BT carry_old = carry; carry = digits_result; digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1] } else carry = 0; } return *this; } // NOTE 1: I did not test this code. And I am not sure if this will work; if it does // not, then you must restrict BaseType to be the second biggest type // available, ie a 32-bit int when you have a 64-bit long. Then use // a temporary or a cast to the mightier type and retrieve the upper bits. // Or you do it bitwise. ;-)
另一个算术运算是类似的。 哎呀，你甚至可以使用stl-functors std :: plus和std :: minus，std :: times和std :: divides …，但是请记住carry。 :)你也可以通过使用加号和减号运算符来实现乘法和除法运算，但是这很慢，因为那样会重新计算你以前在每次迭代中调用加号和减号的计算结果。 有这么简单的任务有很多很好的算法， 使用 维基百科或网络。
当然，你应该实现标准的运算符，如operator<< （只要将value_中的每个值左移n位，从value_.size()-1 …并记住进位:)， operator< – 你甚至可以在这里稍微优化一下，首先检查size()的粗略位数。 等等。 然后通过befriendig std :: ostream operator<<使你的类变得有用。
希望这种方法是有帮助的！
这里有一个完整的部分：[计算机编程的艺术，第2卷：研究数学算法，第4.3节多精度算术，第265-318（ed.3）]。 你可能会在第四章算术中找到其他有趣的材料。
如果你真的不想看另一个实现，你有没有考虑你是什么学习？ 有无数的错误要做，发现那些是有益的，也是危险的。 在确定重要的计算经济和具有适当的存储结构以避免严重的性能问题方面也存在挑战。
一个挑战你的问题：你打算如何测试你的实现，你如何提出证明算法是正确的？
你可能需要另一个实现来测试（不看它是如何实现的），但是除了这个之外，还需要更多的工作来推广，而不需要等待测试。 不要忘记考虑故障模式（内存不足，堆栈过长，运行时间过长等）。
玩的开心！
加法可能不得不在标准线性时间算法中完成
但为了乘法，你可以尝试http://en.wikipedia.org/wiki/Karatsuba_algorithm
一旦你得到了一个数组中的数字的位数，就可以完成和你一样的加法和乘法运算。
有意思的是，在我看到你的问题之前，我刚刚看了一个关于这个视频的视频。 这是链接 。 由混沌通讯大会提供。
不要忘记，你不需要把自己的数字限制在0-9，即使用字节作为数字（0-255），你仍然可以做长时间的算术运算，就像你用十进制数字一样。 你甚至可以使用一个长阵列。
我不相信使用字符串是正确的方式去 – 虽然我从来没有写自己的代码，我认为使用一个基数字类型的数组可能是一个更好的解决方案。 这个想法是，你只是简单地扩展你已经有了相同的方式将CPU扩展一个整数。
例如，如果你有一个结构
typedef struct { int high, low; } BiggerInt;
然后，您可以手动对每个“数字”执行本机操作（在本例中为高和低），注意溢出条件：
BiggerInt add( const BiggerInt *lhs, const BiggerInt *rhs ) { BiggerInt ret; /* Ideally, you'd want a better way to check for overflow conditions */ if ( rhs->high < INT_MAX - lhs->high ) { /* With a variable-length (a real) BigInt, you'd allocate some more room here */ } ret.high = lhs->high + rhs->high; if ( rhs->low < INT_MAX - lhs->low ) { /* No overflow */ ret.low = lhs->low + rhs->low; } else { /* Overflow */ ret.high += 1; ret.low = lhs->low - ( INT_MAX - rhs->low ); /* Right? */ } return ret; }
这是一个简单的例子，但是如何扩展到一个具有可变数量的基类数字类的结构应该是相当明显的。
像其他人说的那样，以老式的方式去做，但是要避免在10号基础上这么做。我建议在65536基础上做所有的事情，然后把东西放在一堆长长的东西里。
如果你的目标体系结构支持BCD（二进制编码的十进制）表示的数字，你可以得到一些你需要做的扩展/加法的硬件支持。 让编译器发出BCD指令是你必须阅读的东西…
摩托罗拉68K系列芯片有这个。 不是说我很苦或什么
看看这里看看GMP如何实现它的算法。
使用你在1至4年级学到的算法。
从那一列开始，然后是十开始，等等。
我的开始将有一个任意大小的整数数组，使用31位和32位作为溢出。
起始者是ADD，然后是MAKE-NEGATIVE，使用2的补码。 之后，减法流畅地进行，一旦你添加/子，一切都是可行的。
可能有更复杂的方法。 但是，这将是数字逻辑的天真方法。
可以尝试执行这样的事情：
http://www.docjar.org/html/api/java/math/BigInteger.java.html
你只需要4位的单个数字0 – 9
所以一个Int值最多允许8位数字。 我决定我会坚持一个字符数组，所以我使用双倍的内存，但对我来说，它只被使用1次。
另外，当把所有的数字存储在一个int中时，它会使它过于复杂，如果有的话，甚至可能会减慢它的速度。
我没有任何速度测试，但看着BigInteger的Java版本，它似乎做了很多工作。
对我来说，我做下面
//Number = 100,000.00, Number Digits = 32, Decimal Digits = 2. BigDecimal *decimal = new BigDecimal("100000.00", 32, 2); decimal += "1000.99"; cout << decimal->GetValue(0x1 | 0x2) << endl; //Format and show decimals. //Prints: 101,000.99
从你的整数字符串中减去48并打印得到大数字的数字。 然后执行基本的数学运算。 否则我会提供完整的解决方案。
C ++类BigInt，使用户能够使用任意的精度整数。 http://sourceforge.net/projects/cpp-bigint/
