我将如何为这个使用数组的 bigint class 重载 + 运算符？ C++

Question

我目前正在学习使用 C++ 的在线数据结构课程，并且我正在从事个人项目以帮助我更好地理解基础知识。我正在进行的项目是 bigint class 的一个实现，一个 class 支持使用数组而不是向量或字符串来存储和计算任意精度整数。我正在努力实现主要算术运算符。

数组中的数字从最低位到最高位存储（201 将存储为 {1,0,2}），计算也按此顺序执行。

我找到了一些与此相关的 material，但绝大多数使用 vectors/strings 并且对我帮助不大。 this and this 等一些其他资源确实有帮助，但当我尝试在我的代码中实现它们时没有用。例如，这段实现加法运算符的代码不起作用，我要么得到一个 bad_alloc 异常，要么答案完全错误，但我似乎无法弄清楚为什么或如何解决它，我'已经用了好几天了：

bigint& operator+(const bigint& lhs, const bigint& rhs){
    bool minus_sign = rhs.is_negative();
    size_t amt_used = 0;    // to keep track of items in the array

    // initial size and size of resulting array
    // set initial size to the size of the larger array
    // set result_size to ini size plus one in case of carry
    size_t ini_size = lhs.get_digit_count() > rhs.get_digit_count() ?
                                lhs.get_digit_count() : rhs.get_digit_count();
    const size_t INITIAL_SIZE = ini_size;
    const size_t RESULT_SIZE = INITIAL_SIZE+1;

    uint8_t temp[RESULT_SIZE],  // temporary array
            result_arr[RESULT_SIZE],
            lhs_arr[INITIAL_SIZE], rhs_arr[INITIAL_SIZE]; // new arrays for lhs/rhs of the same size to avoid overflow if one is smaller

    //assign corresponding values to the new arrays
    for (size_t i = 0; i < lhs.get_digit_count(); i++){
        lhs_arr[i] = lhs.get_digit(i);
    }

    for (size_t i = 0; i < rhs.get_digit_count(); i++){
        rhs_arr[i] = rhs.get_digit(i);
    }

    // perform addition
    int carry = 0;  //carry variable
    size_t j = 0;
    for ( ; j < INITIAL_SIZE; j++){
        uint8_t sum = lhs_arr[j] + rhs_arr[j] + carry;

        if (sum > 9){
            result_arr[j] = sum - 10;
            carry = 1;
            amt_used++;
        }
        else{
            result_arr[j] = sum;
            carry = 0;
            amt_used++;
        }
    }

    if (carry == 1){
        result_arr[j] = 1;
        amt_used++;
    }

    // flip the array to most sig to least sig, since the constructor performs a switch to least-most sig.
    size_t decrement_index = amt_used - 1;
    for (int i = 0; i < RESULT_SIZE; i++){
        temp[i] = result_arr[decrement_index];
        decrement_index--;
    }

    for (int i = 0; i < RESULT_SIZE; i++){
        result_arr[i] = temp[i];
    }

    // create new bigint using the just-flipped array and return it
    bigint result(result_arr, amt_used, minus_sign);

    return result;
}

这是我得到的错误：线程 1：EXC_BAD_ACCESS（代码=1，地址=0x5）

要么是那个，要么我只是添加 8700 + 2100 时得到一个非常大的数字

Answer 1

这段代码有几个问题。

VLA 扩展（temp 等）的使用不是标准的 C++。这些基于堆栈的数组未初始化，因此它们将包含随机数据。当您用数据填充这些数组时，您并没有分配给每个元素。这会导致垃圾结果，例如，当左边的数字比右边的数字短时（因此 lhs_arr 的几个元素中有垃圾数据）。然后，这些错误值将用于加法数组。使用 std::vector 将符合标准，并导致向量元素全部初始化为适当的值（如 0）。这可能是您 "really large number" 的来源。

当您 "flip the array" 时，如果未使用所有结果槽，decrement_index 可能为负数。这可能是导致您 EXC_BAD_ACCESS 崩溃的原因。

返回对局部变量的引用会导致未定义的行为，因为当函数 returns 导致悬垂引用时该局部变量将被销毁。这可能是您所述问题的原因。

你对负数的处理是完全错误的，因为你根本没有真正处理它们。

我将如何为这个使用数组的 bigint class 重载 + 运算符？ C++

How would I overload the + operator for this bigint class which uses arrays? C++

c++

xcode

biginteger

bigint

data-structures