当前位置：文江博客话题详情

如何在C++中实现big int

发布于 2024-07-08 03:51:06 字数 256 浏览 12 评论 0 原文

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

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

情痴 2024-07-15 03:51:07

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

回复收藏 0 原文

﹎☆浅夏丿初晴 2024-07-15 03:51:07

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

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

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.

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.

回复收藏 0 原文

短暂陪伴 2024-07-15 03:51:07

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

回复收藏 0 原文

酒浓于脸红 2024-07-15 03:51:07

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

回复收藏 0 原文

孤单情人 2024-07-15 03:51:07

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

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

回复收藏 0 原文

挽清梦 2024-07-15 03:51:07

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

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

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

回复收藏 0 原文

小草泠泠 2024-07-15 03:51:07

可以尝试实现这样的东西：

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

Could try implementing something like this:

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

You'd only need 4 bits for a single digit 0 - 9

So an Int Value would allow up to 8 digits each. I decided i'd stick with an array of chars so i use double the memory but for me it's only being used 1 time.

Also when storing all the digits in a single int it over-complicates it and if anything it may even slow it down.

I don't have any speed tests but looking at the java version of BigInteger it seems like it's doing an awful lot of work.

For me I do the below

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

回复收藏 0 原文

触ぅ动初心 2024-07-15 03:51:07

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

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

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

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

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

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

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

回复收藏 0 原文

可是我不能没有你 2024-07-15 03:51:07

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

回复收藏 0 原文

始终不够爱げ你 2024-07-15 03:51:06

一个有趣的挑战。 :)

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

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

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

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

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

现在介绍一些对数字进行操作的算法。您可以在逻辑级别上执行此操作，但我们将使用神奇的 CPU 能力来计算结果。但我们将从 Half- 和 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< /code>...哦，记住进位:)，operator< - 您甚至可以在这里进行一些优化，首先使用 size() 检查大致的位数。等等。然后通过 befriendig std::ostream operator<< 让你的类变得有用。

希望这个方法有帮助！

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.

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.

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.

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.

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, use wikipedia or the web.

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

Hope this approach is helpful!

回复收藏 0 原文

瞳孔里扚悲伤 2024-07-15 03:51:06

大 int 类需要考虑的事项：

数学运算符：+、-、/、
*, % 不要忘记你的班级可能位于
运算符，运算符可以是
链接的，操作数之一
可以是 int、float、double 等。
I/O 运算符：>>、<< 这是
在那里你知道如何正确地
根据用户输入创建您的类，以及如何格式化它以进行输出。
转换/转换：弄清楚
你的大整数是什么类型/类
类应该可以转换为，并且
如何正确处理
转换。一个快速列表将
包括 double 和 float，并且可能
包括 int （有适当的界限
检查）和复杂（假设
可以处理该范围）。