在好例子网，分享、交流、成长！
您当前所在位置：首页 → C/C++ 开发实例 → Android手机应用开发 → c++ 大数运算库（bigInt）

c++ 大数运算库（bigInt）

Android手机应用开发

下载此实例
  • 开发语言：C/C++
  • 实例大小：2.56KB
  • 下载次数：19
  • 浏览次数：771
  • 发布时间：2019-07-01
  • 实例类别：Android手机应用开发
  • 发 布 人：QQ18821431
  • 文件格式：.rar
  • 所需积分：2
 相关标签： C语言 大数运算
网友评论 举报投诉 收藏该页

实例介绍

【实例简介】支持任意长度数值的加减乘除、模乘、模幂等。
【实例截图】

【核心代码】 

/****************************************************************/
//大数运算库源文件：BigInt.cpp
//作者：afanty@vip.sina.com
//版本：1.0 (2003.4.26)
//说明：适用于MFC
/****************************************************************/

#include "stdafx.h"
#include "BigInt.h"

CBigInt::CBigInt()
{
	m_nSign=1;
	m_nLength=1;
	for(int i=0;i<BI_MAXLEN;i  )m_ulValue[i]=0;
}

CBigInt::~CBigInt()
{
}

int CBigInt::Cmp(CBigInt& A)
{
	if(m_nLength>A.m_nLength)return 1;
	if(m_nLength<A.m_nLength)return -1;
	for(int i=m_nLength-1;i>=0;i--)
	{
		if(m_ulValue[i]>A.m_ulValue[i])return 1;
		if(m_ulValue[i]<A.m_ulValue[i])return -1;
	}
	return 0;
}

CBigInt& CBigInt::Mov(CBigInt& A)
{
	m_nLength=A.m_nLength;
	for(int i=0;i<BI_MAXLEN;i  )m_ulValue[i]=A.m_ulValue[i];
	return *this;
}

CBigInt& CBigInt::Mov(unsigned __int64 A)
{
	if(A>0xffffffff)
	{
		m_nLength=2;
		m_ulValue[1]=(unsigned long)(A>>32);
		m_ulValue[0]=(unsigned long)A;
	}
	else
	{
		m_nLength=1;
		m_ulValue[0]=(unsigned long)A;
	}
	for(int i=m_nLength;i<BI_MAXLEN;i  )m_ulValue[i]=0;
	return *this;
}

CBigInt CBigInt::Add(CBigInt& A)
{
	CBigInt X;
	if(X.m_nSign==A.m_nSign)
	{
		X.Mov(*this);
		int carry=0;
	    unsigned __int64 sum=0;
	    if(X.m_nLength<A.m_nLength)X.m_nLength=A.m_nLength;
		for(int i=0;i<X.m_nLength;i  )
		{
			sum=A.m_ulValue[i];
			sum=sum X.m_ulValue[i] carry;
			X.m_ulValue[i]=(unsigned long)sum;
			if(sum>0xffffffff)carry=1;
			else carry=0;
		}
		if(X.m_nLength<BI_MAXLEN)
		{
			X.m_ulValue[X.m_nLength]=carry;
		    X.m_nLength =carry;
		}
		return X;
	}
	else{X.Mov(A);X.m_nSign=1-X.m_nSign;return Sub(X);}
}

CBigInt CBigInt::Add(long A)
{
	CBigInt X;
	if((m_nSign*A)>=0)
	{
		X.Mov(*this);
		unsigned __int64 sum;
	    sum=A X.m_ulValue[0];
		X.m_ulValue[0]=(unsigned long)sum;
		if(sum>0xffffffff)
		{
			int i=1;
			while(X.m_ulValue[i]==0xffffffff){X.m_ulValue[i]=0;i  ;}
			X.m_ulValue[i]  ;
			if(i<BI_MAXLEN)X.m_nLength=i 1;
		}
		return X;
	}
	else return Sub(-A);
}
		
CBigInt CBigInt::Sub(CBigInt& A)
{
	CBigInt X;
	if(m_nSign==A.m_nSign)
	{
		X.Mov(*this);
		int cmp=X.Cmp(A); 
		if(cmp==0){X.Mov(0);return X;}
		int len,carry=0;
		unsigned __int64 num;
		unsigned long *s,*d;
	    if(cmp>0){s=X.m_ulValue;d=A.m_ulValue;len=X.m_nLength;}
	    if(cmp<0){s=A.m_ulValue;d=X.m_ulValue;len=A.m_nLength;X.m_nSign=1-X.m_nSign;}
	    for(int i=0;i<len;i  )
		{
			if((s[i]-carry)>=d[i])
			{
				X.m_ulValue[i]=s[i]-carry-d[i];
				carry=0;
			}
			else
			{
				num=0x100000000 s[i];
				X.m_ulValue[i]=(unsigned long)(num-carry-d[i]);
				carry=1;
			}
		}
		while(X.m_ulValue[len-1]==0)len--;
		X.m_nLength=len;
		return X;
	}
	else{X.Mov(A);X.m_nSign=1-X.m_nSign;return Add(X);}
}

CBigInt CBigInt::Sub(long A)
{
	CBigInt X;
	if((m_nSign*A)>=0)
	{
		X.Mov(*this);
		if(X.m_ulValue[0]>=(unsigned long)A){X.m_ulValue[0]-=A;return X;}
		if(X.m_nLength==1){X.m_ulValue[0]=A-X.m_ulValue[0];X.m_nSign=1-X.m_nSign;return X;}
		unsigned __int64 num=0x100000000 X.m_ulValue[0];
		X.m_ulValue[0]=(unsigned long)(num-A);
		int i=1;
		while(X.m_ulValue[i]==0){X.m_ulValue[i]=0xffffffff;i  ;}
		if(X.m_ulValue[i]==1)X.m_nLength--;
		X.m_ulValue[i]--;
		return X;
	}
	else return Add(-A);
}

CBigInt CBigInt::Mul(CBigInt& A)
{
	CBigInt X,Y;
	unsigned __int64 mul;
    unsigned long carry;
    for(int i=0;i<A.m_nLength;i  )
	{
		Y.m_nLength=m_nLength;
		carry=0;
		for(int j=0;j<m_nLength;j  )
		{
			mul=m_ulValue[j];
			mul=mul*A.m_ulValue[i] carry;
			Y.m_ulValue[j]=(unsigned long)mul;
			carry=(unsigned long)(mul>>32);
		}
		if(carry&&(Y.m_nLength<BI_MAXLEN)){Y.m_nLength  ;Y.m_ulValue[Y.m_nLength-1]=carry;}
		if(Y.m_nLength<BI_MAXLEN-i)
		{
			Y.m_nLength =i;
		    for(int k=Y.m_nLength-1;k>=i;k--)Y.m_ulValue[k]=Y.m_ulValue[k-i];
		    for(k=0;k<i;k  )Y.m_ulValue[k]=0;
		}
		X.Mov(X.Add(Y));
	}
	if(m_nSign A.m_nSign==1)X.m_nSign=0;
	else X.m_nSign=1;
	return X;
}

CBigInt CBigInt::Mul(long A)
{
	CBigInt X;
	unsigned __int64 mul;
	unsigned long carry=0;
	X.Mov(*this);
	for(int i=0;i<m_nLength;i  )
	{
		mul=m_ulValue[i];
		mul=mul*A carry;
		X.m_ulValue[i]=(unsigned long)mul;
		carry=(unsigned long)((mul-X.m_ulValue[i])>>32);
	}
	if(carry&&(X.m_nLength<BI_MAXLEN)){X.m_nLength  ;X.m_ulValue[X.m_nLength-1]=carry;}
	if(A<0)X.m_nSign=1-X.m_nSign;
	return X;
}

CBigInt CBigInt::Div(CBigInt& A)
{
	CBigInt X,Y,Z;
	int len;
	unsigned __int64 num,div;
	unsigned long carry=0;
	Y.Mov(*this);
	while(Y.Cmp(A)>0)
	{       
		if(Y.m_ulValue[Y.m_nLength-1]>A.m_ulValue[A.m_nLength-1])
		{
			len=Y.m_nLength-A.m_nLength;
			div=Y.m_ulValue[Y.m_nLength-1]/(A.m_ulValue[A.m_nLength-1] 1);
		}
		else if(Y.m_nLength>A.m_nLength)
		{
			len=Y.m_nLength-A.m_nLength-1;
			num=Y.m_ulValue[Y.m_nLength-1];
			num=(num<<32) Y.m_ulValue[Y.m_nLength-2];
			if(A.m_ulValue[A.m_nLength-1]==0xffffffff)div=(num>>32);
			else div=num/(A.m_ulValue[A.m_nLength-1] 1);
		}
		else
		{
            X.Mov(X.Add(1));
			break;
		}
        Z.Mov(div);
		Z.m_nLength =len;
		for(int i=Z.m_nLength-1;i>=len;i--)Z.m_ulValue[i]=Z.m_ulValue[i-len];
		for(i=0;i<len;i  )Z.m_ulValue[i]=0;
		X.Mov(X.Add(Z));
		Z.Mov(Z.Mul(A));
		Y.Mov(Y.Sub(Z));
	}
	if(Y.Cmp(A)==0)X.Mov(X.Add(1));
	if(m_nSign A.m_nSign==1)X.m_nSign=0;
	else X.m_nSign=1;
	return X;
}

CBigInt CBigInt::Div(long A)
{
	CBigInt X;
	X.Mov(*this);
	if(X.m_nLength==1){X.m_ulValue[0]=X.m_ulValue[0]/A;return X;}
	unsigned __int64 div,mul;
	unsigned long carry=0;
	for(int i=X.m_nLength-1;i>=0;i--)
	{
		div=carry;
		div=(div<<32) X.m_ulValue[i];
		X.m_ulValue[i]=(unsigned long)(div/A);
		mul=(div/A)*A;
		carry=(unsigned long)(div-mul);
	}
	if(X.m_ulValue[X.m_nLength-1]==0)X.m_nLength--;
	if(A<0)X.m_nSign=1-X.m_nSign;
	return X;
}

CBigInt CBigInt::Mod(CBigInt& A)
{
	CBigInt X,Y;
	int len;
	unsigned __int64 num,div;
	unsigned long carry=0;
	X.Mov(*this);
	while(X.Cmp(A)>0)
	{       
		if(X.m_ulValue[X.m_nLength-1]>A.m_ulValue[A.m_nLength-1])
		{
			len=X.m_nLength-A.m_nLength;
			div=X.m_ulValue[X.m_nLength-1]/(A.m_ulValue[A.m_nLength-1] 1);
		}
		else if(X.m_nLength>A.m_nLength)
		{
			len=X.m_nLength-A.m_nLength-1;
			num=X.m_ulValue[X.m_nLength-1];
			num=(num<<32) X.m_ulValue[X.m_nLength-2];
			if(A.m_ulValue[A.m_nLength-1]==0xffffffff)div=(num>>32);
			else div=num/(A.m_ulValue[A.m_nLength-1] 1);
		}
		else
		{
			X.Mov(X.Sub(A));
			break;
		}
        Y.Mov(div);
		Y.Mov(Y.Mul(A));
		Y.m_nLength =len;
		for(int i=Y.m_nLength-1;i>=len;i--)Y.m_ulValue[i]=Y.m_ulValue[i-len];
		for(i=0;i<len;i  )Y.m_ulValue[i]=0;
		X.Mov(X.Sub(Y));
	}
	if(X.Cmp(A)==0)X.Mov(0);
	return X;
}

long CBigInt::Mod(long A)
{
	if(m_nLength==1)return(m_ulValue[0]%A);
	unsigned __int64 div;
	unsigned long carry=0;
	for(int i=m_nLength-1;i>=0;i--)
	{
		div=carry*0x100000000 m_ulValue[i];
		carry=(unsigned long)(div-((div/A)*A));
	}
	return carry;
}

int CBigInt::InPutFromStr(CString& str, const unsigned int system=DEC)
{
    int len=str.GetLength();
	Mov(0);
	for(int i=0;i<len;i  )
    {
       	Mov(Mul(system));
		int k=str[i]-48;
		Mov(Add(k));
  	}
  	return 0;
}

int CBigInt::OutPutToStr(CString& str, const unsigned int system=DEC)
{
	str="";
	char ch;
	CBigInt X;
	X.Mov(*this);
	while(X.m_ulValue[X.m_nLength-1]>0)
	{
		ch=X.Mod(system) 48;
		str.Insert(0,ch);
        X.Mov(X.Div(system));
	}
	return 0;
}	
			
CBigInt CBigInt::Euc(CBigInt& A)
{
	CBigInt X,Y;
	X.Mov(*this);
	Y.Mov(A);
	if((X.m_nLength==1)&&(X.m_ulValue[0]==1))return X;
	if((Y.m_nLength==1)&&(Y.m_ulValue[0]==1)){X.Mov(X.Sub(1));return X;}
	if(X.Cmp(Y)==1)X.Mov(X.Mod(Y));
	else Y.Mov(Y.Mod(X));
	X.Mov(X.Euc(Y));
    Y.Mov(*this);
	if(Y.Cmp(A)==1)
	{
		X.Mov(X.Mul(Y));
		X.Mov(X.Sub(1));
		X.Mov(X.Div(A));
	}
	else
	{
		X.Mov(X.Mul(A));
		X.Mov(X.Add(1));
		X.Mov(X.Div(Y));
	}
	return X;
}
			
CBigInt CBigInt::Mon(CBigInt& A, CBigInt& B)
{
	CBigInt X,Y,Z;
	X.Mov(1);
	Y.Mov(*this);
    Z.Mov(A);
	while((Z.m_nLength!=1)||Z.m_ulValue[0])
	{
		if(Z.m_ulValue[0]&1)
		{
			Z.Mov(Z.Sub(1));
			X.Mov(X.Mul(Y));
			X.Mov(X.Mod(B));
		}
		else
		{
			Z.Mov(Z.Div(2));
			Y.Mov(Y.Mul(Y));
			Y.Mov(Y.Mod(B));
		}
	}
    return X;
}

标签： C语言 大数运算

实例下载地址

c++ 大数运算库（bigInt）

不能下载？内容有错？ 点击这里报错 + 投诉 + 提问

好例子网口号：伸出你的我的手 — 分享！

相关软件

相关文章

网友评论

我要评论

发表评论

(您的评论需要经过审核才能显示)

查看所有0条评论>>

小贴士

感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。

  • 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
  • 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
  • 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
  • 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。

关于好例子网

本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明

;
报警