c++ - BigInt 计算器吐出稍微错误的结果
问题描述
因此,对于我的任务,我必须创建一个可以处理最长 256 个字符的大整数的计算器。我要完成的任务的当前部分是让它与更大的数字相乘。DIGITS 是每个 Bigint 类的位数限制,目前设置为 20 以进行调试,但将增加到 256
当进行 25 * 137 之类的计算时,我得到的答案应该是 3425 5 * 137,这样完美。但是,当它到达必须执行 i 循环的第二次迭代时,它是 20 * 137 时,它得到的答案是错误的,我无法弄清楚为什么。我有一种暗示,这与进位为两位数(14)有关,但我仍然无法真正弄清楚如何解决它。
显然有问题的主要实现在 bigint 类的 * 运算符中。我知道这与 << 或 >> 运算符无关,因为它们非常适合加法和减法。
bigint 类的完整代码如下:
#include <iostream>
#include <string>
#include "Bigint.h"
#include <cmath>
using namespace std;
Bigint::Bigint()
{
for (int i = DIGITS-1; i >= 0; --i) {
digits_[i] = 0;
}
}
ostream& operator<< (ostream& out, const Bigint& n)
{
string s = "";
bool found = false;
for (int i = DIGITS - 1; i >= 0; --i) {
if(n.digits_[i] > 0) {
found = true;
}
if(n.digits_[i] != 0 || found == true) {
s += char(n.digits_[i] + '0');
}
}
if (s == "") {
s = "0";
}
return out << s;
}
istream& operator>> (istream& in, Bigint& n)
{
// Extracts full-length number (does not work for any other length).
// All characters are assumed to be valid digits.
//
string s;
if (in >> s) {
for (int i = 0; i < DIGITS; ++i) {
n.digits_[i] = i < s.length() ? s[s.length() - 1 - i] - '0' : 0;
}
}
return in;
}
Bigint operator+ (const Bigint& n1, const Bigint& n2)
{
Bigint ret;
int cur_carry = 0;
for(int i = 0; i < DIGITS; ++i) {
int n1_digit = n1.get(i);
int n2_digit = n2.get(i);
if(n1_digit < 0 || n1_digit > 9) {
n1_digit = 0;
}
if(n2_digit < 0 || n2_digit > 9) {
n2_digit = 0;
}
//printf("n1 : %d\n", n1_digit);
//printf("n2 : %d\n", n2_digit);
int sum = n1_digit + n2_digit + cur_carry;
//cout << "sum : " << sum << endl;
cur_carry = Bigint::getCarry(sum);
//cout << "new carry : " << cur_carry << endl;
ret.set(i, Bigint::getDigitValue(sum));
//cout << "Set : " << i << "," << Bigint::getDigitValue(sum) << endl;
}
return ret;
}
Bigint operator* (const Bigint& n1, const Bigint& n2)
{
Bigint ret;
//int borrowed = 0;
Bigint sum;
for(int i = 0; i < DIGITS ; i++){
int n1_digit = n1.get(i);
//cout << "n2: " << n2_digit << endl;
Bigint temp;
if(n1_digit < 0 || n1_digit > 9) {
n1_digit = 0;
}
int carry = 0;
for (int j = 0; j < DIGITS ; j++){
int val = n1_digit * (pow(10, i)) * n2.get(j);
cout << "n1: " << n1_digit << endl;
cout << "n2: " << n2.get(j) << endl;
if(carry != 0){
temp.set(j, (Bigint::getDigitValue(val)) + carry);
cout << "Carry was " << carry << ", now set 0" << endl;
cout << "value to set: " << (Bigint::getDigitValue(val)) + carry << endl;
carry = 0;
}
else if(carry == 0){
temp.set(j, Bigint::getDigitValue(val));
cout << "value to set: " << (Bigint::getDigitValue(val))<< endl;
}
carry = (Bigint::getCarry(val) + carry);
cout << "carry: " << carry << endl;
}
cout << "Sum before adding temp: " << sum << endl;
sum = sum + temp;
cout << "Sum after adding temp: " << sum << endl;
}
ret = sum;
return ret; // Only correct when n2 equals 1.
}
int Bigint::get(int pos) const {
//Return address of digit for reading
int ret = digits_[pos];
return ret;
}
void Bigint::set(int pos, int val) {
this->digits_[pos] = val;
}
int Bigint::getCarry(int val) {
//Integer division, always floors
return val/10;
}
int Bigint::getDigitValue(int val) {
return val % 10;
}
头文件:
#ifndef BIGINT_H_
#define BIGINT_H_
#define DIGITS 20
class Bigint
{
public:
/**
* Creates a Bigint initialised to 0.
*/
Bigint();
/**
* Inserts n into stream or extracts n from stream.
*/
friend std::ostream& operator<< (std::ostream &out, const Bigint& n);
friend std::istream& operator>> (std::istream &in, Bigint& n);
/**
* Returns the sum, difference, product, or quotient of n1 and n2.
*/
friend Bigint operator* (const Bigint& n1, const Bigint& n2);
friend Bigint operator+ (const Bigint& n1, const Bigint& n2);
int get(int pos) const;
void set(int pos, int val);
static int getCarry(int val);
static int getDigitValue(int val);
private:
int digits_[DIGITS];
};
#endif // BIGINT_H_
主要的:
#include <iostream>
#include "Bigint.h"
using namespace std;
int main(int argc, char *argv[])
{
Bigint n1, n2;
char op;
while (cin >> n1 >> op >> n2) {
switch (op) {
case '+' :
cout << n1 + n2 << endl;
break;
case '*' :
cout << n1 * n2 << endl;
break;
}
}
return 0;
}
}
解决方案
您不应该使用此行int val = n1_digit * (pow(10, i)) * n2.get(j);
,因为它会导致整数溢出,因为您使用的是 bigintger,而不是使用乘数中的数字并在结果后面添加零。
要添加的零的数量将取决于乘数的位置,您可以for(int i = 0; i < DIGITS ; i++)
在重载的 * 函数中从此循环中找到变量 i
推荐阅读
- css - 如何自动保存主 scss 文件?
- python-3.x - Matplotlib 中轴标签的格式
- java - 构建一个代表 BitSet 的板并将其存储在 BigInteger 中
- python - 用于解析尺寸测量描述的正则表达式
- angular - 角度服务是否可以从异步上下文中访问?
- javascript - 我的无序列表是从 json 文件呈现的,但我想要每个列表元素周围的边框
- jquery - 使用 Bootstrap-slider 插件在 Tooltip 中格式化数字
- javascript - 如何在不使用背景色的情况下用颜色填充 div?
- javascript - 在 Python 中使用带有 for 循环的 Asyncio,类似于 Javascript 中的 map 方法和 promise.all
- excel - VBA 检查 PR SAP 附件