如何在C++中实现大型int

我想在C++中实现一个大的int类作为编程练习 - 一个可以处理大于long int的数字的类.我知道已经有几个开源实现,但我想写自己的.我试图了解正确的方法是什么.

我知道一般策略是将数字作为字符串,然后将其分解为较小的数字(例如,单个数字),并将它们放在一个数组中.此时,实现各种比较运算符应该相对简单.我主要担心的是如何实现添加和乘法等功能.

我正在寻找一种通用的方法和建议,而不是实际的工作代码.

1> mstrobl..：

---

一个有趣的挑战.:)

我假设你想要任意长度的整数.我建议采用以下方法:

考虑数据类型"int"的二进制特性.考虑使用简单的二进制操作来模拟CPU添加内容时电路中的操作.如果您对此更感兴趣,请考虑阅读有关半加器和全加器的维基百科文章.你会做类似的事情,但你可以降低水平 - 但是懒惰,我以为我只是放弃并找到一个更简单的解决方案.

但在进入任何关于加,减,乘的算法细节之前,让我们找一些数据结构.当然,一种简单的方法是将事物存储在std :: vector中.

template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};

您可能想要考虑是否要生成固定大小的向量以及是否要预先分配它.原因是对于不同的操作,您将必须遍历向量的每个元素 - O(n).您可能想知道操作的复杂程度,固定的n就是这样.

但现在对一些算法进行操作数字.您可以在逻辑级别上执行此操作,但我们将使用该神奇的CPU功率来计算结果.但是我们将从Half-andAddAdders的逻辑插图中接替的是它处理进位的方式.例如,考虑如何实现+ =运算符.对于BigInt <> :: value_中的每个数字,您需要添加它们并查看结果是否产生某种形式的进位.我们不会按顺序执行,而是依赖于BaseType的性质(无论是long还是int或short或者其他):它会溢出.

当然,如果添加两个数字,结果必须大于这些数字中的较大数字,对吧？如果不是,则结果溢出.

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, i.e. 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,...,但请注意进位.:)您也可以使用加号和减号运算符来实现乘法和除法,但这非常慢,因为这会重新计算您在先前调用每次迭代中加号和减号时计算的结果.这个简单的任务有很多好的算法,使用 维基百科或网络.

当然,您应该实现标准运算符,例如operator<<(只需将value_中的每个值向左移动n位,从value_.size()-1... 开始并记住进位:),operator<- 您甚至可以优化一点,检查size()第一个粗略的位数.等等.然后通过befriendig std :: ostream让你的课变得有用operator<<.

希望这种方法很有帮助!

---

"int"(如签名)是一个坏主意.溢出的标准未定义行为使得逻辑正确(如果不是不可能)变得困难,至少是可移植的.但是,很容易使用无符号整数进行二进制补码,其中溢出行为严格定义为给出模2 ^ n结果.

2> Harper Shelb..：

---

大型int类需要考虑的事项:

数学运算符:+, - ,/,*,%不要忘记你的类可能在运算符的两边,运算符可以被链接,其中一个操作数可以是int,float,double等.

I/O运算符:>>,<<这是您了解如何从用户输入正确创建类的地方,以及如何将其格式化为输出.

转换/转换:确定您的大型int类应该可以转换为哪些类型/类,以及如何正确处理转换.快速列表将包括double和float,并且可以包括int(具有适当的边界检查)和复杂(假设它可以处理范围).

---

@Dave您仍然可以为位移操作定义<<和>>以及流的I/O ...

---

对于整数,运算符<<和>>是位移操作.将它们解释为I/O将是糟糕的设计.

---

@Dave：除了标准的C ++之外，将operator <<和operator >>与iostream一起用于I / O。

3> orcmid..：

---

这里有一个完整的部分:[计算机编程的艺术,第2卷:半数值算法,第4.3节"多精度算术",第265-318页(第3版)].您可以在第4章算术中找到其他有趣的材料.

如果你真的不想看另一个实现,你有没有考虑过你要学习什么？有无数的错误要做,发现这些错误是有益的,也是危险的.在识别重要的计算经济性和具有适当的存储结构以避免严重的性能问题方面也存在挑战.

挑战问题:你打算如何测试你的实现？你如何建议证明它的算法是正确的？

您可能希望另一个实现进行测试(不考虑它是如何实现的),但是如果能够概括而不期待一个令人厌恶的测试级别,则需要更多的实现.不要忘记考虑故障模式(内存不足,堆栈外,运行时间过长等).

玩得开心!

4> Aditya Mukhe..：

---

可能必须在标准线性时间算法中
进行加法,但是对于乘法,您可以尝试http://en.wikipedia.org/wiki/Karatsuba_algorithm

5> Bill the Liz..：

---

一旦你有一个数组中的数字的数字,你可以完全像你想象的那样进行加法和乘法.