时间戳

首页 > 解决方案 > BigInt 乘法和减法错误

c++ - BigInt 乘法和减法错误

问题描述

我的任务是我必须创建一个可以处理最长 256 个字符的大整数的计算器。我遇到了错误，无法将某些减法数字如何工作（例如 23456 - 13141= 10315）进行倍数以及奇怪的问题，但是任何其他减法（例如 6 - 5）都不起作用。我很困惑为什么会这样。

完整代码如下

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

using namespace std; 

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

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

ostream& operator<< (ostream& out, const Bigint& n) 
{
    string s = "";
    int leadingZeros = 0;

    for (int i = DIGITS-1; i >= 0 ; --i) { 

        if(n.digits_[i] != 0){      
            leadingZeros = 1;
        }

        if(leadingZeros == 1){
            s += char(n.digits_[i] + '0'); 
        }
    }
    return out << s;
}

istream& operator>> (istream& in, Bigint& n)
{

    string s;
    if (in >> s) {

        int length = s.length(); 
        int i;
        for (i = 0; i < DIGITS && i < length; ++i) {
            n.digits_[i] = int(s[length-1 - i] - '0'); 
        }
    }
    return in;
}

Bigint operator+ (const Bigint& n1, const Bigint& n2)
{
    Bigint add;
    int carry = 0, sum = 0;

    for(int i=0; i < DIGITS; ++i){ 
        sum = n1.digits_[i] + n2.digits_[i] + carry; 
        add.digits_[i] = sum % 10;
        carry = sum / 10;
    }
    return add;
}

Bigint operator- (const Bigint& n1, const Bigint& n2) 
{
    Bigint sub;
    int carry = 0; 
    for (int i=0; i< DIGITS; i++) 
    { 

        int val = n1.digits_[i] - n2.digits_[i] -carry;  

        if (val < 0) 
        { 
            val += 10; 
            carry = 1; 
        } 
        else
            carry = 0; 

        sub.digits_[i] = val;
    } 
    return sub;
}

Bigint Bigint :: multiplyBigint(const Bigint& num, const int n, int count){ 

    Bigint result;
    int carry =0;

    for(int i=0; i< DIGITS; ++i){
        int val = (num.digits_[i] * n) + carry;
        result.digits_[i+count] = val % 10;
        carry = val / 10; 
    }

    return result;
}

Bigint operator* (const Bigint& n1, const Bigint& n2)
{
    Bigint multiply;
    Bigint temp;

    int count =0;

    for(int i=0; i< DIGITS; ++i){
        temp = Bigint :: multiplyBigint(n1, n2.digits_[i], count);
        count++;
        multiply = multiply + temp;
    }

    return multiply;
}

Bigint operator/ (const Bigint& n1, const Bigint& n2)
{
    Bigint divide;
    Bigint temp = n1;

    while(temp > n2){
        divide = divide + 1;
        temp = temp - n2;
    }

    return divide; 
}

Bigint operator+ (const Bigint& n1, int n2)
{
    Bigint add;
    int carry = 0, sum = 0;

    for(int i=0; i < DIGITS; ++i){
        sum = n1.digits_[i] + (n2 % 10) + carry;
        n2 = n2 / 10;
        add.digits_[i] = sum % 10;
        carry = sum / 10;
    }
    return add;
}

bool operator> (const Bigint& n1, const Bigint& n2){

    for(int i= DIGITS - 1; i >= 0; --i){
        if(n1.digits_[i] > n2.digits_[i])
            return true;
    }
    return false;
}

头文件

#ifndef BIGINT_H_ //This checks to whether the given token has been defined somewhere else in the file.
#define BIGINT_H_

#define DIGITS 256 //increases the array size to 256 digits.

class Bigint
{
  public: // this makes the members of the public accessible from anywhere in the project.

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

    /**
     * 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 and compares them.
     */
    friend Bigint operator+ (const Bigint& n1, const Bigint& n2);
    friend Bigint operator- (const Bigint& n1, const Bigint& n2);
    friend Bigint operator* (const Bigint& n1, const Bigint& n2);
    friend Bigint operator/ (const Bigint& n1, const Bigint& n2);

    friend Bigint operator+ (const Bigint& n1, int n2);
    friend bool operator> (const Bigint& n1, const Bigint& n2);

  private: //making this only accessible within other members of this same class.
    int digits_[DIGITS];
    int radix;
    static Bigint multiplyBigint(const Bigint& num, const int n, int count);
};

#endif // BIGINT_H_

主文件

#include <iostream> //provides basic input and output services such as char.
#include "Bigint.h" //provides access and link to header file.

using namespace std;

int findRadix(string value){ //uses the Radix sort alogrithm to sort each value.

    if(value.length() == 3){
        if(value[0] == '-' && value[1] == 'r'){
            if(value[2] >= '2' && value[2] <= '9')
                return value[2] - '0';
            else if(value[2] >= 'A' && value[2] <= 'Z')
                return (value[2] - 'A') + 10;
        }
    }

    return 10;
}

int main(int argc, char *argv[]) 
{
    int radix;

    if(argc ==2){
        radix = findRadix(argv[1]);
    }


    Bigint n1(radix), n2(radix); //This compares n1 and n2 to each other to give a result.
    char op;

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

    return 0;
}

标签： c++arrayselementdigits

解决方案

看来我发现了你的问题——你自己没有打扫卫生。也就是说，每次您输入一个新号码时，它也会使用一些旧号码。

这个问题有几种可能的解决方案。最简单的一个（带有一些代码修复）如下：

clear在类的某处创建一个方法：

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

删除默认构造函数（这是可选的，但他是多余的），并将另一个更改为：

Bigint::Bigint(int radix = 10) : radix{radix}
{
    clear();
}

并在输入运算符的开头添加以下内容：

istream& operator>> (istream& in, Bigint& n)
{
    clear(); //This is the important one!!!!

    string s;
    if (in >> s) {
    ...
    ...
}

还有其他可能的解决方案：

  • 您可以将成员添加int length;到您的班级。您在输入运算符中已经有了这个长度，您只需要保留它并在所有计算中使用它。

  • 更好的是，将您的更改digits_为std::vector<int> digits_;. 这将允许您摆脱该clear函数，从而使您的构造函数为空（仅使用成员初始化）。您只需要digits_.clear();在输入运算符的开头调用即可。并使用digits_.push_back(...);而不是摆弄索引。

但是最正确的解决方案（尽管std::vector<int>无论如何都应该更改）是删除您的输入运算符并将您的更改Bigint::Bigint为接受一个字符串。那是：

Bigint::Bigint(std::string s, int radix = 10) : radix{radix}
{
    const int length = s.length();
    for (int i = 0; (i < DIGITS) && (i < length); ++i)
        n.digits_[i] = int(s[length()-1 - i] - '0');
}

之后，在您的主要部分中，您只需执行以下操作：

void main(...)
{
    ....

    char op;
    std::string s1, s2;

    while (cin >> s1 >> op >> s2)
    {
        Bigint n1 {s1, radix};
        Bigint n2 {s2, radix};

        switch (op) {
        .....
        }
    }
}

这有以下好处：

我强烈考虑digits_用std::vector<int>. 这将具有接受任何大小的数字的好处，因为向量可以根据需要增长。这也将使您的字符串到整数的转换代码更简单。并且使您的乘法更简单，因为您可以通过简单的操作轻松地在向量的末尾和开头附加零。并且会避免很多其他错误。只需将其更改为std::vector<int>！;-)

另外，请注意这using namespace std;是不好的做法：Why is "using namespace std;" 被认为是不好的做法？

推荐阅读