前言
C++中一直没有实现big integer类,而long long类型也仅仅占了8个字节,取值范围在-9223372036854775808~+9223372036854775807之间。所以,要实现比long long更大的整数类型,就必须自己造轮子。
一般来说,对于数据的保存有两种做法,一个是用字符串进行保存,一个是用一个数值数组进行保存。这里我用数值型数组进行保存。
(Q:为什么不用字符串存储呢? A:因为这是我在C++课上遇到的一个附加思考题,我就完全按照题目要求来实现了,实际上我个人也觉得用数组更方便实现一点)
功能描述
利用int数组编写高精度运算类bign
,完成大整数的运算。
类的数据成员有两个:一个是int型变量length
,用来存储大数数据的有效长度;另一个是整型数组data
,用来存储大整数(数组长度最大500)。(实际上,读者完全可以利用short数组或者unsigned char 数组保存值)
支持字符串赋值和整数赋值,了重载+ - * / += -= *= 、= >> << > < >= <= == !=运算符。
类的定义
class bign
{
private:
//length存大整数的长度
int length;
//data存大整数的各个位置的值
int data[500]; //下标0存个位数字,下标1存十位数字,以此类推
public:
bign();
void operator=(const string &); //利用字符串赋值
void operator=(const int &); //利用int赋值
bign &operator+=(const bign &);
bign &operator-=(const bign &);
bign &operator*=(const bign &);
bign &operator/=(const bign &);
bign operator+(const bign &);
bign operator-(const bign &);
bign operator*(const bign &);
bign operator/(const bign &);
bool operator>(const bign &);
bool operator>=(const bign &);
bool operator<(const bign &);
bool operator<=(const bign &);
friend bool operator==(const bign &, const bign &);
friend bool operator!=(const bign &, const bign &);
friend ostream &operator<<(ostream &, const bign &);
friend istream &operator>>(istream &, bign &);
};
类的实现
无参构造函数
长度默认为0,data的值全部置0。
bign::bign()
{
length = 0;
for (int i = 0; i < 500; i++)
data[i] = 0;
}
重载 = ,实现赋值
字符串为参数:
void bign::operator=(const string &str)
{
length = str.length();
int j = 0;
for (int i = str.length() - 1; i >= 0; i--, j++)
//字符在ASCII中以数值储存,'0'-'9',对应十进制数字48-57
data[j] = str[i] - '0'; //-'0'的本质是-48,比如'9'-'0'本质是57-48,就转化为了数值9
for (int i = str.length(); i < 500; i++)
data[i] = 0;
}
int变量为参数:
void bign::operator=(const int &num)
{
string str = to_string(num);
operator=(str);
}
这里偷了个懒。
重载 << >> ,实现输入输出
istream &operator>>(istream &in, bign &bignum)
{
string str;
in >> str;
bignum = str;
return in;
}
ostream &operator<<(ostream &out, const bign &bignum)
{
string s = "";
for (int i = bignum.length - 1; i >= 0; i--)
s += to_string(bignum.data[i]);
out << s;
return out;
}
重载 == 等,实现关系比较
bool operator==(const bign &n1, const bign &n2)
{
if (n1.length != n2.length)
return false;
for (int i = 0; i < n1.length; i++)
if (n1.data[i] != n2.data[i])
return false;
return true;
}
bool operator!=(const bign &n1, const bign &n2)
{
return !(n1 == n2); //利用operator==()函数取反
}
bool bign::operator>(const bign &bignum)
{
if (this->length > bignum.length)
return true;
else if (this->length < bignum.length)
return false;
for (int i = length; i > 0; i--)
if (data[i] != bignum.data[i])
return data[i] > bignum.data[i];
return false;
}
bool bign::operator>=(const bign &bignum)
{
if (this->length > bignum.length)
return true;
else if (this->length < bignum.length)
return false;
for (int i = length; i > 0; i--)
if (data[i] != bignum.data[i])
return data[i] > bignum.data[i];
return true;
}
bool bign::operator<(const bign &bignum)
{
return !(*this >= bignum); //利用operator>=()函数取反
}
bool bign::operator<=(const bign &bignum)
{
return !(*this > bignum); //利用operator<()函数取反
}
重载 + ,实现大整数加法
大整数加法比较简单,利用carried变量记录进位,然后每一位相加即可。
bign bign::operator+(const bign &bignum)
{
int longer_len = max(this->length, bignum.length);
int carried = 0;
bign temp;
for (int i = 0; i < longer_len; i++)
{
temp.data[i] = (this->data[i] + bignum.data[i] + carried) % 10;
carried = (this->data[i] + bignum.data[i] + carried) / 10;
}
if (carried > 0)
{
temp.data[longer_len] = carried;
longer_len += 1;
}
temp.length = longer_len;
return temp;
}
//利用operator+()实现operator+=()
bign &bign::operator+=(const bign &bignum)
{
*this = *this + bignum;
return *this;
}
重载 - ,实现大整数减法
减法只考虑了大数减小数。
减法和加法类似,利用borrowed变量记录借位,按位置相减,最后算出长度(最高位)即可。
bign bign::operator-(const bign &bignum)
{
int longer_len = max(this->length, bignum.length);
int borrowed = 0;
bign temp;
for (int i = 0; i < longer_len; i++)
{
if (this->data[i] < bignum.data[i] + borrowed)
{
temp.data[i] = 10 + this->data[i] - bignum.data[i] - borrowed;
borrowed = 1;
}
else
{
temp.data[i] = this->data[i] - bignum.data[i] - borrowed;
borrowed = 0;
}
}
//计算长度
for (int i = 500; i >= 0; i--)
{
if (temp.data[i] > 0)
{
temp.length = i + 1;
break;
}
}
return temp;
}
//利用operator-()实现operator-=()
bign &bign::operator-=(const bign &bignum)
{
*this = *this - bignum;
return *this;
}
重载 * ,实现大整数乘法
这里我使用的算法原理是模拟乘法竖式计算。为了简化步骤,计算时先不进位,全部运算完之后再进行进位。
bign bign::operator*(const bign &bignum)
{
bign temp;
for (int i = 0; i < length; i++) //this->data作为竖式上面的数
for (int j = 0; j < bignum.length; j++) //bignum.data作为竖式下面的数
temp.data[i + j] += this->data[i] * bignum.data[j];
//相乘后的结果加到对应位置,但并不进位
//统一进位
for (int i = 0; i < 500; i++)
{
if (temp.data[i] >= 10)
{
temp.data[i + 1] += (temp.data[i] / 10);
temp.data[i] %= 10;
}
}
//计算长度
for (int i = 500; i >= 0; i--)
{
if (temp.data[i] > 0)
{
temp.length = i + 1;
break;
}
}
return temp;
}
//利用operator*()实现operator*=()
bign &bign::operator*=(const bign &bignum)
{
*this = *this * bignum;
return *this;
}
重载 / ,实现大整数除法 (难点)
设计大整数除法的算法是实现大整数类最大的难点。
基本思想是:反复做减法,看从被除数里面最多能减去多少个除数,商就是多少。
但是,逐个减显然效率过低,尤其是对于大整数。所以我们要判断:一次最多能减几个“除数的10的n次方”。
以7546除以23为例:
- 7546长度为4,23长度为2,长度差值是2,所以从23的10^2倍开始考虑
- 先用7546减去23的100倍,即减去2300,可以减3次,余下646,此时商就是300 (300 = 100 * 3),百位是3
- 然后646减去23的10倍,即减去230,可以减2次,余下186,此时商就是320 (320 = 300 + 10 * 2),十位是2
- 然后186减去23的1倍,可以减8次,余下2,此时商就是328 (328 = 320 + 1 * 8),个位是1
bign bign::operator/(const bign &bignum)
{
//如果除数大于被除数,返回大整数0
bign ans; //最终的答案
ans = 0;
if (*this < bignum)
return ans; //返回的是bign,而不是int数值
//如果除数等于被除数,返回大整数1
ans = 1;
if (*this == bignum)
return ans;
//如果除数小于被除数,开始计算
int d_len = length - bignum.length;
bign this_copy = *this; //this的拷贝
bign temp10; //大整数10
temp10 = 10;
bign temp1; //大整数1
temp1 = 1;
bign tempn;
ans = 0;
for (int i = d_len; i >= 0; i--)
{
//把被除数的10^n次倍数赋值给tempn
tempn = bignum;
for (int j = 0; j < i; j++)
tempn *= temp10;
//看看能减几次tempn,存到temp_ans里
bign temp_ans;
temp_ans = 1;
while ((temp_ans * tempn) <= this_copy)
temp_ans += temp1;
temp_ans -= temp1;
this_copy -= (temp_ans * tempn); //this_copy去掉已经减掉的值,以进行下一次计算
ans.data[i] = temp_ans.data[0]; //把商的对应位数存起来
}
//计算长度
for (int i = 500; i >= 0; i--)
{
if (ans.data[i] > 0)
{
ans.length = i + 1;
break;
}
}
return ans;
}
//利用operator/()实现operator/=()
bign &bign::operator/=(const bign &bignum)
{
*this = *this / bignum;
return *this;
}
全部代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
class bign
{
private:
int length;
int data[500];
public:
bign();
void operator=(const string &);
void operator=(const int &);
bign &operator+=(const bign &);
bign &operator-=(const bign &);
bign &operator*=(const bign &);
bign &operator/=(const bign &);
bign operator+(const bign &);
bign operator-(const bign &);
bign operator*(const bign &);
bign operator/(const bign &);
bool operator>(const bign &);
bool operator>=(const bign &);
bool operator<(const bign &);
bool operator<=(const bign &);
friend bool operator==(const bign &, const bign &);
friend bool operator!=(const bign &, const bign &);
friend ostream &operator<<(ostream &, const bign &);
friend istream &operator>>(istream &, bign &);
};
bign::bign()
{
length = 0;
for (int i = 0; i < 500; i++)
data[i] = 0;
}
void bign::operator=(const string &str)
{
length = str.length();
int j = 0;
for (int i = str.length() - 1; i >= 0; i--, j++)
data[j] = str[i] - '0';
for (int i = str.length(); i < 500; i++)
data[i] = 0;
}
void bign::operator=(const int &num)
{
string str = to_string(num);
operator=(str);
}
bool operator==(const bign &n1, const bign &n2)
{
if (n1.length != n2.length)
return false;
for (int i = 0; i < n1.length; i++)
if (n1.data[i] != n2.data[i])
return false;
return true;
}
bool operator!=(const bign &n1, const bign &n2)
{
return !(n1 == n2);
}
bool bign::operator>(const bign &bignum)
{
if (this->length > bignum.length)
return true;
else if (this->length < bignum.length)
return false;
for (int i = length; i > 0; i--)
if (data[i] != bignum.data[i])
return data[i] > bignum.data[i];
return false;
}
bool bign::operator>=(const bign &bignum)
{
if (this->length > bignum.length)
return true;
else if (this->length < bignum.length)
return false;
for (int i = length; i > 0; i--)
if (data[i] != bignum.data[i])
return data[i] > bignum.data[i];
return true;
}
bool bign::operator<(const bign &bignum)
{
return !(*this >= bignum);
}
bool bign::operator<=(const bign &bignum)
{
return !(*this > bignum);
}
istream &operator>>(istream &in, bign &bignum)
{
string str;
in >> str;
bignum = str;
return in;
}
ostream &operator<<(ostream &out, const bign &bignum)
{
string s = "";
for (int i = bignum.length - 1; i >= 0; i--)
s += to_string(bignum.data[i]);
out << s;
return out;
}
bign bign::operator+(const bign &bignum)
{
int longer_len = max(this->length, bignum.length);
int carried = 0;
bign temp;
for (int i = 0; i < longer_len; i++)
{
temp.data[i] = (this->data[i] + bignum.data[i] + carried) % 10;
carried = (this->data[i] + bignum.data[i] + carried) / 10;
}
if (carried > 0)
{
temp.data[longer_len] = carried;
longer_len += 1;
}
temp.length = longer_len;
return temp;
}
bign &bign::operator+=(const bign &bignum)
{
*this = *this + bignum;
return *this;
}
bign bign::operator-(const bign &bignum)
{
int longer_len = max(this->length, bignum.length);
int borrowed = 0;
bign temp;
for (int i = 0; i < longer_len; i++)
{
if (this->data[i] < bignum.data[i] + borrowed)
{
temp.data[i] = 10 + this->data[i] - bignum.data[i] - borrowed;
borrowed = 1;
}
else
{
temp.data[i] = this->data[i] - bignum.data[i] - borrowed;
borrowed = 0;
}
}
for (int i = 500; i >= 0; i--)
{
if (temp.data[i] > 0)
{
temp.length = i + 1;
break;
}
}
return temp;
}
bign &bign::operator-=(const bign &bignum)
{
*this = *this - bignum;
return *this;
}
bign bign::operator*(const bign &bignum)
{
bign temp;
for (int i = 0; i < length; i++)
for (int j = 0; j < bignum.length; j++)
temp.data[i + j] += this->data[i] * bignum.data[j];
for (int i = 0; i < 500; i++)
{
if (temp.data[i] >= 10)
{
temp.data[i + 1] += (temp.data[i] / 10);
temp.data[i] %= 10;
}
}
for (int i = 500; i >= 0; i--)
{
if (temp.data[i] > 0)
{
temp.length = i + 1;
break;
}
}
return temp;
}
bign &bign::operator*=(const bign &bignum)
{
*this = *this * bignum;
return *this;
}
bign bign::operator/(const bign &bignum)
{
bign ans;
ans = 0;
if (*this < bignum)
return ans;
ans = 1;
if (*this == bignum)
return ans;
int d_len = length - bignum.length;
bign this_copy = *this;
bign temp10;
temp10 = 10;
bign temp1;
temp1 = 1;
bign tempn;
ans = 0;
for (int i = d_len; i >= 0; i--)
{
tempn = bignum;
for (int j = 0; j < i; j++)
tempn *= temp10;
bign temp_ans;
temp_ans = 1;
while ((temp_ans * tempn) <= this_copy)
temp_ans += temp1;
temp_ans -= temp1;
this_copy -= (temp_ans * tempn);
ans.data[i] = temp_ans.data[0];
}
for (int i = 500; i >= 0; i--)
{
if (ans.data[i] > 0)
{
ans.length = i + 1;
break;
}
}
return ans;
}
bign &bign::operator/=(const bign &bignum)
{
*this = *this / bignum;
return *this;
}
//主函数测试一下
int main()
{
bign a, b, c;
a = "123456789123456789987654321999999999999999999999999";
cin >> b;
c = 12345;
cout << (a + b) << endl;
cout << (a - b) << endl;
cout << (a * b) << endl;
cout << (a / b) << endl;
cout << (a < b) << endl;
cout << (a > c) << endl;
a += b;
cout << a << endl;
cout << (a <= b) << endl;
cout << (a >= c) << endl;
a += c;
cout << a << endl;
cout << (a == b) << endl;
cout << (a != c) << endl;
return 0;
}
/*
输入:
6514
输出:
123456789123456789987654322000000000000000000006513
123456789123456789987654321999999999999999999993485
804197524350197529979580253507999999999999999999993486
18952531336115564935163389929382867669634633097
0
1
123456789123456789987654322000000000000000000006513
0
1
123456789123456789987654322000000000000000000018858
0
1
*/
可以改进之处
- unsigned,不能储存负数。实际上这是一个比较好解决的问题,数据成员里加一个bool型的变量,对代码做一些小改动就能完善了。
- 没有异常处理,算法很朴素,类不够稳健。读者可以尝试自行改进。
Comments | NOTHING