0

我是 C++ 新手并试图创建一个“BigInt”类。我决定将大部分实现基于将数字读入向量。

到目前为止，我只为输入字符串编写了复制构造函数。

Largenum::Largenum(std::string input)
{
 for (std::string::const_iterator it = input.begin(); it!=input.end(); ++it)
    {
      number.push_back(*it- '0');
    }
}

我遇到的问题是加法功能。我创建了一个函数，经过几次测试后似乎可以工作，但正如您所见，它的效率非常低。我有 2 个不同的向量，例如：

std::vector<int> x = {1,3,4,5,9,1};
std::vector<int> y = {2,4,5,6};

我想解决这个问题的方法是在较短的之前添加 0，在这种情况下 y 向量使两个向量具有相同的大小，例如：

x = {1,3,4,5,9,1};
y = {0,0,2,4,5,6};

然后使用基本样式添加添加它们。

我不想在向量 Y 前面添加 0，因为它会很慢。我目前的解决方案是反转向量，然后 push_back 适当数量的 0，然后将其反转回来。这可能比简单地插入前面似乎要慢，我还没有测试过。

问题是，在我对向量进行所有加法并 push_back 结果之后。我留下了一个反向向量，我需要再次使用反向！必须有比我的方法更好的方法，但我一直在寻找它。理想情况下，我也会制作 A const 。这是函数的代码：

Largenum Largenum::operator+(Largenum &A)
{
    bool carry = 0; 
    Largenum sum;                

    std::vector<int>::size_type max = std::max(A.number.size(), this->number.size());
    std::vector<int>::size_type diff = std::abs (A.number.size()-this->number.size());

    if (A.number.size()>this->number.size())
    {
        std::reverse(this->number.begin(), this->number.end());
        for (std::vector<int>::size_type i = 0; i<(max-diff); ++i) this->number.push_back(0);
        std::reverse(this->number.begin(), this->number.end());
    }
    else if (this->number.size() > A.number.size())
    {
        std::reverse(A.number.begin(), A.number.end());
        for (std::vector<int>::size_type i = 0; i<(max-diff); ++i) A.number.push_back(0);
        std::reverse(A.number.begin(), A.number.end());
    }
    for (std::vector<int>::size_type i = max; i!=0; --i)
    {
        int num = (A.number[i-1] + this->number[i-1] + carry)%10;
        sum.number.push_back(num);
        (A.number[i-1] + this->number[i-1] + carry >= 10) ? carry = 1 : carry = 0;
    }
    if (carry) sum.number.push_back(1);

   reverse(sum.number.begin(), sum.number.end());

   return sum;
}

如果有人有任何很棒的输入，这是我第一个在 C++ 中使用类的程序，它相当压倒性。

4

2 回答 2

1

我认为您的功能非常接近我见过的最佳功能。仍然有一些建议如何改进它：

  • 十进制数字系统效率很低，大数字有很多数字。最好使用更高的基数来减少必须添加的位数。以人类可读的表示形式读取和写入这些数字会有点困难，但是您将多次优化操作，因为您将拥有更少的数字。
  • 在实现大整数时，我以相反的顺序表示它们，因此我在索引为 0 的位置有最低有效数字，而在数组末尾有最高有效数字。这样，当进位强制您添加一个新数字时，您只执行 a push_back，而不是整个反向。
于 2013-06-19T14:04:47.367 回答
0

一个问题：现代处理器上的整数模数相当慢，即使与分支错误预测相比也是如此。与其做一个显式的 %10，不如在你的第三个 for 循环中试试这个：

int num = A.number[i-1] + this->number[i-1] + carry;
if(num >= 10)
{
    carry = 1;
    num -= 10;
}
else
{
    carry = 0;
}
sum.number.push_back(num);
于 2013-06-20T12:28:00.770 回答