C++ gdb 错误读取变量 : Cannot access memory at address

Question

我正在尝试解决一个问题，它希望程序输出 n^84601 的结果。 (n=0,1,...,10) 因此，我尝试使用大整数来解决它，它在小数时效果很好，但在大数时会出现段错误。

#include <stdlib.h>
#include <iostream>
using namespace std;

const int MX = 100000;
struct BigInt {
    int ar[MX];
    int len;
    BigInt(int n) {
        int i = 0;
        while (n != 0) {
            ar[i] = n % 10;
            n /= 10;
            i++;
        }
        len = i;
    }
    BigInt times(BigInt x) {
        BigInt tmp(0);
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < x.len; j++) {
                int r = ar[i] * x.ar[j] + tmp.ar[i + j];
                tmp.ar[i + j] = r % 10;
                tmp.ar[i + j + 1] += r / 10;
            }
        }
        for (int i = min(len + x.len, MX - 1);; i--) {
            if (tmp.ar[i] != 0) {
                tmp.len = i + 1;
                break;
            }
        }
        return tmp;
    }
    void print() {
        for (int i = len - 1; i >= 0; i--) {
            cout << ar[i];
        }
        cout << endl;
    }
};
BigInt poww(BigInt a, int n) {
    if (n == 1) {
        return a;
    }
    BigInt x = poww(a, n / 2);
    BigInt y = x.times(x);
    if (n % 2 == 1) {
        y = y.times(a);
    }
    return y;
}
int main(void) {
    ios::sync_with_stdio(false);
    int n;
    while (cin >> n) {
        if (n == 0)
            cout << 0 << endl;
        else if (n == 1)
            cout << 1 << endl;
        else
            poww(BigInt(n), 86401).print();
    }
    return 0;
}

当我将 MX 改为 10000 并将 86401 改为 864 时，它可以正确计算 2^ 864.但它会与 2^86401 发生段错误。

Answer 1

你有一个堆栈溢出。

• 您的 BigInt 对象非常大:它包含 100001 个 int，通常为 400,004 字节。
• 你在堆栈上分配了其中的几个(有些是不必要的:你真的应该通过 const 引用传递参数)。
• 你有递归。
• 典型的堆栈大小限制为 8MB。

结合上面的语句，你可以看到一次最多可以有 20 个 BigInt 入栈。您的递归深度至少为 17，因此在堆栈上为每个递归调用创建多个 BigInt 肯定会失败。

有几种解决方法:

• 使用更高效的编码——目前您正在使用 int 来保存一个数字，unsigned char 会更合适
• 在堆上而不是堆栈上为数字分配空间。如果这样做，请注意 rule of five .