【压位高精度】高性能BigInt类 支持负数(内存优化版)
本文最后更新于 178 天前,其中的信息可能已经有所发展或是发生改变。
本文持续更新中~敬请关注

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 14000;
struct BigInt
{
	bool flag;
	int len;
	int number[MAXN];
	BigInt(BigInt& a)
	{
		flag = a.flag;
		len = a.len;
		memcpy(number, a.number, MAXN * 4);
	}
	BigInt()//新建高精度数
	{
		memset(number, 0, MAXN * 4);
		flag = 1;
	}
	BigInt(string s)//字符串类型输入,双精度
	{
		memset(number, 0, MAXN * 4);
		flag = 1;
		if (s[0] == '-')
		{
			flag = 0;
			s.erase(s.begin());
		}
		int dec[] = { 1,10,100,1000 };
		reverse(s.begin(), s.end());
		len = s.size();
		for (int i = 0; i < len; i++)
		{
			number[i / 4] += (s[i] - '0') * dec[i % 4];
		}
	}
	BigInt(int num)
	{
		memset(number, 0, MAXN * 4);//构造函数初始化数组
		flag = 1;
		if (num < 0) 
		{
			flag = 0;
			num = abs(num);
		}
		len = 1;//0
		int dec[] = { 1,10,100,1000 };
		for (int i = 0; num > 0; i++)
		{
			number[i / 4] += (num % 10) * dec[i % 4];
			num /= 10;
			len = i + 1;
		}
	}
	int operator[](int i)//从个位数右往左起,从0计数,不可赋值
	{
		int dec[] = { 1,10,100,1000 };
		int ans = number[i / 4] / dec[i % 4] % 10;
		return ans;
	}
	void print()//打印数字
	{
		if (flag == 0)cout << "-";
		cout << number[(len - 1) / 4];
		for (int i = (len - 1) / 4 - 1; i >= 0; i--)
		{
			cout << setfill('0') << setw(4) << number[i];
		}
	} 
	void edit(int i, int j)//把第i位修改为j
	{
		int dec[] = { 1,10,100,1000 };
		number[i / 4] = number[i / 4] - ((*this)[i] - j) * dec[i % 4];
	}
}; 
BigInt operator-(BigInt a, BigInt b); 
int compare_abs(BigInt& a, BigInt& b) 
{
	for (int i = (a.len - 1) / 4; i >= 0; i--)
	{
		if (a.number[i] < b.number[i])return 1;
		if (a.number[i] > b.number[i])return 0;
	}
	return 2;
}
int compare(BigInt& a, BigInt& b)
{
	if (a.flag == 0 && b.flag == 1)return true;
	if (a.flag == 1 && b.flag == 0)return false;
	if (a.flag == 1)
	{
		if (a.len < b.len)return true;
		if (a.len > b.len)return false;
		int temp = compare_abs(a, b);
		if (temp == 1)return 1;
		if (temp == 0)return 0;
		return 2;
	}
	else
	{
		if (a.len < b.len)return false;
		if (a.len > b.len)return true;
		int temp = compare_abs(a, b);
		if (temp == 1)return 0;
		if (temp == 0)return 1;
		return 2;
	}
}
bool operator<(BigInt& a, BigInt& b)
{ 
	if (compare(a, b) == 1)return true;
	else return false;
}
bool operator>(BigInt& a, BigInt& b)
{
	if (compare(a, b) == 0)return true;
	else return false;
}
bool operator==(BigInt& a, BigInt& b)
{
	if (compare(a, b) == 2)return true;
	else return false;
}
BigInt operator*(BigInt a, BigInt b)
{
	BigInt ans;
	if (a.flag != b.flag)ans.flag = 0;
	ans.len = a.len + b.len;
	for (int i = 0; i <= (a.len - 1) / 4; i++)//可减少运算量
	{
		for (int j = 0; j <= (b.len - 1) / 4; j++)
		{
			ans.number[i + j] += a.number[i] * b.number[j];
			ans.number[i + j + 1] += ans.number[i + j] / 10000;
			ans.number[i + j] %= 10000;
		}
	}
	if (ans[ans.len - 1] == 0)ans.len--;
	if (ans[ans.len - 1] == 0)ans.len = 1;//结果为0时
	return ans;
}
BigInt operator+(BigInt a, BigInt b)
{
	if (a.flag == 1 && b.flag == 0)
	{
		b.flag = !b.flag;
		a = a - b;
		return a;
	}
	else if (a.flag == 0 && b.flag == 1)
	{
		a.flag = !a.flag;
		a = b - a;
		return a;
	}
	BigInt ans;
	if (a.flag == 0 && b.flag == 0)ans.flag = 0;
	ans.len = max(a.len, b.len);
	for (int i = 0; i <= (ans.len - 1) / 4; i++)
	{
		ans.number[i] += a.number[i] + b.number[i];
		ans.number[i + 1] += ans.number[i] / 10000;
		ans.number[i] %= 10000;

	}
	if (ans[ans.len])ans.len++;
	return ans;
}
BigInt operator-(BigInt a, BigInt b)
{
	if (a.flag == 1 && b.flag == 0)
	{
		b.flag = !b.flag;
		a = a + b;
		return a;
	}
	else if (a.flag == 0 && b.flag == 1)
	{
		a.flag = !a.flag;
		BigInt temp;
		temp = a + b;
		temp.flag = 0;
		return temp;
	}
	else if (a.flag == 0 && b.flag == 0)
	{
		a.flag = !a.flag;
		b.flag = !b.flag;
		BigInt temp;
		temp = a + b;
		temp.flag = 0;
		return temp;
	}
	BigInt ans;
	ans.len = max(a.len, b.len);
	for (int i = 0; i <= (ans.len - 1) / 4; i++)
	{
		ans.number[i] += a.number[i] - b.number[i];
		if (ans.number[i] < 0)
		{
			ans.number[i] += 10000;
			ans.number[i + 1]--;
		}
	}
	int i = (ans.len - 1) / 4;
	if (ans.number[i + 1] < 0)//负数处理
	{
		ans.flag = 0;
		for (int j = 0; j <= i; j++)
		{
			ans.number[j] = 10000 - ans.number[j];
			ans.number[j + 1]++;
		}
	}
	while (i >= 0 && ans.number[i] == 0)i--;
	ans.len = (i + 1) * 4;
	while (ans.len > 0 && ans[ans.len - 1] == 0)ans.len--;
	return ans;
}
BigInt operator^(BigInt a, int b)
{
	BigInt ans(1);
	while (b)
	{
		if (b % 2 == 1)ans = ans * a;
		if (b != 1)a = a * a;//可能溢出
		b = b / 2;
	}
	return ans;
}
/*
高精度四则运算Release
1.MAXN控制高精度数位数,过小可能溢出。最大位数为MAXN*4
2.高精度数有三种创建方式,直接创建,字符串类型转换,int类型转换
3.一个高精度数结构体内必有三个成员:flag,数字长度,数字数组。新建高精度数必须给长度赋值
4.运算符重载,两个对象均为BigInt时,使用引用。其中一个为int时,转换成BigInt
5.ans.len为数字位数,[]下标访问时从第0位开始
*/
int main()
{
	//Demo演示
	string a, b;
	cin >> a >> b;
	BigInt aa(a), bb(b);
	aa = aa * bb;
	aa.print();
	return 0;
}

 

更新日志:

V1.0

1.上线

V1.1

1.内存优化

2.修复了运算次数过多的Bug,性能提升

3.修复了溢出问题

V2.0

1.支持负数运算

 

TODO Lists:

 

文章标题:【压位高精度】高性能BigInt类 支持负数(内存优化版)
文章链接:https://intmain0.com/102/
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处
评论和私信会在第一时间回复。如果您觉得文章对您有帮助,可以点击文章右下角【分享】一下。您的鼓励是博主的最大动力!
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇