添加存储在向量中的大整数的函数问题

Question

所以我决定编写自己的多精度数据类型。我编写了一个简单的函数来添加存储在 vector<uint_fast8_t> 中的大量数字。

vector<uint_fast8_t> Add(vector<uint_fast8_t > x, vector<uint_fast8_t > y){
    unsigned int x_size = x.size() / sizeof(uint_fast8_t);
    unsigned int y_size = y.size() / sizeof(uint_fast8_t);
    unsigned int res_size{};
    if(x_size>y_size){
        res_size = x_size;
        y.insert(y.end(),uint_fast8_t(0), res_size-y_size);
    } else{
        res_size = x_size;
        x.insert(x.end(),uint_fast8_t(0), res_size-x_size);
    }
    reverse(x.begin(), x.end());
    reverse(y.begin(), y.end());
    vector<uint_fast8_t > res(res_size, 0);
    for(unsigned int i = 0; i < res_size; ++i){
        uint_fast8_t curr = res[i] + x[i] + y[i];
        if(curr >= 10){
            if(i==res_size){
                res.push_back(uint_fast8_t(1));
            } else{
                res[i+1] = uint_fast8_t(1);
            }
            res[i] = curr - uint_fast8_t(10);
        } else{
            res[i] = curr;
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

问题此函数仅适用于从 0 到 10000000 的数字（10000000 是 vector<uint_fast8_t>{1,0,0,0,0,0,0,0}）。对于更大的数字，结果是疯狂的。例如它吐出 10000000000 + 123 + = 1012300000123。为什么会这样？ 编辑 1 我被问及这个部门 x.size() / sizeof(uint_fast8_t)。据我所知 returns 对象的大小（以字节为单位）。我将它除以 uint_fast8_t 的大小以获得向量中的元素数。它似乎运作良好。可能我误会了什么。

Answer 1

好的，我修好了

感谢您指出我代码中的一些错误。我是初学者，所以这对我很重要。在您的帮助下，我设法解决了这个问题。我认为问题出在预先确定向量的大小。这是工作代码：（我认为插入函数可以在没有 for 循环的情况下插入许多零。我会检查并替换它）

vector<uint_fast8_t> Add(vector<uint_fast8_t > x, vector<uint_fast8_t > y) {
unsigned long x_size = x.size();
unsigned long y_size = y.size();
unsigned long res_size{};
uint_fast8_t curr = 0;
vector<uint_fast8_t > res{};

if(x_size>y_size){
    res_size = x_size;
    for(unsigned int i = 0; i < res_size - y_size; ++i){
        y.insert(y.begin(), uint_fast8_t(0));
    }
} else{
    res_size = y_size;
    for(unsigned int j = 0; j < res_size - x_size; ++j){
        x.insert(x.begin(), uint_fast8_t(0));
    }
}

reverse(x.begin(), x.end());
reverse(y.begin(), y.end());

for(unsigned int k = 0; k < res_size; ++k){
    curr += x[k] + y[k];
    if(curr >= 10){
        res.push_back(curr - uint_fast8_t(10));
        curr = 1;
        if(k == res_size -1){
            res.push_back(curr);
        }
    } else{
        res.push_back(curr);
        curr = 0;
    }
}

reverse(res.begin(), res.end());

return res;

}

Answer 2

这可以用 std::vector::resize, std::transform 和适当的函数对象来表达得更简单。

using Multiprecision = std::vector<uint_fast8_t>;

Multiprecision Add(Multiprecision x, Multiprecision y){

    auto common_size = std::max(x.size(), y.size());
    x.resize(common_size);
    y.resize(common_size);
    Multiprecision res(common_size);

    bool carry = false;
    std::transform(x.begin(), x.end(), y.begin(), res.begin(), [&carry](uint_fast8_t x, uint_fast8_t y){ 
        uint_fast8_t value = x + y + carry; 
        carry = (value >= 10);
        return value - (carry * 10);
    });

    return res;
}

添加存储在向量中的大整数的函数问题

Issue with function that adds large integers stored in vectors

c++

algorithm

addition

multiprecision