c++ BigInt和分段错误

g6baxovj  于 2023-05-08  发布在  其他
关注(0)|答案(2)|浏览(107)

我的程序运行在所有数字上，但在计算BigInt MAX（INT_MAX）时不运行。当我试着运行这个时，它给了我一个分段错误。下面是BigInt类：

#include <iostream>
#include <limits.h>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class BigInt
{
    private:
        vector<char> v; 
    public:
        BigInt() 
        {
            v.push_back('0');
        }
        
        BigInt(int num) 
        {
            while (num != 0)
            {
                v.push_back(num % 10);
                num /= 10;
            }
        }
        
        BigInt(string str) //3
        {
            for (int i = str.length() - 1; i >= 0; i--)
                v.push_back(str[i] - '0');
        }
        
        BigInt operator+(BigInt b) 
        {
            BigInt result;
            int carry = 0;
            for (int i = 0; i < max(v.size(), b.v.size()); i++)
            {
                int sum = carry;
                if (i < v.size())
                    sum += v[i];
                if (i < b.v.size())
                    sum += b.v[i];
                result.v.push_back(sum % 10);
                carry = sum / 10;
            }
            if (carry != 0)
                result.v.push_back(carry);
            return result;
        }
        
        BigInt operator++( ) 
        {
            *this = *this + BigInt(1);
            return *this;
        }
        
        BigInt operator++(int) 
        {
            BigInt temp = *this;
            *this = *this + BigInt(1);
            return temp;
        }
        
        BigInt operator*(BigInt b) 
        {
            BigInt result;
            result.v.resize(v.size() + b.v.size());
            
            for (int i = 0; i < v.size(); i++)
                for (int j = 0; j < b.v.size(); j++)
                    result.v[i + j] += v[i] * b.v[j];
            
            for (int i = 0; i < result.v.size() - 1; i++)
            {
                result.v[i + 1] += result.v[i] / 10;
                result.v[i] %= 10;
            }
            
            while (result.v.back() == 0 && result.v.size() > 1)
                result.v.pop_back();
            
            return result;
        }
        
        BigInt operator+=(BigInt b) 
        {
            *this = *this + b;
            return *this;
        }
        
        BigInt half() 
        {
            BigInt result;
            
            int remainder = 0;
            
            for (int i = v.size() - 1; i >= 0; i--)
            {
                int current = remainder * 10 + v[i];
                int digit = current / 2;
                
                if (digit != 0 || !result.v.empty())
                    result.v.push_back(digit);
                
                remainder = current % 2;
            }
            
            if (result.v.empty())
                result.v.push_back(0);
            
            return result;
        }
        
        bool isOdd()
        {
            return v[0] % 2 == 1;
        }
        
        bool isEven()
        {
            return !isOdd();
        }
        
        bool operator==(BigInt b)  
        {
            if (v.size() != b.v.size())
                return false;
            
            for (int i = 0; i < v.size(); i++)
                if (v[i] != b.v[i])
                    return false;
            
            return true;
        }
        
        bool operator<(BigInt b) 
        {
            if (v.size() != b.v.size())
                return v.size() < b.v.size();
            
            for (int i = v.size() - 1; i >= 0; i--)
                if (v[i] != b.v[i])
                    return v[i] < b.v[i];
            
            return false;
        }
        
friend ostream& operator<<(ostream& os, const BigInt& b){
    if (b.v.size() < 9)
    {
        for (auto it = b.v.rbegin(); it != b.v.rend(); ++it)
        {
            os << static_cast<int>(*it);
        }
    }
    else
    {
        os << static_cast<int>(b.v.back()) << ".";
        for (size_t i = 1; i <= 7; ++i)
        {
            os << static_cast<int>(b.v[b.v.size() - i - 1]);
        }
        os << "e" << b.v.size() - 1;
    }
    return os;
    }
};

下面是驱动程序代码：

struct ThreeNp1
{
    BigInt start;
    BigInt steps;
    BigInt max;
    BigInt odd;
    BigInt even;
};
void print(ThreeNp1 temp)
{
    cout << "start:" << temp.start << endl;
    cout << "steps:" << temp.steps << endl;
    cout << "max:" << temp.max << endl;
    cout << "odds:" << temp.odd << endl;
    cout << "evens:" << temp.even << endl;
}
void findThreeNp1(BigInt n, ThreeNp1 &Np1, bool printSteps = false)
{
    if (printSteps)
    {
        cout << "->" << '(' << n << ')';
    }
    if (Np1.max < n) 
        Np1.max = n; 

    if (n == BigInt(1)) 
    {
        return; 
    }
    else if (n.isEven()) 
    {
        Np1.even++; 
        Np1.steps++;
        findThreeNp1(n.half(), Np1, printSteps); 
    }
    else if (n.isOdd()) 
    {
        Np1.odd++;
        Np1.steps++;
        BigInt tempN(n);                                       
        findThreeNp1(tempN * BigInt(3) + BigInt(1), Np1, printSteps); 
    }
    else
        {
            cout << "How the hell did I get here?\n";
            return;
        }
}
int main()
{
    BigInt MAX(INT_MAX);
    cout << "The largest integer is " << MAX << endl;
    cout << "Twice the largest integer is " << MAX + MAX << endl;
    BigInt start(INT_MAX); 
    bool printSteps = false;
    ThreeNp1 N = {start, 0, 0, 0, 0};   
    findThreeNp1(start, N, printSteps);
    cout << endl;
    print(N);
    return 0;
}

我已经重写了很多次代码，我已经检查了我的逻辑错误。我能想到的办法都试过了。如果有人看到任何错误或我可以改善，让这件事运行，请让我知道。

c++

2条答案

按热度按时间
a14dhokn

a14dhokn1#

segfault是由于递归函数findThreeNp1()耗尽了它的堆栈空间，我/@john将根本原因归因于以下缺陷：
1.默认构造函数应该将vector<...> a留空。否则BigInt（1）+ BigInt（1）将变为20。这需要一个特殊的情况，当vector.size() == 0在operator<<和isOdd()。

  1. vector<char> v意味着它是实现定义的，如果它是有符号的或无符号的。在我的系统上，它是签名的，这意味着99 * 99会触发溢出。将类型更改为unsigned char。
  2. half()不工作。BigInt(20).half()不应该是01。我重写了它并进行了最低限度的测试。
    下面是生成的程序：
#include <iostream>
#include <limits.h>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
class BigInt
{
    private:
        // stores numbers in reverse order, i.e. 123 as [3, 2, 1]
        vector<unsigned char> v;
    public:
        BigInt() {
        }

        BigInt(int num) {
            for(; num; num /= 10)
                v.push_back(num % 10);
        }

        BigInt operator+(BigInt b) {
            BigInt result;
            int carry = 0;
            int n = max(v.size(), b.v.size());
            for (int i = 0; i < n; i++) {
                int sum = carry;
                if (i < v.size())
                    sum += v[i];
                if (i < b.v.size())
                    sum += b.v[i];
                result.v.push_back(sum % 10);
                carry = sum / 10;
            }
            if (carry)
                result.v.push_back(carry);
            return result;
        }

        BigInt operator++() {
            *this = *this + BigInt(1);
            return *this;
        }

        BigInt operator++(int) {
            BigInt temp = *this;
            *this = *this + BigInt(1);
            return temp;
        }

        BigInt operator*(BigInt b) {
            BigInt result;
            result.v.resize(v.size() + b.v.size());
            for (int i = 0; i < v.size(); i++)
                for (int j = 0; j < b.v.size(); j++)
                    result.v[i + j] += v[i] * b.v[j];

            for (int i = 0; i < result.v.size() - 1; i++) {
                result.v[i + 1] += result.v[i] / 10;
                result.v[i] %= 10;
            }

            while (result.v.back() == 0 && result.v.size() > 1)
                result.v.pop_back();

            return result;
        }

        BigInt operator+=(const BigInt &b) {
            *this = *this + b;
            return *this;
        }

        BigInt half() {
            BigInt result;
            for(int i = 0; i < v.size(); i++) {
                // losing the most significant digit
                if(i + 1 != v.size() || v[i] / 2)
                    result.v.push_back((v[i]) / 2);
                // truncate least significant digit, i.e. 3/2 = 1
                if(i && (v[i] % 2))
                    result.v[i-1] += 5;
            }
            return result;
        }

        bool isOdd() {
            return v.size() && (v[0] % 2 == 1);
        }

        bool isEven() {
            return !isOdd();
        }

        bool operator==(BigInt b) {
            if (v.size() != b.v.size())
                return false;

            for (int i = 0; i < v.size(); i++)
                if (v[i] != b.v[i])
                    return false;

            return true;
        }

        bool operator<(BigInt b) {
            if (v.size() != b.v.size())
                return v.size() < b.v.size();

            for (int i = v.size() - 1; i >= 0; i--)
                if (v[i] != b.v[i])
                    return v[i] < b.v[i];

            return false;
        }

        friend ostream& operator<<(ostream& os, const BigInt& b){
            if(!b.v.size()) {
                os << 0;
            } else if (b.v.size() < 9) {
                for (auto it = b.v.rbegin(); it != b.v.rend(); ++it)
                    os << static_cast<int>(*it);
            } else {
                os << static_cast<int>(b.v.back()) << ".";
                for (size_t i = 1; i <= 7; ++i) {
                    os << static_cast<int>(b.v[b.v.size() - i - 1]);
                }
                os << "e" << b.v.size() - 1;
            }
            return os;
        }
};

struct ThreeNp1 {
    BigInt start;
    BigInt steps;
    BigInt max;
    BigInt odd;
    BigInt even;
};

void print(ThreeNp1 temp) {
    cout << "start:" << temp.start << endl;
    cout << "steps:" << temp.steps << endl;
    cout << "max:" << temp.max << endl;
    cout << "odds:" << temp.odd << endl;
    cout << "evens:" << temp.even << endl;
}

void findThreeNp1(BigInt n, ThreeNp1 &Np1, bool printSteps = false) {
    if (printSteps)
    {
        cout << "->" << '(' << n << ')';
    }
    if (Np1.max < n)
        Np1.max = n;

    if (n == BigInt(1)) {
        return;
    } else if (n.isEven()) {
        ++Np1.even;
        ++Np1.steps;
        findThreeNp1(n.half(), Np1, printSteps);
    }
    else if (n.isOdd()) {
        ++Np1.odd;
        ++Np1.steps;
        BigInt tempN(n);
        findThreeNp1(tempN * BigInt(3) + BigInt(1), Np1, printSteps);
    } else {
        cout << "How the hell did I get here?\n";
        return;
    }
}

int main(int argc, char **argv) {
    BigInt MAX(INT_MAX);
    cout << "The largest integer is " << MAX << endl;
    cout << "Twice the largest integer is " << MAX + MAX << endl;
    BigInt start(INT_MAX);
    bool printSteps = false;
    ThreeNp1 N = {start, 0, 0, 0, 0};   
    findThreeNp1(start, N, printSteps);
    cout << endl;
    print(N);
    return 0;
}

输出为：

$ time ./a.out
The largest integer is 2.1474836e9
Twice the largest integer is 4.2949672e9

start:2.1474836e9
steps:450
max:1.2353467e15
odds:162
evens:288

real    0m0.015s
user    0m0.010s
sys     0m0.005s

下面是findThreeNp1()的迭代版本。一旦其他问题得到解决，它就不会有太大的区别（在10 k外部运行时，它的速度提高了约2.5%）：

void findThreeNp1(BigInt n, ThreeNp1 &Np1, bool printSteps = false) {
    while(!(n == BigInt(1))) {
        if (printSteps)
            cout << "->" << '(' << n << ')';
        if (Np1.max < n) 
            Np1.max = n;
        ++Np1.steps;
        if (n.isEven()) {
            ++Np1.even; 
            n = n.half();
        } else {
            ++Np1.odd;
            n = BigInt(3) * n + BigInt(1);
        }
    }
}

Np1.steps == Np1.odd + Np1.even所以我们只需要其中两个变量。

赞(0）分享  回复(0）举报  2023-05-08
sqxo8psd

sqxo8psd2#

你的错误在这里

BigInt() 
{
    v.push_back('0');
}

那应该是

BigInt() 
{
    v.push_back(0);
}

因为你的类存储整数而不是数字。所以零是0而不是"0"。
具体来说，你的乘法代码从result开始，用BigInt result;初始化为零，但因为你的默认构造函数没有正确初始化为零，乘法例程也有bug，这导致了无限递归和堆栈溢出，当你试图计算Collatz猜想系列时。
调试器很快就发现了这个错误，你应该学习如何使用它。

更新（已更正）

您的half例程有问题。您处理要从最高有效位到最低有效位减半的数字的位数。但是您将结果数字按相同的顺序（最重要的数字在前）推送到result变量。这与您的类的工作方式相矛盾，该类首先存储最低有效位。结果是，在half操作之后，数字是正确的，但以相反的顺序存储。由于默认构造函数的工作方式，还包含了一个额外的零数字。
可能默认构造函数应该让vector为空。将零BigInt打印为"0"是一种特殊情况，应该在打印例程中处理，而不是在计算例程中处理。这将简化代码。例如，BigInt x;和BigInt y(0);产生不同的内部向量。这也是一个bug。

赞(0）分享  回复(0）举报  2023-05-08
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com