1.txt

巨型整数类

/*****************************************************************************
*
*   filename: BigInt.h
*
* descrpition:   no-length-limited integer number and basic calculation
*
* written by:   idealcat
* Data: 2007/12/6
*
* version: 1.0
*
* modification : 
*
*
********************************************************************************/
#define WIN32_LEAN_AND_MEAN   // 从 Windows 头中排除极少使用的资料
#include <stdio.h>
#include <tchar.h>

#pragma once

#include<iostream>
#include<string>
using namespace std;

class CBigInt
{
public:
CBigInt();
CBigInt(string s);
CBigInt(const CBigInt& ); //拷贝构造
CBigInt& operator = (const CBigInt& );
friend CBigInt operator + (const CBigInt& , const CBigInt& );
friend CBigInt operator - (const CBigInt& , const CBigInt& );
friend CBigInt operator * (const CBigInt& , const CBigInt& );
void display();
public:
~CBigInt(void);

private:

string digits;
unsigned int length;
friend CBigInt abs(const CBigInt& );
friend string toString(long );
friend long toLong(string );
friend string substring(string , int , int );
friend string substring(string , int );
};
/*****************************************************************************
*
*   filename: BigInt.cpp
*
* descrpition:   no-length-limited integer number and basic calculation
*
* written by:   idealcat
*
* Data: 2007/12/6
*
* version: 1.0
*
* modification : 
*
*
********************************************************************************/
#include "stdafx.h"
#include "BigInt.h"


CBigInt::CBigInt()
{
digits = "0";
length = 1;
}

CBigInt::CBigInt(string s)
{
string str = "";
int Zflag = 1, Cflag = 1;//Zflag判断首位是否是0，Cflag判断首位是否为符号，置1表示需要判断
for(int i=0; i<static_cast<int>(s.length()); i++)
{
   if(Zflag||Cflag){//开始判断首位
    if( s[i]>'0' && s[i]<='9'|| s[i] == '-')
     if(Cflag && s[i] == '-')//如果为负号
     { 
      str += s[i];
      Cflag =0;    //找到负号，不需要再判断符号了
     }
     else
     {
      str += s[i];
      Zflag = 0;    //找到不是0的第一位，如果没符号表示正数
      Cflag = 0;    //同时符号位也不要再判断了
     }
   }
   else
    if( s[i]>='0' && s[i]<='9')
     str += s[i];
}
if(str == ""){
   digits = "0";
   length = 1;
}
else{
   digits = str;
   length = (unsigned int)str.length();
}
}

CBigInt::CBigInt(const CBigInt& b) //拷贝构造
{
this->digits = b.digits;
this->length = b.length;
}

CBigInt& CBigInt::operator =(const CBigInt& b)
{
this->digits = b.digits;
this->length = b.length;
return *this;
}

void CBigInt::display()
{
cout<<this->digits<<endl;
}


CBigInt::~CBigInt(void)
{
}

CBigInt operator + (const CBigInt& x, const CBigInt& y)
{
//注意类型转换，因为string类中长度等信息是size_t类型，所以使用的时候要强制类型转换
//先将短字符串相加，再处理长字符串多出的部分，注意进位
int    i, j1, j2;
size_t   maxlength = x.length >= y.length ? x.length :y.length; //记录最长字符串
char   carry = 0;    //carry为进位
string   sumdigits = "";   //sumdigits为和字符串
char   temp, c1, c2;

for(i=0; i<static_cast<int>(maxlength); i++)
{
//从后向前，低位相加
//j1，j2表示x，y的索引位置，分别从末尾到首部
   j1 = static_cast<int>(x.length-1-i);
   j2 = static_cast<int>(y.length-1-i);
   if(j1 < 0 || j2 < 0)
    //如果有一个字符串已经到头，则退出开始单独处理较长的字符串的多出部分
    break;
   c1 = x.digits[j1] - '0'; //将字符转化成数字
   c2 = y.digits[j2] - '0';
   temp = c1 + c2 + carry;
   if(temp >= 10)
   {
    temp %= 10;   //使temp的值为0~9这几个数字
    carry = 1;
   }
   else
    carry = 0;
   temp += '0';   //将数字转成字符
   sumdigits = temp + sumdigits;
  
} // end for

if(j1<0){
  
   for( ; i<static_cast<int>(maxlength); i++){
    j2 = static_cast<int>(y.length-1-i);
    c2 = y.digits[j2]-'0';
    temp = c2 + carry ;
    if(temp >= 10){
     carry = 1;
     temp %= 10;
    }
    else
     carry =0;
    temp += '0';
    sumdigits = temp + sumdigits;
   }
}
else{
  
   for( ; i<static_cast<int>(maxlength); i++)
   {
    j1 = static_cast<int>(x.length-1-i);
    c1 = x.digits[j1]-'0';
    temp = c1 + carry;
    if(temp >= 10){
     carry = 1;
     temp %= 10;
    }
    else
     carry =0;
    temp += '0';
    sumdigits = temp + sumdigits;
   }
}
if(carry)          //如果有进位，最大位数加一
   sumdigits = '1' + sumdigits;
return CBigInt(sumdigits);
}


CBigInt operator -(const CBigInt& x, const CBigInt& y)
{
//与加法一样注意类型转换，string类中长度等信息是size_t类型
//此函数是计算 x-y，如果 x<y 则结果要加上负号
//与加法不同的是可能最大位数会加一
const char NEGATIVE_SIGN = '-';
short Bflag = 0;   //借位标志符号
string difference = ""; //差
int i=0, j1=0, j2=0;
char c1,c2,temp;
if(x.length != y.length){

   if(x.length > y.length){   //x比y大
    for(i=0; i< static_cast<int>(x.length); i++){
     j1 = static_cast<int>(x.length-1-i);
     j2 = static_cast<int>(y.length-1-i);
     if(j2<0)
      break;
     c1 = x.digits[j1] - '0';
     c2 = y.digits[j2] - '0';
     if(!Bflag){     //没有进位
      if(c1 < c2){   //不够减借一位
       temp = c1 + (10-c2);
       Bflag = 1;
      }
      else{     //够减
       temp = c1 - c2;
       Bflag = 0;
      }
     }
     else{      //有进位
      if(c1-1 < c2){
       temp = (c1-1) + (10-c2);
       Bflag = 1;
      }
      else{
       temp = c1-1 - c2;
       Bflag = 0;
      }
     }
     temp += '0';
     difference = temp + difference;
    }// end for
    for(; i< static_cast<int>(x.length); i++){
     j1 = static_cast<int>(x.length-1-i);
    
     if(!Bflag)   //如果没借位则直接赋值给差
      difference = x.digits[j1] + difference;
     else{    //如果有进位
      c1 = x.digits[j1] - '0';

      if(c1 == 1 || c1 == 0){
       if(c1 == 1){
        temp = '0';
        Bflag = 0;
       }
       else{
        temp = '9';
        Bflag = 1;
       }
      }
      else{
       temp = c1-1 + '0';
       Bflag = 0;
      }

      if(i!=static_cast<int>(x.length)-1 || temp!='0')
       difference = temp + difference;
     }// end if for Bflag judgement
    }//end for
   }// end if
   else{ 
    //++++++++y比x大+++++++++++++
    for(i=0; i< static_cast<int>(y.length); i++){
     j1 = static_cast<int>(x.length-1-i);
     j2 = static_cast<int>(y.length-1-i);
     if(j1<0)
      break;
     c1 = x.digits[j1] - '0';
     c2 = y.digits[j2] - '0';
     if(!Bflag){//没进位
      if(c2 < c1){
       temp = c2 + (10-c1);
       Bflag = 1;
      }
      else{
       temp = c2 - c1;
       Bflag = 0;
      }
      temp += '0';
      difference = temp + difference;
     }
     else{ //有进位
      if(c2-1 < c1){
       temp = (c2-1) + (10-c1);
       Bflag = 1;
      }
      else{
       temp = c2-1 - c1;
       Bflag = 0;
      }
      temp += '0';
      difference = temp + difference;
     }
    }// end for
    for(; i< static_cast<int>(y.length); i++){
     j2 = static_cast<int>(y.length-1-i);
    
     if(!Bflag)   //如果没借位则直接赋值给差
      difference = y.digits[j2] + difference;
     else{    //有进位
      c2 = y.digits[j2] - '0';
      if(c2 == 1 || c2 == 0){
       if(c2 == 1){
        temp = '0';
        Bflag = 0;
       }
       else{
        temp = '9';
        Bflag = 1;
       }
      }
      else{
       temp = c2-1 + '0';
       Bflag =0;
      }
      if(i != static_cast<int>(y.length)-1 || temp != '0')
       difference = temp + difference;
     }//end if for Bflag judgement
    }//end for
    difference = NEGATIVE_SIGN + difference;
   }// end else
  
}

//--------- x.length==y.length ------------
else{
   int k;
   for(i=0; i<static_cast<int>(x.length); i++){
    //通过for循环找到不同位置
    if(x.digits[i] != y.digits[i])
     break;     //找到不一样的位数后要退出！！
    else{
     if(i == (static_cast<int>(x.length)-1))
      return CBigInt("0");   //完全相等的出口  
    }
   }//end for
   if(x.digits[i] > y.digits[i]){//x比y大
    for(k = static_cast<int>(x.length)-1; k >= i; k--){
     c1 = x.digits[k] - '0';
     c2 = y.digits[k] - '0';
     if(!Bflag){//无进位
      if(c1 >= c2){//够减
       temp = c1 - c2;
       Bflag = 0;
      }
      else{ //不够减借位
       temp = c1+ (10-c2);
       Bflag = 1;
       }
      }
     else{//有进位
      if((c1-1) >= c2){//够减
       temp = c1-1 -c2;
       Bflag = 0;
      }
      else{//不够减继续借位
       temp = c1-1 + (10-c2);
       Bflag = 1;
      }
     }
      temp += '0';
      if(k != i || temp != '0')
       difference = temp + difference;
    }//end for
   }//end if x.digits[i] > y.digits[i] 
   //+++++++++++x.digits[i] < y.digits[i]++++++++
   else{
    for(k = static_cast<int>(x.length)-1; k >= i; k--){
     c1 = x.digits[k] - '0';
     c2 = y.digits[k] - '0';
      if(!Bflag){
       if(c2 >= c1){
        temp = c2 - c1;
        Bflag = 0;
       }
       else{
        temp = c2+ (10-c1);
        Bflag = 1;
       }
      }
      else{
       if((c2-1) >= c1){
        temp = c2-1 -c1;
        Bflag = 0;
       }
       else{
        temp = c2-1 + (10-c1);
        Bflag = 1;
       }
      }
      temp += '0';
      if(k != i || temp != '0')
       difference = temp + difference;
      
    }//end for
    difference = NEGATIVE_SIGN + difference;
   }//end else x.digits[i] < y.digits[i]


}//end else x.length==y.length
return CBigInt(difference);     //其他情况总出口
}




CBigInt operator *(const CBigInt& x, const CBigInt& y)
{
if( x.length + y.length >= 10){
    //partA, partB, partC, partD;
   int len;
   if(x.length != 1 && y.length != 1)
   {
    len = static_cast<int>(x.length<=y.length?x.length:y.length);//按短的分
    len = len/2;
    string partA = substring(x.digits, static_cast<int>(x.length)-len);
    string partB = substring(x.digits, static_cast<int>(x.length)-len, static_cast<int>(x.length));
    string partC = substring(y.digits, static_cast<int>(y.length)-len);
    string partD = substring(y.digits, static_cast<int>(y.length)-len, static_cast<int>(y.length));
    CBigInt A(partA);
    CBigInt B(partB);
    CBigInt C(partC);
    CBigInt D(partD);
    cout<<"A ";
    A.display();
    cout<<"B ";
    B.display();
    cout<<"C ";
    C.display();
    cout<<"D ";
    D.display();

    string s1 = "", s2 = "",s3 = "";
    s1 =(A*C).digits;
    int flag = 0;
    //
    if((A-B).digits[0]=='-'&&(D-C).digits[0]=='-' || (A-B).digits[0]!='-'&&(D-C).digits[0]!='-'){
     //(A-B)*(D-C)>=0
     s2 =(A*C + B*D + (abs(A-B))*(abs(D-C)) ).digits;
    }
    else
     if((A*C + B*D - abs(A-B)*abs(D-C)).digits[0] == '-'){
      s2 =(abs(A-B)*abs(D-C)-(A*C + B*D)).digits;
      flag = 1;
     }
     else{
      s2 =(A*C + B*D-abs(A-B)*abs(D-C)).digits;
      flag =0;
     }

    s3 = (B*D).digits;
    int i;
    string add = "";
    for(i=0; i<len; i++){
     add += '0';
    }

    s1 += add +add;
    s2 += add;
   
//*
    string s2t1a = (A-B).digits;
    string s2t1b = (D-C).digits;
    string s2t1 = toString(toLong(s2t1a)*toLong(s2t1b));
    string s2t2 = (A*C).digits;
    string s2t3 = (B*D).digits;
    cout<<"A*C ="<<s1<<endl;
    cout<<"A-B ="<<s2t1a<<"\tD-C="<<s2t1b<<endl;
    cout<<"(A-B)*(D-C)= "<<s2t1<<"\tA*C ="<<s2t2<<"\tB*D="<<s2t3<<endl;
    cout<<"(abs((A-B))*abs((D-C)) + A*C + B*D) "<<s2<<endl;
//*/ 
    string s;
    if(!flag)
     s = ( CBigInt(s1) + CBigInt(s2) + CBigInt(s3)).digits;
    else
     s = ( CBigInt(s1) - CBigInt(s2) + CBigInt(s3)).digits;
//*
    cout<<"B*D= "<<s3<<endl;
    cout<<"s="<<s<<endl;
//*/
    return CBigInt(s);
   }
   else
   {
    if(x.length)
    {//x位一位数
     len = y.length /2;
     string partC = substring(y.digits, static_cast<int>(y.length)-len);
     string partD = substring(y.digits, static_cast<int>(y.length)-len, static_cast<int>(y.length));
     CBigInt C(partC);
     CBigInt D(partD);

     string add = "";
     for(int i=0; i<len; i++){
      add += '0';
     }
     string s1 = (x*C).digits;
     s1 += add;
     string s2 = (x*D).digits;    
     return CBigInt( CBigInt(s1)+CBigInt(s2) );
    }
    else
    {//y位一位数 
     len = x.length /2;
     string partA = substring(x.digits, static_cast<int>(x.length)-len);
     string partB = substring(x.digits, static_cast<int>(x.length)-len, static_cast<int>(x.length));
     CBigInt A(partA);
     CBigInt B(partB);

     string add = "";
     for(int i=0; i<len; i++){
      add += '0';
     }
     string s1 = (y*A).digits;
     s1 += add;
     string s2 = (y*B).digits ;    
     return CBigInt( CBigInt(s1)+CBigInt(s2) );
    }
   }
}//end if-else 判断位数一位
else
   return CBigInt( toString( (toLong(x.digits))*(toLong(y.digits)) ) );

}

//private: friend string toString(long )
string toString(long l)
{//解决0-bug
char c = 0;
string str = "";
do{
   c = static_cast<char>(l%10) + '0';
   str = c + str;
   l = l/10;
}while(l);
return str;
}


//private: friend long toLong(string )
long toLong(string str)
{
int c = 0;
long l = 0;
for(int i=0; i<static_cast<int>(str.length()); i++){
   l *= 10;
   c = str[i]- '0';
   l += c;  
}
return l;
}

//private: friend string substring(string , int , int )
string substring(string s, int index , int last){
string str = "";
for(int i=index; i<last; i++)
   str += s[i]; 
return str;
}

//private: friend string substring(string , int )
string substring(string s, int last){
string str = "";
for(int i=0; i<last; i++)
   str += s[i];
return str;
}

//private: friend CBigInt abs(const CBigInt& )
CBigInt abs(const CBigInt& b)
{
string str = b.digits;
if(str[0] == '-'){

   str = substring(str, 1, static_cast<int>(str.length()) );
   return CBigInt(str);
}
else
   return b;
}