c++ - BigInt 计算器吐出稍微错误的结果

Question

因此，对于我的作业，我必须创建一个计算器，该计算器可以处理最长 256 个字符的大整数。我目前要做的任务是让它与更大的数字相乘。 DIGITS 是每个 Bigint 类的数字限制，目前为了调试设置为 20，但将增加到 256

当进行类似 25 * 137 的计算时，我得到的答案是 3285，而它应该是 3425。当我查看为调试而设置的 cout 时，i 循环的第一次迭代完美运行并将 685 添加到总和为 5 * 137，因此效果很好。然而，当它到达必须执行 i 循环的第二次迭代的位置时，它是 20 * 137，它得到的答案是错误的，我无法弄清楚为什么。我有一种暗示，这与进位是两位数 (14) 有关，但我仍然无法真正弄清楚如何解决它。

明显有问题的主要实现是在 bigint 类的 * 运算符中。我知道这与 << 或 >> 运算符无关，因为它们非常适合加法和减法。

bigint 类的完整代码如下:

#include <iostream>
#include <string>
#include "Bigint.h"
#include <cmath>

using namespace std;

Bigint::Bigint()
{
    for (int i = DIGITS-1; i >= 0; --i) {
        digits_[i] = 0;
    }
}

ostream& operator<< (ostream& out, const Bigint& n)
{

    string s = "";
    bool found = false;
    for (int i = DIGITS - 1; i >= 0; --i) {
        if(n.digits_[i] > 0) {
            found = true;
        }
        if(n.digits_[i] != 0 || found == true) {
            s += char(n.digits_[i] + '0');
        }
    }
    if (s == "") {
        s = "0";
    }
    return out << s;
}

istream& operator>> (istream& in, Bigint& n)
{
    // Extracts full-length number (does not work for any other length).
    // All characters are assumed to be valid digits.
    //
    string s;
    if (in >> s) {
        for (int i = 0; i < DIGITS; ++i) {
            n.digits_[i] = i < s.length() ? s[s.length() - 1 - i] - '0' : 0;
        }
    }
    return in;
}

Bigint operator+ (const Bigint& n1, const Bigint& n2)
{
    Bigint ret;
    int cur_carry = 0;
    for(int i = 0; i < DIGITS; ++i) {
        int n1_digit = n1.get(i);
        int n2_digit = n2.get(i);
        if(n1_digit < 0 || n1_digit > 9) {
            n1_digit = 0;
        }
        if(n2_digit < 0 || n2_digit > 9) {
            n2_digit = 0;
        }
        //printf("n1 : %d\n", n1_digit);
        //printf("n2 : %d\n", n2_digit);
        int sum = n1_digit + n2_digit + cur_carry;
        //cout << "sum : " << sum << endl;
        cur_carry = Bigint::getCarry(sum);
        //cout << "new carry : " << cur_carry << endl;
        ret.set(i, Bigint::getDigitValue(sum));
        //cout << "Set : " << i << "," << Bigint::getDigitValue(sum) << endl;
    }
    return ret;
}

Bigint operator* (const Bigint& n1, const Bigint& n2)
{
    Bigint ret;
    //int borrowed = 0;
    Bigint sum;
    for(int i = 0; i < DIGITS ; i++){
        int n1_digit = n1.get(i);
        //cout << "n2: " << n2_digit << endl;
        Bigint temp;

        if(n1_digit < 0 || n1_digit > 9) {
            n1_digit = 0;
        }

        int carry = 0;

        for (int j = 0; j < DIGITS ; j++){
            int val = n1_digit * (pow(10, i)) * n2.get(j);
            cout << "n1: " << n1_digit << endl;
            cout << "n2: " << n2.get(j) << endl;

            if(carry != 0){
                temp.set(j, (Bigint::getDigitValue(val)) + carry);
                cout << "Carry was " << carry << ", now set 0" << endl;
                cout << "value to set: " << (Bigint::getDigitValue(val)) + carry << endl;
                carry = 0;
            }
            else if(carry == 0){
                temp.set(j, Bigint::getDigitValue(val));
                cout << "value to set: " << (Bigint::getDigitValue(val))<< endl;
            }

            carry = (Bigint::getCarry(val) + carry);
            cout << "carry: " << carry << endl;
        }
        cout << "Sum before adding temp: " << sum << endl;
        sum = sum + temp;
        cout << "Sum after adding temp: " << sum << endl;


    }

    ret = sum;
    return ret; // Only correct when n2 equals 1.
}

int Bigint::get(int pos) const {
    //Return address of digit for reading
    int ret = digits_[pos];
    return ret;
}

void Bigint::set(int pos, int val) {
    this->digits_[pos] = val;
}

int Bigint::getCarry(int val) {
    //Integer division, always floors
    return val/10;
}

int Bigint::getDigitValue(int val) {
    return val % 10;
}

头文件:

#ifndef BIGINT_H_
#define BIGINT_H_

#define DIGITS 20

class Bigint
{
  public:

    /**
     * Creates a Bigint initialised to 0.
     */
    Bigint();

    /**
     * Inserts n into stream or extracts n from stream.
     */
    friend std::ostream& operator<< (std::ostream &out, const Bigint& n);
    friend std::istream& operator>> (std::istream &in, Bigint& n);

    /**
     * Returns the sum, difference, product, or quotient of n1 and n2.
     */
    friend Bigint operator* (const Bigint& n1, const Bigint& n2);
    friend Bigint operator+ (const Bigint& n1, const Bigint& n2);

    int get(int pos) const;
    void set(int pos, int val);

    static int getCarry(int val);
    static int getDigitValue(int val);

  private:
    int digits_[DIGITS];
};

#endif // BIGINT_H_

主要内容:

#include <iostream>
#include "Bigint.h"

using namespace std;

int main(int argc, char *argv[]) 
{
    Bigint n1, n2;
    char op;

    while (cin >> n1 >> op >> n2) {
        switch (op) {
        case '+' :
            cout << n1 + n2 << endl;
            break;
        case '*' :
            cout << n1 * n2 << endl;
            break;
        }
    }



    return 0;
}
}

Answer 1

你不应该使用这条线 int val = n1_digit * (pow(10, i)) * n2.get(j); 因为它会给出整数溢出，因为你正在使用 bigintger 而是使用乘数中的数字并在结果后面添加零。

要添加的零的数量将取决于乘数位的位置，您可以从这个循环中找到变量 i for(int i = 0; i < DIGITS ; i++)在重载的 * 函数中