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

StackOverflow https://stackoverflow.com/questions/269268

题

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

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

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

有帮助吗？

解决方案

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

  1. 数学运算符：+， - ，/， *，％不要忘记你的班级可能在两边 运营商，运营商可以 链接，那个操作数之一 可以是int，float，double等。

  2. I / O运算符：<！> gt; <！> gt;，<！> lt; <！> lt;这是 你在哪里弄清楚如何正确 从用户输入创建您的类，以及如何将其格式化为输出。

  3. Conversions / Casts：弄清楚 你的big int是什么类型/类 class应该可以转换为，和 如何妥善处理 转换。快速列表会 包括double和float，也可以 include int（有适当的边界 检查）和复杂（假设它 可以处理范围）。

其他提示

一个有趣的挑战。 ：）

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

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

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

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

您可能需要考虑是否要制作固定大小的矢量以及是否要预先分配它。原因是对于不同的操作，您将必须遍历向量的每个元素 - O（n）。您可能想要了解操作的复杂程度，固定的n就是这样。

但现在对某些算法进行操作。您可以在逻辑级别上执行此操作，但我们将使用该神奇的CPU功率来计算结果。但是我们将从Half-andAddAdders的逻辑插图中接替的是它处理进位的方式。例如，考虑如何实施 + =运算符。对于BigInt <！> lt; <！> gt; :: 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<检查粗略的位数。等等。然后通过befriendig std :: ostream size()使你的课变得有用。

希望这种方法有用！

有一个完整的部分：[计算机编程的艺术，第2卷：半数值算法，第4.3节“多精度算术”，第265-318页（第3版）]。您可以在第4章算术中找到其他有趣的材料。

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

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

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

玩得开心！

可能必须在标准线性时间算法中进行添加 但是对于乘法，您可以尝试 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基础上做这一切，然后把东西放在一堆长片中。

使用您在1年级到4年级学到的算法。
从ones列开始，然后是ten，等等。

如果您的目标体系结构支持数字的BCD（二进制编码的十进制）表示，您可以获得一些硬件支持，以便您需要进行长时间的乘法/加法。让编译器发出BCD指令是你必须阅读的内容......

摩托罗拉68K系列芯片就是这样的。不是我很苦或者什么。

我的开始是拥有一个任意大小的整数数组，使用31位，32n'd作为溢出。

启动操作将是ADD，然后是MAKE-NEGATIVE，使用2的补码。在那之后，减法流动很简单，一旦你有add / sub，其他一切都是可行的。

可能有更复杂的方法。但这将是数字逻辑的天真方法。

可以尝试实现这样的事情：

http://www.docjar.org/html/ API / JAVA /数学/ BigInteger.java.html

对于单个数字0 - 9

，您只需要4位

因此，Int Value最多允许8个数字。我决定坚持使用一系列字符，所以我使用了双倍的内存，但对我而言，它只使用了一次。

此外，当将所有数字存储在单个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并打印以获得大数字的数字。 然后执行基本的数学运算。    否则我会提供完整的解决方案。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top