如何在C++中实现大int

有趣的挑战。:)

考虑数据类型“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能力来计算结果。但是我们将从半加法器和全加法器的逻辑图中接管的是它处理进位的方式。作为一个例子,考虑如何实现 . 对于BigInt中的每个数字<>::然后,你把这些加起来,看看结果是否会产生某种形式的进位。我们不会一点一点地这样做,而是依赖于我们的基类型的性质(无论是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,…,但要注意进位。:)您还可以通过使用加号和减号运算符实现乘法和除法,但这非常慢,因为这将重新计算您在每次迭代中调用加号和减号时已经计算过的结果。对于这个简单的任务,有很多好的算法, use wikipedia 或者网络。

当然,您应该实现标准操作符,例如 operator<< (只需将value_u中的每个值向左移动n位,从 value_.size()-1 ... 哦,记住随身携带:), operator< -您甚至可以在这里进行一些优化,使用 size() 第一等等然后,通过与std::ostream交朋友,使您的类变得有用 操作员<&书信电报;

一个大的int类需要考虑的事情:

1. 运算符,该运算符可以是 链式的,其中一个操作数 可以是int、float、double等。

2. I/O操作员:>><&书信电报;这是 在那里你可以找到正确的方法 从用户输入创建类,以及如何将其格式化为输出。

3. 转换/强制转换:计算出 你的大整数是什么类型/类 类应可转换为,并且 如何正确处理这些问题 转变一份简单的清单会很有用 包括双重和浮动,并且可以 包含int(具有适当的边界 检查)和复杂(假设为

这方面有一个完整的章节:[计算机编程的艺术,第2卷:半数值算法,第4.3节多精度算法,第265-318页(第3版)]。你可以在第四章“算术”中找到其他有趣的材料。

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

一个挑战性的问题:您打算如何测试您的实现,以及您打算如何证明它的算法是正确的?

您可能希望测试另一个实现(不考虑它是如何实现的),但要想在不期望测试达到令人满意的水平的情况下进行推广,需要更多的时间。不要忘记考虑失效模式(内存不足、堆栈不足、运行时间过长等)。

玩得高兴

可能必须在标准线性时间算法中进行加法
http://en.wikipedia.org/wiki/Karatsuba_algorithm

一旦你在一个数组中有了数字,你就可以像直接做加法和乘法一样做加法和乘法。

不要忘记,您不需要将自己限制为数字0-9,即使用字节作为数字(0-255),并且您仍然可以执行与十进制数字相同的长时间算术。您甚至可以使用一个长数组。

例如,如果您有一个结构

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进制来做这一切。我建议在Base65536中完成这一切,并以long数组存储内容。

如果您的目标体系结构支持数字的BCD(二进制编码的十进制)表示,那么您可以获得一些硬件支持,以实现所需的直接乘法/加法。让编译器发出BCD指令是您必须仔细阅读的内容。。。

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

起始op是ADD,然后使用2的补码使其为负。在那之后,减法的流程很简单,一旦你有了add/sub,其他的一切都是可行的。

可以尝试实现如下内容:

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

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

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

此外,当将所有数字存储在一个整数中时,它会使它变得过于复杂,甚至可能会减慢速度。

我没有任何速度测试,但看看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

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

使用 位置数制 (例如,流行的10进制数字系统),任何任意大的整数都可以表示为 在基地 B B=2^{32} .

我们已经知道如何用带基的数制来表示整数 B=10 B B .

B

• 在这些算法中产生的各种中间值的范围是多少。

• 如何估计长除法中的下一个商位数。

(当然,可以使用其他算法来执行这些操作)。

可以找到一些算法/实现细节 here here 和 here

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