大整数.txt

学算法的入门算法

struct BigInt
{
     int a[MAX];
     int len;
     BigInt();
     BigInt(char str[]);
     void convert(char str[]);
     void add(BigInt rhs);
     void sub(BigInt rhs);
     void mul(BigInt rhs);
     int div(int rhs);   //返回余数
     void exp(int rhs);
     void cout();
};

BigInt :: BigInt()
{
     memset(a,0,sizeof(a));
}

BigInt :: BigInt(char str[])
{
     memset(a,0,sizeof(a));
     convert(str);
}

void BigInt :: convert(char str[])
{
     int s;
     int i,j,k;
     int l = strlen(str);

    for (i = j = 0; i+4 < l; i += 4)  //每个a[i]为4位,0为最小一直到修改后的len = j为最高位；
   {
      s = 1;
      for (k = 0; k < 4; k++)
     {
          a[j] += (str[l-1-i-k]-'0') * s;  
          s *= 10;
     }
     j++;
   }
   if (i != l)   //剩余的；
   {
      s = 1;
      for (; i < l; i++)
      {
           a[j] += (str[l-1-i]-'0') * s;
           s *= 10;
      }
      j++;
   }
   len = j;
}

void BigInt :: add(BigInt rhs)
{
     int i,j;
     int c = 0;

     for (i=j=0; i<len || j < rhs.len; i++,j++)
     {
          a[i] += c+rhs.a[j];
          c = 0;
          if (a[i] >= 10000)
          {
               c = a[i]/10000;
               a[i] %= 10000;
          }
    }
    a[i] = c;
    for ( ; a[i] == 0 && i >= 0; i--);
    len = i+1;
    if (len == 0) len = 1;
}

void BigInt :: sub(BigInt rhs)
{
     int i,j;
     int c = 0;

     for (i=j=0; i<len; i++)
    {
         a[i] -= c+rhs.a[i];
         c = 0;
         if (a[i] < 0)
         {
              c = 1;
              a[i] += 10000;
         }
     }
     for ( ; a[i] == 0 && i >= 0; i--);
     len = i+1;
     if (len == 0) len = 1;
}

void BigInt :: mul(BigInt rhs)
{
     int i,j;
     int c = 0;
     int tm[MAX] = {0};

     for (i=0; i<len; i++)
     {
          for (j=0; j<rhs.len; j++)
          {
              tm[i+j] += rhs.a[j]*a[i];
              if (tm[i+j] >= 10000)
              {
                    tm[i+j+1] += tm[i+j]/10000;
                    tm[i+j] %= 10000;
              }
          }
     }
     for (i+=j; tm[i] == 0; i--);
     len = i+1;
     if (len == 0) len = 1;
     memcpy(a,tm,sizeof(int)*len);
}

int BigInt :: div(int rhs)
{
    int i;
    int c = 0;

    for (i=len-1; i>=0; i--)
    {
        c = c*10000+a[i];
        a[i] = c/rhs;
        c %= rhs;
    }
    for (i=len-1; i>=0 && a[i] == 0; i--);
    len = i+1;
    if (len == 0) len = 1;
    return c;
}

//2^rhs
void BigInt :: exp(int rhs)
{
    BigInt b("2"); 
// 2^s = 2^(s/2)*2^(s/2)*2^(s%2);
    while (rhs)
    {
        if (rhs & 1) mul(b);
        b.mul(b);
        rhs >>= 1;
    }
}

void BigInt :: cout()
{
    int i;

    printf("%d",a[len-1]);
    for (i=len-2; i>=0; i--)
         printf("%04d",a[i]);
    printf("\n");
}