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

问题描述 投票：78回答：13

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

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

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

c++ biginteger bignum largenumber
13个回答
35
投票

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

  1. 数学运算符：+， - ，/，*，％不要忘记你的类可能在运算符的两边，运算符可以被链接，其中一个操作数可以是int，float，double等。
  2. I / O运算符：>>，<<这是您在何处从用户输入中正确创建类，以及如何将其格式化为输出。
  3. 转换/转换：确定您的大型int类应该可以转换为哪些类型/类，以及如何正确处理转换。快速列表将包括double和float，并且可以包括int（具有适当的边界检查）和复杂（假设它可以处理范围）。
1
投票

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

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

0
投票

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

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

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

0
投票

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

http://www.docjar.org/html/api/java/math/BigInteger.java.html

对于单个数字0 - 9，您只需要4位

因此，Int值最多允许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
-1
投票

从您的整数字符串中减去48并打印以获得大数字的数字。然后执行基本的数学运算。否则我会提供完整的解决方案。

43
投票

一个有趣的挑战。 :)

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

考虑数据类型“int”的二进制特性。考虑使用简单的二进制操作来模拟CPU添加内容时电路中的操作。如果您对此更感兴趣，请考虑阅读this wikipedia article on half-adders and full-adders。你会做类似的事情，但你可以降低水平 - 但是懒惰，我以为我只是放弃并找到一个更简单的解决方案。

但在进入任何关于加，减，乘的算法细节之前，让我们找一些数据结构。当然，一种简单的方法是将事物存储在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，...，但请注意进位。 :)您也可以使用加号和减号运算符来实现乘法和除法，但这非常慢，因为这会重新计算您在先前调用每次迭代中加号和减号时计算的结果。这个简单的任务有很多好的算法，use wikipedia或网络。

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

希望这种方法很有帮助！

26
投票

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

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

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

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

玩得开心！

6
投票

添加可能必须在标准线性时间算法中完成 但对于乘法，你可以尝试http://en.wikipedia.org/wiki/Karatsuba_algorithm

5
投票

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

4
投票

不要忘记，您不需要将自己限制为0-9作为数字，即使用字节作为数字（0-255），您仍然可以像对十进制数字一样进行长手运算。你甚至可以使用长数组。

3
投票

我不相信使用字符串是正确的方法 - 尽管我自己从未编写代码，但我认为使用基本数字类型的数组可能是更好的解决方案。我们的想法是，您只需扩展已经获得的内容，就像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;
}

这是一个简单的例子，但是如何扩展到一个具有可变数量的任何基础数字类的结构应该是相当明显的。

2
投票

像其他人说的那样，用老式的长手方式做，但是不要在基础10中做这一切。我建议在基础65536中完成所有操作，并将数据存储在一系列多头中。

1
投票

使用您在1到4年级学到的算法。 从ones列开始，然后是tens，依此类推。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.