c++ - 如何在 C++ 中实现大 int

Question

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

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

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

score 46 · Accepted Answer

一个有趣的挑战。:)

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

考虑数据类型“int”的二进制性质。考虑使用简单的二进制运算来模拟 CPU 中的电路在添加事物时所做的事情。如果您有更深入的兴趣，请考虑阅读有关半加器和全加器的维基百科文章。你会做类似的事情，但你可以降到最低水平 - 但是因为懒惰，我想我会放弃并找到一个更简单的解决方案。

但在讨论任何关于加、减、乘的算法细节之前，让我们先了解一些数据结构。当然，一种简单的方法是将内容存储在 std::vector 中。

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

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

但是现在来一些关于对数字进行操作的算法。您可以在逻辑级别上执行此操作，但我们将使用这种神奇的 CPU 能力来计算结果。但是我们将从 Half-Adders 和 FullAdders 的逻辑说明中接替的是它处理进位的方式。例如，考虑如何实现+= 运算符。对于 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 函子 std::plus 和 std::minus，std::times 和 std::divides，...，但请注意进位。:) 您还可以通过使用加号和减号运算符来实现乘法和除法，但这非常慢，因为这会重新计算您在每次迭代中之前调用加号和减号时已经计算的结果。对于这个简单的任务，有很多很好的算法，使用维基百科或网络。

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

希望这种方法有帮助！

score 37 · Accepted Answer

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

数学运算符：+、-、/、*、% 不要忘记您的类可能位于运算符的任一侧，运算符可以链接，其中一个操作数可以是 int、float、double 等.
I/O 操作符：>>、<< 在这里，您可以了解如何根据用户输入正确创建类，以及如何格式化输出。
转换/强制转换：弄清楚你的大 int 类应该转换成哪些类型/类，以及如何正确处理转换。快速列表将包括 double 和 float，并且可能包括 int（带有适当的边界检查）和 complex（假设它可以处理范围）。

score 29 · Accepted Answer

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

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

给你的一个挑战问题：你打算如何测试你的实现以及你打算如何证明它的算术是正确的？

您可能希望对另一个实现进行测试（而不看它是如何做到的），但是要进行概括而不期望进行令人痛苦的测试水平，这将需要更多的时间。不要忘记考虑故障模式（内存不足问题、堆栈不足、运行时间过长等）。

玩得开心！

score 6 · Accepted Answer

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

score 5 · Accepted Answer

一旦您在数组中获得了数字的数字，您就可以像普通手写一样进行加法和乘法运算。

score 4 · Accepted Answer

不要忘记您不需要将自己限制为 0-9 作为数字，即使用字节作为数字 (0-255)，您仍然可以像处理十进制数字一样进行长手算术。你甚至可以使用一个 long 数组。

score 3 · Accepted Answer

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

这是一个有点简单的例子，但它应该是相当明显的，如何扩展到一个结构，该结构具有你正在使用的任何基本数字类的可变数量。

score 2 · Accepted Answer

使用你在一年级到四年级学到的算法。
从个位列开始，然后是十位，依此类推。

score 2 · Accepted Answer

就像其他人说的那样，以老式的长手方式进行操作，但不要在基数 10 中执行此操作。我建议在基数 65536 中执行所有操作，并将内容存储在长数组中。

score 1 · Accepted Answer

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

摩托罗拉 68K 系列芯片具有此功能。并不是说我很苦或什么。

score 0 · Accepted Answer

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

起始操作将是 ADD，然后是 MAKE-NEGATIVE，使用 2 的补码。在那之后，减法变得微不足道，一旦你有了加法/减法，其他一切都是可行的。

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

score 0 · Accepted Answer

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

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

单个数字 0 - 9 只需要 4 位

因此，一个 Int Value 每个最多允许 8 位数字。我决定坚持使用一组字符，所以我使用双倍的内存，但对我来说它只被使用了 1 次。

此外，当将所有数字存储在一个 int 中时，它会使它过于复杂，如果有的话，它甚至可能会减慢它的速度。

我没有进行任何速度测试，但查看 Java 版本的 BigInteger 似乎它做了很多工作。

对我来说，我做以下

//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

score 0 · Accepted Answer

计算机硬件提供了存储整数和对其进行基本算术运算的便利；通常这仅限于某个范围内的整数（例如，最多 2^{64}-1）。但是可以通过程序支持更大的整数；下面是一种这样的方法。

使用位置数字系统（例如流行的 base-10 数字系统），任何任意大的整数都可以表示为base中的数字B序列。因此，此类整数可以存储为 32 位整数数组，其中每个数组元素都是 base 中的一个数字B=2^{32}。

我们已经知道如何使用带有 base 的数字系统来表示整数B=10，以及如何在这个系统中执行基本的算术运算（加、减、乘、除等）。执行这些操作的算法有时被称为教科书算法。我们可以将这些 Schoolbook 算法应用（进行一些调整）到任何 base B，因此可以对 base 中的大整数实现相同的操作B。

要将这些算法应用于任何 base B，我们需要进一步了解它们并处理以下问题：

在这些算法中产生的各种中间值的范围是多少。
迭代加法和乘法产生的最大进位是多少。
如何估计长除法中的下一个商数。

（当然，可以有其他算法来执行这些操作）。

可以在此处（初始章节）、此处（由我编写）和此处找到一些算法/实现细节。

score -1 · Accepted Answer

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

c++ - 如何在 C++ 中实现大 int

14 回答 14

Related

Reference