C++大整数加，减运算及排序用类实现

所谓的高精度运算,是指参与运算的数(加数,减数,因子……）范围大大超出了标准数据类
型（整型，实型）能表示的范围的运算。例如，求两个200位的数的和。这时，就要用到高
精度算法了。在这里，我们先讨论高精度加法。高精度运算主要解决以下三个问题：

基本方法

1、加数、减数、运算结果的输入和存储
运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。在Pasc
al中，能表示多个数的数据类型有两种：数组和字符串。
（1）数组：每个数组元素存储1位（在优化时，这里是一个重点！），有多少位就需要多
少个数组元素；
用数组表示数的优点：每一位都是数的形式，可以直接加减；运算时非常方便
用数组表示数的缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数
值的输入习惯；

（2）字符串：字符串的最大长度是255，可以表示255位。
用字符串表示数的优点：能直接输入输出，输入时，每两位数之间不必分隔符，符合数值
的输入习惯；
用字符串表示数的缺点：字符串中的每一位是一个字符，不能直接进行运算，必须先将它
转化为数值再进行运算；运算时非常不方便；

（3）因此，综合以上所述，对上面两种数据结构取长补短：用字符串读入数据，用数组存
储数据：
var s1,s2:string;
a,b,c:array [1..260] of integer;
i,l,k1,k2:integer;
begin
write('input s1:');readln(s1);
write('input s2:');readln(s2);
{----读入两个数s1，s2，都是字符串类型}
l:=length(s1);{求出s1的长度，也即s1的位数；有关字符串的知识。}
k1:=260;
for i:=l downto 1 do
begin
a[k1]:=ord(s1[i])-48;{将字符转成数值}
k1:=k1-1;
end;
k1:=k1+1;
{----以上将s1中的字符一位一位地转成数值并存在数组a中；低位在后（从第2
60位开始），高位在前（每存完一位，k1减1）}

对s2的转化过程和上面一模一样。

2、运算过程
在往下看之前，大家先列竖式计算35+86。
注意的问题：
（1）运算顺序：两个数靠右对齐；从低位向高位运算；先计算低位再计算高位；
（2）运算规则：同一位的两个数相加再加上从低位来的进位，成为该位的和；这个和去掉
向高位的进位就成为该位的值；如上例：3+8+1=12，向前一位进1，本位的值是2；可借助
MOD、DIV运算完成这一步；
（3）最后一位的进位：如果完成两个数的相加后，进位位值不为0，则应添加一位；
（4）如果两个加数位数不一样多，则按位数多的一个进行计算；
if k1>k2 then k:=k1 else k:=k2;
y:=0;
for i:=260 downto k do
begin
x:=a[i]+b[i]+y;
c[i]:=x mod 10;
y:=x div 10;
end;
if y<>0 then begin k:=k-1;c[k]:=y; end;

3、结果的输出（这也是优化的一个重点）
按运算结果的实际位数输出
for i:=k to 260 do write(c[i]);
writeln;

4、例子：求两个数的加法
program sum;
var s,s1,s2:string;
a,b,c:array [1..260] of integer;
i,l,k1,k2:integer;
begin
write('input s1:');readln(s1);
write('input s2:');readln(s2);
l:=length(s1);
k1:=260;
for i:=l downto 1 do
begin
a[k1]:=ord(s1[i])-48;
k1:=k1-1;
end;
k1:=k1+1;

l:=length(s2);
k2:=260;
for i:=l downto 1 do
begin
b[k2]:=ord(s2[i])-48;
k2:=k2-1;
end;
k2:=k2+1;

if k1>k2 then k:=k2 else k:=k1;
y:=0;
for i:=260 downto k do
begin
x:=a[i]+b[i]+y;
c[i]:=x mod 10;
y:=x div 10;
end;
if y<>0 then begin k:=k-1;c[k]:=y;
end;
for i:=k to 260 do write(c[i]);
writeln;
end.

优化：

以上的方法的有明显的缺点：
（1）浪费空间：一个整型变量（-32768~32767）只存放一位（0~9）；
（2）浪费时间：一次加减只处理一位；

针对以上问题，我们做如下优化：一个数组元素存放四位数；（integer的最大范围是327
67，5位的话可能导致出界）。具体方法：
l:=length(s1);
k1:=260;
repeat {----有关字符串的知识}
s:=copy(s1,l-3,4);
val(s,a[k1],code);
k1:=k1-1;
s1:=copy(s1,1,l-4);
l:=l-4;
until l<=0;
k1:=k1+1;
而因为这个改进，算法要相应改变：
（1）运算时：不再逢十进位，而是逢万进位（mod 10000; div 10000);
（2）输出时：最高位直接输出，其余各位，要判断是否足够4位，不足部分要补0；例如：
1，23，2345这样三段的数，输出时，应该是100232345而不是1234567。

改进后的算法：
program sum;
var s1,s2:string;
a,b,c:array [1..260] of integer;
i,l,k1,k2,code:integer;

begin
write('input s1:');readln(s1);
write('input s2:');readln(s2);
l:=length(s1);
k1:=260;
repeat {----有关字符串的知识}
s:=copy(s1,l-3,4);
val(s,a[k1],code);
k1:=k1-1;
s1:=copy(s1,1,l-4);
l:=l-4;
until l<=0;
k1:=k1+1;
l:=length(s2);
k2:=260;
repeat
s:=copy(s2,l-3,4);
val(s,b[k2],code);
k2:=k2-1;
s2:=copy(s2,1,l-4);
l:=l-4;
until l<=0;
k2:=k2+1;

if k1 y:=0;
for i:=260 downto k do
begin
x:=a[i]+b[i]+y;
c[i]:=x mod 10000;
y:=x div 10000;
end;
if y<>0 then begin k:=k-1;c[k]:=y;end;

write(c[k]);
for i:=k+1 to 260 do
begin
----if c[i]<1000 then write('0');
----if c[i]<100 then write('0');
----if c[i]<10 then write('0');
----write(c[i]);
end;
writeln;
end.

实现了加法、减法、比较大小，有了比较大小，排序自己做吧，实在是懒得写了，要是楼主要完整的测试mfc程序，我可以发给你：
下面是头文件:
#pragma once

#ifndef CBIGINTEGER
#define CBIGINTEGER
const int MaxBitNum=5;
class CBigInteger
{
public:
CBigInteger(void);
CBigInteger(CBigInteger &a);
//CBigInteger(CBigInteger &a);//拷贝构造函数
CBigInteger(CString NumStr);
public:
~CBigInteger(void);

private:
int *DataArray;//存储绝对值的数组，简单起见，每个数组元素存储一位
char Sign;//正负号，取值为'+'或者'-'

bool PosAddPos(CBigInteger &a,CBigInteger &b);//正数加正数
bool PosBigSubPosSmall(CBigInteger &a,CBigInteger &b);//大正数减小正数
bool Formal(CString Type);//规整DataArray使每一个数组元素均小于10大于等于0

public:
CBigInteger operator + (CBigInteger &a);
CBigInteger operator - (CBigInteger &a);
CBigInteger Abs();//获得绝对值
void operator = (CBigInteger &a);
bool operator >(CBigInteger &a);
bool operator ==(CBigInteger &a);
bool operator <(CBigInteger &a);
CString ToString();//转换为字符串，便于输出
};
#endif

下面是Cpp文件：
#include "StdAfx.h"
#include "BigInteger.h"

CBigInteger::CBigInteger(void)
{
this->DataArray=new int[MaxBitNum];
for(int i=0;i DataArray[i]=0;//初始化为0
this->Sign='+';
}
CBigInteger::CBigInteger(CString NumStr)
{
this->DataArray=new int[MaxBitNum];
for(int i=0;i DataArray[i]=0;
int nCount=NumStr.GetLength();
if(nCount>MaxBitNum+1 || (NumStr[0]!='+' && NumStr[0]!='-'))
{
CString temp;
temp.Format(_T("%s初始化CBigInterger失败"),NumStr);
AfxMessageBox(temp);
CBigInteger();
}
else
{
Sign=NumStr[0];
char* ch=new char[1];
for(int i=1;i {

ch[0]=NumStr[nCount-i];
//
DataArray[i-1]=atoi(ch);

}
delete []ch;

}

}
CBigInteger::CBigInteger(CBigInteger &a)
{
this->DataArray=new int[MaxBitNum];
for(int i=0;i DataArray[i]=a.DataArray[i];
this->Sign=a.Sign;
}
CBigInteger::~CBigInteger(void)
{
delete []DataArray;
}

CBigInteger CBigInteger::operator +(CBigInteger &a)
{
CBigInteger out;
CString thisStr=this->ToString();
CString aStr=a.ToString();

if(Sign=='+' && a.Sign=='+')
{
out.Sign='+';
if(out.PosAddPos((*this),a))
{
return out;
}
else
{
CString ErrorStr;
ErrorStr.Format(_T("%s\n%s\n相加越界"),this->ToString(),a.ToString());
AfxMessageBox(ErrorStr);
return out;
}
}
if(Sign=='-' && a.Sign=='-')
{
out.Sign='-';
if(out.PosAddPos((*this),a))
{
return out;
}
else
{
CString ErrorStr;
ErrorStr.Format(_T("%s\n%s\n相加越界"),this->ToString(),a.ToString());
AfxMessageBox(ErrorStr);
return out;
}
}
if(Sign=='+' && a.Sign=='-')
{
CBigInteger AbsA=a.Abs();
if(AbsA<(*this) || AbsA==(*this))
{//减数不大于被减数
if(out.PosBigSubPosSmall((*this),AbsA))
{
return out;
}
else
{
CString ErrorStr;
ErrorStr.Format(_T("%s\n%s\n相加越界"),this->ToString(),a.ToString());
AfxMessageBox(ErrorStr);
return out;
}
}
else
{//被减数小于减数
if(out.PosBigSubPosSmall(AbsA,(*this)))
{
out.Sign='-';
return out;
}
else
{
CString ErrorStr;
ErrorStr.Format(_T("%s\n%s\n相加越界"),this->ToString(),a.ToString());
AfxMessageBox(ErrorStr);
return out;
}

}

}
return out;
}
CBigInteger CBigInteger::operator -(CBigInteger &a)
{
CString thisStr=this->ToString();
CString aStr=a.ToString();

CBigInteger aa(a);
if(aa.Sign=='-')
aa.Sign='+';
else
aa.Sign='-';
CString aaStr=aa.ToString();

return (*this)+aa;
}
CBigInteger CBigInteger::Abs()
{
CBigInteger rtv(*this);
rtv.Sign='+';
return rtv;
}
bool CBigInteger::operator >(CBigInteger &a)
{
CString thisStr=this->ToString();
CString aStr=a.ToString();

if((*this)==a)
{
return false;
}
if(this->Sign=='+' && a.Sign=='-')
{
return true;
}
if(this->Sign=='-' && a.Sign=='+')
{
return false;
}
if(this->Sign=='-' && a.Sign=='-')
{

for(int i=0;i {
if(DataArray[MaxBitNum-i-1]>a.DataArray[MaxBitNum-i-1])
{
return false;
}
if(DataArray[MaxBitNum-i-1] {
return true;
}
}
return false;
}
if(this->Sign=='+' && a.Sign=='+')
{

for(int i=0;i {
int thisData=DataArray[MaxBitNum-i-1],aData=a.DataArray[MaxBitNum-i-1];
if(DataArray[MaxBitNum-i-1]>a.DataArray[MaxBitNum-i-1])
{
return true;
}
if(DataArray[MaxBitNum-i-1] {
return false;
}

}
return false;
}
return false;
}
bool CBigInteger::operator ==(CBigInteger &a)
{
if(Sign==a.Sign)
{
for(int i=0;i {
if(DataArray[i]!=a.DataArray[i])
{
return false;
}

}
return true;
}
return false;
}
bool CBigInteger::operator <(CBigInteger &a)
{
if((*this)==a)
return false;
if((*this)>a)
return false;
return true;
}
void CBigInteger::operator = (CBigInteger &a)
{
this->DataArray=new int[MaxBitNum];
for(int i=0;i DataArray[i]=a.DataArray[i];
this->Sign=a.Sign;
}
CString CBigInteger::ToString()
{
CString str,temp;
str.Format(_T("\"%c"),Sign);
for(int i=0;i {
temp.Format(_T("%d"),DataArray[MaxBitNum-1-i]);
str+=temp;
if((i+1)%5==0 &&i!=MaxBitNum-1)
{
str+=",";
}
}
str+=_T("\"");
return str;
}

bool CBigInteger::PosAddPos(CBigInteger &a,CBigInteger &b)//正数加正数
{
for(int i=0;i DataArray[i]=a.DataArray[i]+b.DataArray[i];
return this->Formal(_T("Add"));
}
bool CBigInteger::PosBigSubPosSmall(CBigInteger &a,CBigInteger &b)//大正数减小正数
{
for(int i=0;i {
DataArray[i]=a.DataArray[i]-b.DataArray[i];
}
return this->Formal(_T("Sub"));
}

bool CBigInteger::Formal(CString Type)//规整DataArray使每一个数组元素均小于10大于等于0
{

if(Type==_T("Add"))
{
for(int i=0;i {
if(DataArray[i]>=10)
{
DataArray[i]=DataArray[i]-10;
DataArray[i+1]+=1;
}
}
if(DataArray[MaxBitNum-1]>=10)
return false;//越界
else
return true;
}
if(Type==_T("Sub"))
{
for(int i=0;i {
if(DataArray[i]<0)
{
DataArray[i]+=10;
DataArray[i+1]--;
}
}
if(DataArray[MaxBitNum-1]<0)
return false;
else
return true;
}
return false;
}

类中带主函数

是C++?

JAVA?