前言:由于计算机运算是有模运算,数据范围的表示有一定限制,如整型int(C++中int 与long相同)表达范围是(-2^31~2^31-1),unsigned long(无符号整数)是(0~2^32-1),都约为几十亿.如果采用实数型,则能保存最大的double只能提供15~16位的有效数字,即只能精确表达数百万亿的数.因此,在计算位数超过十几位的数时,不能采用现有类型,只能自己编程计算.
由于数计算时可能要进位,因此为了方便,将数由低位到高位依次存在数组下标对应由低到高位置上,另外,我们申请数组大小时,一般考虑了最大的情况,在很多情况下,表示有富余,即高位有很多0,可能造成无效的运算和判断,因此,我们一般将数组的第0个下标对应位置来存储该数的位数.如数:3485(三千四百八十五)，表达在数组a[10]上情况是:
下标　　0 　 1　 2 　3 　　4 　 5 6 7 8 9
内容　　4 　5 　 8 　4 　　3 　 0 0 0 0 0
```
说明：位数   个位  十位  百位　千位
```
倒序存储
面对高精度类型的题我们只需要像竖式一样从低位到高位计算，最后进行处理
注：高精度计算时一般用正数，对于负数，通过处理符号位的修正，在程序实现上用一个变量来存储符号位，用另一个数组存差的绝对值，置符号位：判断被减数是否大于减数：大则将符号位置为空；小则将符号位置为“- ”，交换减数与被减数；
memset可用fill代替
在以后的学习中为了加快计算速度,也可用数组的一个元素表示数的多位数字(该内容可以进一步优化一个链接)
- 以下的方法的有明显的缺点：
  - （1）浪费空间：一个整型变量（-32768~32767）只存放一位（0~9）；
  - （2）浪费时间：一次加减只处理一位；
  - 针对以上问题，如下优化：一个数组元素存放四位数；（integer的最大范围是32767，5位的话可能导致出界）将标准数组改为紧缩数组

高精度数的存储

１．如对数采用的字符串输入


#include <iostream>
#include <cstring>
using namespace std;
const int N=100;//最多100位
int main()
{
	int a[N+1],i;
	string s1;
	cin>>s1;//数s1
	memset(a,0,sizeof(a)); //数组清0
	a[0]=s1.length(); //位数
	for(i=1;i<=a[0];i++) a[i]=s1[a[0]-i]-'0';//将字符转为数字并倒序存储．
	return 0;
}

2.直接读入



#include <iostream>
using namespace std;
const int N=100;//最多100位
int main()
{
	int a[N+1],i,s,key;
	cin>>key;//数key
	memset(a,0,sizeof(a)); //数组清0
	i=0;//第0位
	while(key)  //当key大于0
	{
	  a[++i]=key%10;//取第i位的数
	  key=key/10;
	}
	a[0]=i; //共i位数
	return 0;
}

3.直接初始化(用a[]存储)
- 初始化为0: memset(a,0,sizeof(a));
- 初始化为1: memset(a,0,sizeof(a));a[0]=1;a[1]=1;

以下程序都只写函数，不写完整程序，所有高精度数存储都满足上述约定。(序号为1的)

高精度数的比较



int compare(int a[],int b[])   //比较a和b的大小关系，若a>b则为1，a<b则为-1,a=b则为0
{
	int i;
	if (a[0]>b[0])
			return 1;//a的位数大于b则a比b大
	if (a[0]<b[0]) 
		return -1;//a的位数小于b则a比b小
	for(i=a[0];i>0;i--)  //从高位到低位比较
     {
		if (a[i]>b[i]) 
			return 1;
		if (a[i]<b[i])
		 return -1;
	}
			return 0;//各位都相等则两数相等。
}

2.clear内联函数中if语句不可以删掉，如果2个输入都为0，在执行玩第一个语句后，全被删除，为空，所以if语句是输入全为0的情况！


 //清除前缀0，如果结果是空字符串则设为0 
   inline void clear(string& a){
       while(a.length()>0 && a[0]=='0')
           a.erase(0, 1);
      if(a == "")
         a = "0";

//如果a>=b则返回真（如果包含前缀零会被消除） 
  bool isBigger(string a, string b){
      clear(a);
      clear(b);
      if(a.length() > b.length())
          return true;
     if(a.length()==b.length() && a>=b)
          return true;
     return false; 
  }

高精度数的加法


int plus(int a[],int b[]) //计算a=a+b
{
	int i,k;
	k=a[0]>b[0]?a[0]:b[0]; //k是a和b中位数最大的一个的位数
	for(i=1;i<=k;i++)
	{
		a[i+1]+=(a[i]+b[i])/10;  //若有进位，则先进位
	    a[i]=(a[i]+b[i])%10;
	}  //计算当前位数字,注意：这条语句与上一条不能交换。
	if(a[k+1]>0) 
		a[0]=k+1;  //修正新的a的位数（a+b最多只能的一个进位）
	else 
		a[0]=k;
	return 0;
}

2.
注意一定要补0，否侧无法进位！！！



//两个高精度正整数加法 a+b 
 string stringAddString(string a, string b){
     //1、对位，将两个数补零直到其具有相同长度 
     while(a.length() < b.length())         
         a = '0' + a;
     while(a.length() > b.length())
         b = '0' + b; 
     //2、补零，在开头再加一个0以便进位
     a = '0' + a;
     b = '0' + b;
     //3、从低位开始相加，注意进位
     for(int i=a.length()-1; i>=0; i--){
         a[i] = a[i] + b[i] - '0';
         if(a[i] > '9'){
             a[i] = a[i] - 10;
             a[i-1] += 1;
         }
     } 
     clear(a);
     return a;  
 }

高精度数的减法


int gminus(int a[],int b[]);//计算a=a-b，返加符号位0:正数 1:负数
{ 
	int flag,i
 	 flag=compare(a,b); //调用比较函数判断大小
	if (falg==0)//相等
 	 {
		memset(a,0,sizeof(a));
		return 0;
	}  //若a=b，则a=0,也可在return前加一句a[0]=1,表示是 1位数0
	if(flag==1) //大于  
  {  
		for(i=1;i<=a[0];i++)
     	 { 
				if(a[i]<b[i])
			{ 
				a[i+1]--;

				a[i]+=10;
			} //若不够减则向上借一位
       		 a[i]=a[i]-b[i];
		}
     	while(a[a[0]]==0)
				a[0]--; //修正a的位数
   		 return 0;
	}
	else if (flag==-1)//小于  则用a=b-a,返回-1
    { 
		for(i=1;i<=b[0];i++)   
  			 {  
			if(b[i]<a[i])
			{ 
				b[i+1]--;
				b[i]+=10;
			} //若不够减则向上借一位
        a[i]=b[i]-a[i];
		}
     a[0]=b[0];
     while(a[a[0]]==0) 
		a[0]--; //修正a的位数
    return -1;
	}
}

2.两个高精度正整数减法 a-b



  string stringSubString(string a, string b){
      bool aBigger = true;
      //1、对位，将两个数补零直到其具有相同长度 
      while(a.length() < b.length())         
          a = '0' + a;
     while(a.length() > b.length())
          b = '0' + b;  
      //2、推测结果正负值，调整为前大后小 
      if(a < b)  
      {  
          aBigger = false;  
          string buf = b;  
          b = a;  
          a = buf;  
      } 
      //3、从低位开始相减，注意借位,注意不用函数string是往后插入，然后从0开始，所以i=a.length()-1;
      for(int i=a.length()-1; i>=0; i--){
          if(a[i] >= b[i]){
              a[i] = a[i] - (b[i] - '0');
         }else{
              a[i] = a[i] + 10;
              a[i-1] -= 1;
              a[i] = a[i] - (b[i] - '0');
          }
      }//4.字符就是int，字符型运算时是用ASCII码运算，
//所以a[i] - b[i]为ASCII相减，此时不为数字字符，所以加上'0'
	//保证a[i]为数字字符（string)!!!!!!!!!!!
      clear(a);
      if(!aBigger)   
          a = '-' + a;
//string中因为'-'放在前面，所以输出时在前面，前后连接
      return a;    
  }

高精度乘法1(高精度乘单精度数，单精度数是指通常的整型数)



int multi1(int a[],long  key) //a=a*key,key是单精度数  
{
	int i,k;
	if (key==0)
	{
		memset(a,0,sizeof(a));
		a[0]=1;
		return 0;
	} //单独处理key=0
	for(i=1;i<=a[0];i++)
		a[i]=a[i]*key;//先每位乘起来
	for(i=1;i<=a[0];i++)
	{
		a[i+1]+=a[i]/10;
		a[i]%=10;
	} //进位
	//注意上一语句退出时i=a[0]+1
	while(a[i]>0)
	 {
		a[i+1]=a[i]/10;
		a[i]=a[i]%10;
		i++;
		a[0]++;
	}  //继续处理超过原a[0]位数的进位,修正a的位数
	return 0;
}

待续

高精度除以低精度

算法：按照从高位到低位的顺序，逐位相除。在除到第j位时，该位在接受了来自第j+1位的余数后与除数相除，如果最高位为零，则商的长度减一



#include  <stdio.h>
#define   N  500
main()
{
  int  a[N] = {0}, c[N] = {0};
  int  i, k, d, b;
  char  a1[N];  
  printf("Input 除数:");
  scanf("%d", &b);
  printf("Input 被除数:");
  scanf("%s", a1);
  k = strlen(a1);
  for(i = 0; i < k; i++)  a[i] = a1[k - i - 1] - '0';
  d = 0;
  for(i = k - 1; i >= 0 ; i--)
  {
     d = d * 10 + a[i];
     c[i] = d / b;
     d = d % b;      
  }   
  while(c[k - 1] == 0 && k > 1)  k--;  
  printf("商=");
  for(i = k - 1; i >= 0; i--)  printf("%d", c[i]);
  printf("\n余数=%d", d);   
}

待续