bigint.cpp

大整数除法 比如说超过64位的整数相除

#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <string.h>
#define MAX 1000
#define MARK ('0'-1)

//The Prototypes of the functions
char* Initialiaze(char [],int);
char* Addition(char[],char[]);
char* Substraction(char[],char[]);
char* Multiplication(char[],char[]);
char* Division(char[],char[]);
char Div_per_bit(char [],int , char []);
int Sub_per_bit(char [],char [],int *);
int Copy(char [],int ,char []);
int Compare(char [],char []);
int Data_Process(char []);
int Value(char);
int Compare(char [],char []);
int Judge(int);
int Convert(char [],char [],int);

int main()
{    char a[MAX],b[MAX];
     printf("a(length<%d):",MAX);
     gets(a);
     printf("b(length<%d):",MAX);
     gets(b);
	 printf("\n");
	 printf("a+b=%s\n",Addition(a,b));
	 printf("a-b=%s\n",Substraction(a,b));
	 printf("a*b=%s\n",Multiplication(a,b));
	 printf("a/b=%s\n",Division(a,b));	// 除乘结合
     return 0;
}
//The Iniatilize function ,initialize the result number before calculation
char* Initialize(char s[],int length)
{    int i;
     for (i=0; i<length; i++)
       s[i]=MARK;
     return s;

}
//The Addition function , add two operands and return the result
char* Addition(char a[],char b[])
{    char c[2*MAX],d[2*MAX];
     int i,j,k,a_length,b_length;
     Initialize(c,2*MAX);
     a_length=strlen(a);
     b_length=strlen(b);
     for (i=a_length-1,j=b_length-1,k=2*MAX-1; ( i>=0 || j>=0 ) ; i--,j--,k--)
     {  if ( i>=0 && j>=0 )
      c[k]=Value(a[i])+Value(b[j])+'0';
    else
      if (i>=0 && j<0 )
         c[k]=Value(a[i])+'0';
      else
        if ( i<0 && j>=0 )
           c[k]=Value(b[j])+'0';
     }
     Data_Process(c);
     Convert(c,d,2*MAX);
     return d;
}
//The Substraction function , substract one operand from another operand , and return the result
char* Substraction(char a[],char b[])
{    char c[2*MAX],d[2*MAX];
     int i,j,k,a_length,b_length,sub_result,symbol,flag[2*MAX]={0};
     Initialize(c,2*MAX);
     a_length=strlen(a);
     b_length=strlen(b);
     if (strcmp(a,b)==0)
    return ("0");
     for (i=a_length-1,j=b_length-1,k=2*MAX-1; ( i>=0 || j>=0 ) ; i--,j--,k--)
     {   sub_result=a[i]-b[j];
     symbol=Judge(sub_result);
     if (i>=1 && j>=0)
     {      if (flag[k]==0)
        {   if  (a[i]>=b[j])
               c[k]=sub_result+'0';
            else
            {       c[k]=sub_result+10+'0';
               flag[k-1]=1;
            }
        }
        else
        {   if (a[i]-b[j]>=1)
              c[k]=sub_result-1+'0';
            else
            {     c[k]=sub_result+9+'0';
              flag[k-1]=1;
            }
        }
     }
     else
     if  (i==0 && j<0)
        {
             if (flag[k]==0)
              c[k]=a[i];
             else
             {   if (a[i]==1)
                ;
             else
                 c[k]=a[i]-1;
             }
        }
     else
     {  if ((i==0) && (j==0))
           {   if (flag[k]==0)
               {  switch (symbol)
              {  case 0:   ;
                       break;
                 case 1:   c[k]=sub_result+'0';
                       break;
                 case -1:  return NULL;
                       break;
               }
               }
               else
               {   switch (Judge(sub_result-1))
               {  case 0:   ;
                        break;
                  case 1:   c[k]=sub_result-1+'0';
                        break;
                  case -1:  return NULL;
                        break;
               }
               }
           }
         else
         if ((i<0) && (j>=0))
            return NULL;
         else
         if ((i>0) && (j<0))
         {  if (flag[k]==0)
              c[k]=a[i];
            else
            {   if (a[i]>'0')
               c[k]=a[i]-1;
            else
            {  c[k]='9';
               flag[k-1]=1;
            }
            }
         }
     }
     }
     Convert(c,d,2*MAX);
     return d;
}
//The Multiplication function,multipy two operands and return the result
char* Multiplication(char a[],char b[])
{    char c[2*MAX],d[2*MAX];
     int i,j,k,p,a_length,b_length;
     Initialize(c,2*MAX);
     a_length=strlen(a);
     b_length=strlen(b);
     for (j=b_length-1;  j>=0 ; j--)
     {  k=2*MAX-(b_length-j);
    for (i=a_length-1,p=k; i>=0; i--,p--)
       if (c[p]==MARK)
       {    c[p]=(Value(a[i]))*(Value(b[j]))%10+'0';
            if (c[p-1]==MARK)
                     c[p-1]=(Value(a[i]))*(Value(b[j]))/10+'0';
                 else
                     c[p-1]+=(Value(a[i]))*(Value(b[j]))/10;
       }
       else
       {    c[p]+=(Value(a[i]))*(Value(b[j]))%10;
            if (c[p-1]==MARK)
                 c[p-1]=(Value(a[i]))*(Value(b[j]))/10+'0';
            else
                 c[p-1]+=(Value(a[i]))*(Value(b[j]))/10;
       }
    Data_Process(c);
     }
     Convert(c,d,2*MAX);
     return d;

}
//The Division function,divise one operand from another operand, and return the result
char* Division(char a[],char b[])
{   char a1[MAX],c[MAX];
	char *d = new char[MAX];
    strcpy(a1,a);
    int i,k,a_length=strlen(a1),b_length=strlen(b);
    for (i=0; b[i]; i++)
       if (b[i]!='0')
      break;
    if ((unsigned int)i==strlen(b))
    {    printf("Error!\nIf you do division,the dividend must not equal to zero!\n");
        return 0;
    }
    if (Compare(a,b)==-1)
    {    printf("Error!\nIf you do division, A must bigger than B!\n");
    return 0;
    }
    for ( i=0,k=0; k<a_length-b_length+1; i++,k++)
      c[k]=Div_per_bit(a1,b_length+i,b);
    c[k]='\0';
    Convert(c,d,MAX);
    return d;

}
//The Div_per_bit function , calculate quotient per digit ,and return the result to Division function
char Div_per_bit(char a[],int a_l,char b[])
{   int i,j;
    char c[MAX];
    for (i=0,j=0; i<a_l; i++)
      if ( a[i]!=MARK)
      {   c[j]=a[i];
      j++;
      }
    c[j]='\0';
    for (i=0; c[i]; i++)
       if (c[i]!='0')
      break;
    if ((unsigned int)i==strlen(c))
       return '0';
    if (Compare(c,b)<0)
       return '0';
    if (Compare(c,b)==0)
    {  for ( i=0; i<a_l; i++)
      a[i]=MARK;
       return '1';
    }
    i=0;
    while (Compare(c,b)>=0)
       Sub_per_bit(c,b,&i);
    Copy(a,a_l,c);
    return ('0'+i);

}
//The Sub_per_bit function, do the division by using substraction time after time
int  Sub_per_bit(char a[],char b[],int *count)
{    char c[MAX],d[MAX];
     int i,j,k,a_length,b_length,sub_result,symbol,flag[MAX]={0};
     Initialize(c,MAX);
     a_length=strlen(a);
     b_length=strlen(b);
     if (strcmp(a,b)==0)
    strcpy(c,"0");
     for (i=a_length-1,j=b_length-1,k=MAX-1; ( i>=0 || j>=0 ) ; i--,j--,k--)
     {   sub_result=a[i]-b[j];
     symbol=Judge(sub_result);
     if (i>=1 && j>=0)
     {      if (flag[k]==0)
        {   if  (a[i]>=b[j])
               c[k]=sub_result+'0';
            else
            {       c[k]=sub_result+10+'0';
               flag[k-1]=1;
            }
        }
        else
        {   if (a[i]-b[j]>=1)
              c[k]=sub_result-1+'0';
            else
            {     c[k]=sub_result+9+'0';
              flag[k-1]=1;
            }
        }
     }
     else
     if  (i==0 && j<0)
        {
             if (flag[k]==0)
              c[k]=a[i];
             else
             {   if (a[i]==1)
                ;
             else
                 c[k]=a[i]-1;
             }
        }
     else
     {  if ((i==0) && (j==0))
           {   if (flag[k]==0)
               {  switch (symbol)
              {  case 0:   ;
                       break;
                 case 1:   c[k]=sub_result+'0';
                       break;
                 case -1:  return 0;
                       break;
               }
               }
               else
               {   switch (Judge(sub_result-1))
               {  case 0:   ;
                    break;
                  case 1:   c[k]=sub_result-1+'0';
                    break;
                  case -1:  return 0;
                    break;
               }
               }
           }
         else
         if ((i<0) && (j>=0))
         {  return 0;
         }
         else
         if ((i>0) && (j<0))
         {  if (flag[k]==0)
              c[k]=a[i];
            else
            {   if (a[i]>'0')
               c[k]=a[i]-1;
            else
            {  c[k]='9';
               flag[k-1]=1;
            }
            }
         }
     }
     }
     Convert(c,d,MAX);
     strcpy(a,d);
     (*count)++;
     return 1;
}
//The Copy function , copy  a number_string  to another , wipe off the inutility symbol
int Copy(char a[],int a_l,char c[])
{   int i,j,c_l=strlen(c);
    for (i=0; i<a_l-c_l; i++)
      a[i]=MARK;
    for (i,j=0; j<c_l; i++,j++)
      a[i]=c[j];
    return 1;
}
//The Compare function ,compare two numbers and return the result
int Compare(char a[],char b[])
{//   char c[MAX];
    if ((strlen(a))>(strlen(b)))
       return 1;
    if ((strlen(a))==(strlen(b)))
       return (strcmp(a,b));
    //if ((strlen(a))<(strlen(b)))
       return -1;
}

//The Value function , receiver a digit_char, and return the number
int Value(char c)
{   if (isdigit(c))
       return (c-'0');
    else return 0;
}
//The Data_Process function,
int Data_Process(char s[])
{   int p,head,tail=2*MAX-1;
    for (head=0; s[head]==MARK ; head++)
      ;
    for (p=tail; p>=head  ; p--)
      if (!isdigit(s[p]))
     if (s[p-1]!=MARK)
     {  s[p-1]+=(s[p]-'0')/10;
        s[p]=(s[p]-'0')%10+'0';
     }
     else
     {  s[p-1]=(s[p]-'0')/10+'0';
        s[p]=(s[p]-'0')%10+'0';
     }
     return 1;
}
//The Judeg function , judge the symbol of the number
int Judge(int i)
{   if (i==0)
       return 0;
    else
       if (i>0)
      return 1;
       else
      return  -1;
}
//The Convert function , convert the original result to the final result ,wipe off the inuility symbol and number
int Convert(char c[],char d[],int length)
{   int i,j;
    for (i=0; i<length; i++)
      if (c[i]==MARK || c[i]=='0')
      ;
      else
     break;
    for (i,j=0; i<length; i++,j++)
      d[j]=c[i];
    d[j]='\0';
    return 1;
}