代码之家  ›  专栏  ›  技术社区  ›  babakahn

如何重载这个使用数组的bigint类的+运算符?C++

  •  0
  • babakahn  · 技术社区  · 7 年前

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

    数字存储在从最低有效位到最高有效位的数组中(201将存储为{1,0,2}),并且也按此顺序执行计算。

    我发现了一些与此相关的材料,但绝大多数使用向量/字符串,对我帮助不大。一些其他资源,例如 this this 确实有帮助,但当我试图在代码中实现它们时,它不起作用。例如,这段实现加法运算符的代码不起作用,我要么得到了一个错误的\u 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\u BAD\u访问(代码=1,地址=0x5)

    要么我得到一个很大的数字,当我加8700+2100

    1 回复  |  直到 7 年前
        1
  •  0
  •   1201ProgramAlarm    7 年前

    此代码有几个问题。

    VLA扩展的使用(用于 temp etc)不是标准的C++。这些基于堆栈的数组未初始化,因此它们将包含随机数据。用数据填充这些数组时,并不是为每个元素赋值。例如,当左边的数字小于右边的数字时,这会导致垃圾结果(因此 lhs_arr 其中包含垃圾数据)。然后将在加法数组中使用这些错误值。使用 std::vector 将符合标准,并导致向量元素全部初始化为适当的值(如0)。这可能就是你的“非常大的数字”的来源。

    “翻转阵列”时, decrement_index 如果未使用所有结果槽,则可能为负值。这可能是你的原因 EXC_BAD_ACCESS 崩溃。

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

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