如何在 C++ 中实现 big int

How to implement big int in C++

提问by oneself

I'd like to implement a big int class in C++ as a programming exercise—a class that can handle numbers bigger than a long int. I know that there are several open source implementations out there already, but I'd like to write my own. I'm trying to get a feel for what the right approach is.

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

I understand that the general strategy is get the number as a string, and then break it up into smaller numbers (single digits for example), and place them in an array. At this point it should be relatively simple to implement the various comparison operators. My main concern is how I would implement things like addition and multiplication.

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

I'm looking for a general approach and advice as opposed to actual working code.

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

采纳答案by Harper Shelby

Things to consider for a big int class:

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

1. Mathematical operators: +, -, /, *, % Don't forget that your class may be on either side of the operator, that the operators can be chained, that one of the operands could be an int, float, double, etc.

2. I/O operators: >>, << This is where you figure out how to properly create your class from user input, and how to format it for output as well.

3. Conversions/Casts: Figure out what types/classes your big int class should be convertible to, and how to properly handle the conversion. A quick list would include double and float, and may include int (with proper bounds checking) and complex (assuming it can handle the range).

1. 数学运算符：+、-、/、*、% 不要忘记您的类可能位于运算符的任一侧，运算符可以链接，其中一个操作数可以是 int、float、double 等.

2. I/O 操作符：>>、<< 在这里您可以了解如何根据用户输入正确创建您的类，以及如何将其格式化以进行输出。

3. 转换/转换：弄清楚您的 big int 类应该转换为哪些类型/类，以及如何正确处理转换。快速列表将包括 double 和 float，并且可能包括 int（具有适当的边界检查）和 complex（假设它可以处理范围）。

回答by mstrobl

A fun challenge. :)

一个有趣的挑战。:)

I assume that you want integers of arbitrary length. I suggest the following approach:

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

Consider the binary nature of the datatype "int". Think about using simple binary operations to emulate what the circuits in your CPU do when they add things. In case you are interested more in-depth, consider reading this wikipedia article on half-adders and full-adders. You'll be doing something similar to that, but you can go down as low level as that - but being lazy, I thought I'd just forego and find a even simpler solution.

考虑数据类型“int”的二进制性质。考虑使用简单的二进制运算来模拟 CPU 中的电路在添加东西时所做的事情。如果您有兴趣更深入地了解，请考虑阅读这篇关于 half-adders 和 full-adders 的维基百科文章。你会做类似的事情，但你可以降到最低级别 - 但我很懒，我想我会放弃并找到一个更简单的解决方案。

But before going into any algorithmic details about adding, subtracting, multiplying, let's find some data structure. A simple way, is of course, to store things in a std::vector.

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

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

You might want to consider if you want to make the vector of a fixed size and if to preallocate it. Reason being that for diverse operations, you will have to go through each element of the vector - O(n). You might want to know offhand how complex an operation is going to be and a fixed n does just that.

您可能需要考虑是否要制作固定大小的向量以及是否要预先分配它。原因是对于不同的操作，您必须遍历向量的每个元素 - O(n)。您可能想立即知道操作将有多复杂，而固定的 n 正好可以做到这一点。

But now to some algorithms on operating on the numbers. You could do it on a logic-level, but we'll use that magic CPU power to calculate results. But what we'll take over from the logic-illustration of Half- and FullAdders is the way it deals with carries. As an example, consider how you'd implement the += operator. For each number in BigInt<>::value_, you'd add those and see if the result produces some form of carry. We won't be doing it bit-wise, but rely on the nature of our BaseType (be it long or int or short or whatever): it overflows.

但是现在要介绍一些对数字进行运算的算法。您可以在逻辑级别上执行此操作，但我们将使用这种神奇的 CPU 能力来计算结果。但是我们将从 Half- 和 FullAdders 的逻辑说明中接管的是它处理进位的方式。例如，考虑如何实现+= 运算符。对于 BigInt<>::value_ 中的每个数字，您将它们相加并查看结果是否产生某种形式的进位。我们不会按位来做，而是依赖于我们的 BaseType 的性质（无论是 long 或 int 还是 short 或其他）：它会溢出。

Surely, if you add two numbers, the result must be greater than the greater one of those numbers, right? If it's not, then the result overflowed.

当然，如果您将两个数字相加，结果一定大于这些数字中较大的一个，对吗？如果不是，则结果溢出。

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. ;-)

The other arithmetic operation go analogous. Heck, you could even use the stl-functors std::plus and std::minus, std::times and std::divides, ..., but mind the carry. :) You can also implement multiplication and division by using your plus and minus operators, but that's very slow, because that would recalculate results you already calculated in prior calls to plus and minus in each iteration. There are a lot of good algorithms out there for this simple task, usewikipediaor the web.

其他算术运算类似。哎呀，您甚至可以使用 stl 函子 std::plus 和 std::minus、std::times 和 std::divides，...，但要注意进位。:) 您还可以使用加号和减号运算符来实现乘法和除法，但这非常慢，因为这会重新计算您在每次迭代中之前对加号和减号的调用中已经计算过的结果。对于这个简单的任务，有很多很好的算法，使用维基百科或网络。

And of course, you should implement standard operators such as operator<<(just shift each value in value_ to the left for n bits, starting at the value_.size()-1... oh and remember the carry :), operator<- you can even optimize a little here, checking the rough number of digits with size()first. And so on. Then make your class useful, by befriendig std::ostream operator<<.

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

Hope this approach is helpful!

希望这个方法有帮助！

回答by orcmid

There's a complete section on this: [The Art of Computer Programming, vol.2: Seminumerical Algorithms, section 4.3 Multiple Precision Arithmetic, pp. 265-318 (ed.3)]. You may find other interesting material in Chapter 4, Arithmetic.

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

If you really don't want to look at another implementation, have you considered what it is you are out to learn? There are innumerable mistakes to be made and uncovering those is instructive and also dangerous. There are also challenges in identifying important computational economies and having appropriate storage structures for avoiding serious performance problems.

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

A Challenge Question for you: How do you intend to test your implementation and how do you propose to demonstrate that it's arithmetic is correct?

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

You might want another implementation to test against (without looking at how it does it), but it will take more than that to be able to generalize without expecting an excrutiating level of testing. Don't forget to consider failure modes (out of memory problems, out of stack, running too long, etc.).

您可能希望针对另一个实现进行测试（无需查看它是如何执行的），但是要能够在不期望进行令人难以忍受的测试水平的情况下进行概括，还需要做更多的工作。不要忘记考虑故障模式（内存不足问题、堆栈外问题、运行时间过长等）。

Have fun!

玩得开心！

回答by Aditya Mukherji

addition would probably have to be done in the standard linear time algorithm
but for multiplication you could try http://en.wikipedia.org/wiki/Karatsuba_algorithm

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

回答by Bill the Lizard

Once you have the digits of the number in an array, you can do addition and multiplication exactly as you would do them longhand.

一旦您在数组中获得了数字的数字，您就可以完全按照手写方式进行加法和乘法。

回答by Lazarus

Don't forget that you don't need to restrict yourself to 0-9 as digits, i.e. use bytes as digits (0-255) and you can still do long hand arithmetic the same as you would for decimal digits. You could even use an array of long.

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

回答by hark

I'm not convinced using a string is the right way to go -- though I've never written code myself, I think that using an array of a base numeric type might be a better solution. The idea is that you'd simply extend what you've already got the same way the CPU extends a single bit into an integer.

我不相信使用字符串是正确的方法——尽管我自己从未编写过代码，但我认为使用基本数字类型的数组可能是更好的解决方案。这个想法是，您只需扩展您已经拥有的内容，就像 CPU 将单个位扩展为整数一样。

For example, if you have a structure

例如，如果您有一个结构

typedef struct {
    int high, low;
} BiggerInt;

You can then manually perform native operations on each of the "digits" (high and low, in this case), being mindful of overflow conditions:

然后，您可以对每个“数字”（在本例中为高和低）手动执行本机操作，注意溢出情况：

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;
}

It's a bit of a simplistic example, but it should be fairly obvious how to extend to a structure that had a variable number of whatever base numeric class you're using.

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

回答by Tim

Use the algorithms you learned in 1st through 4th grade.
Start with the ones column, then the tens, and so forth.

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

回答by Eclipse

Like others said, do it to old fashioned long-hand way, but stay away from doing this all in base 10. I'd suggest doing it all in base 65536, and storing things in an array of longs.

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

回答by dmckee --- ex-moderator kitten

If your target architecture supports BCD (binary coded decimal) representation of numbers, you can get some hardware support for the longhand multiplication/addition that you need to do. Getting the compiler to emit BCD instruction is something you'll have to read up on...

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

The Motorola 68K series chips had this. Not that I'm bitter or anything.

摩托罗拉 68K 系列芯片有这个。不是说我很苦或什么。