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

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)部门的情况。据我所知，它以字节为单位返回对象的大小。我把它除以uint_fast8_t的大小，得到向量中元素的数量。它似乎运行良好。也许我误解了什么。

Answer 1

使用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;
}

Answer 2

好的，我修复了它

谢谢你指出我代码中的一些错误。我是个发明家，所以这对我来说很重要。在你的帮助下，我设法解决了这个问题。我认为问题出在预先确定矢量的大小上。以下是工作代码：(我认为插入函数可以在没有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;

}