大數運算實現加減乘除四則運算

首先，讓我們先來熟悉一下兩種防止頭文件被重復引用的處理#pragma once和#ifndef的區別

        http://10739786.blog.51cto.com/10729786/1730827

    接下來，開始我們的主題 <大數運算>
    在平時生活中細心的你可能會發現，好多時候我們使用計算器時，總有一個顯示的最大值，當計算超過這個值時就不能再計算了，那如果我們想要計算更大的數值要怎么辦？

    本文通過C++編程實現 大數的加減乘除四則運算

    <思路與方法同樣都在程序內部>

    這次通過標準的三個文件來實現聲明<BIGDATA.h>、定義實現函數功能<BIGDATA.cpp>、測試<test.cpp>

<BIGDATA.h>

#pragma once

#ifndef __BIGDATA_H__
#define __BIGDATA_H__

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include<string.h>
#include<assert.h>

//1、考慮當數值小時，運算速度盡量貼近內置類型（所以，結構會有兩個-->內置類型long long 及大數的 char*）
//2、構造時可能的輸入{"1234" "0001234"  "1564adf"  "   "  "+(-)12345" }
//

typedef long long INT64;

//string MAX_INT64 = "9223372036854775807";
//string MIN_INT64 = "-9223372036854775808";

//enum{ MAX_INT64 = 9223372036854775807, MIN_INT64 = -9223372036854775808 };//不行enum后是int類型
//

const INT64 MAX_INT64 = 0x7fffffffffffffff;// 9223372036854775807;
const INT64 MIN_INT64 = 0x8000000000000000;//-9223372036854775808;


class BigData
{
public:
 BigData(INT64 value = 0);
 BigData(const string pData);

 BigData operator+(const BigData bigdata);
 BigData operator-(const BigData bigdata);
 BigData operator*(const BigData bigdata);
 BigData operator/(const BigData bigdata);

 ~BigData();

 void Print();

private:
 bool PDataIsOverINT64()const;
 friend std::ostream&operator<<(std::ostream& _cout, const BigData& bigdata);//不能在_cout前加const   ->_cout<<10<<endl;將不能通過
 
 BigData Add(string pData1, string pData2);//并不一定要寫成成員函數 (也可以寫成一般函數被使用)
 BigData Sub(string pData1, string pData2);
 BigData Mul(string pData1, string pData2);
 BigData Div(string pData1, string pData2);

private:
 INT64 _value;
 string _pData;
};

#endif __BIGDATA_H__


//<BIGDATA.cpp>


#include"BIGDATA.h"

BigData::BigData(INT64 value)//若輸入的數值位數大于MAX_DATA，系統編譯不通過，當位數一致且大于時，轉為負，無能為力
 :_value(value)
{
 //在_pData中加入value
 void Invert(string& pdata);
 size_t i = 0;
 INT64 tmp = 0;
 _pData.append(1, '+');
 if (value < 0)
 {
  _pData[0] = '-';
  value *= -1;
 }
 while (value != 0)
 {
  tmp = value % 10;
  _pData.append(1, (char)(tmp + '0'));
  value /= 10;
 }
 Invert(_pData);
}

BigData::BigData(const string  pData)
{
 //解決各種特殊情況
 //{"1234" "0001234"  "1564adf"  "   "  "+(-)12345" NULL }
 //參考atoi()函數處理辦法
 

 //跳過符號將輸入字符串都歸為一般

//  //判是否是數字字符isdigit(int c)是-1/否0  還有判空字符（宏定義） isspace(int c)  頭文件<ctype.h>

 char* tmp = (char*)&pData[0];
 _pData.append(1, '+');  //添加符號(默認為'+')

 if ((*tmp < '0' || *tmp > '9') && *tmp != ' '&& *tmp != '+'&& *tmp != '-'&& *tmp != '\t')  //排除其他符號
 {
  //cout << "false" << endl;
  _pData.append(1, '0');
  _value = 0;
  return;
 }

 while(isspace(*tmp)) //while (*tmp==' ')   //消除前面的空格(tab)
 {
  tmp++;
 }

 if (*tmp == '+' || *tmp == '-')  //跳過符號/修正符號
 {
  if (*tmp == '-')
  {
   _pData[0] = '-';
  }
  tmp++;
 }

 while (*tmp == '0')   //消除前面的0（必須先消除空格，再消除0，最后判斷+（-））
 {
  tmp++;
 }

//*********************
 //一個一個追加效率不高-->轉化為一次開辟
 //while(isdigit(*tmp))  //while (*tmp >= '0'&& *tmp <= '9')
 //{
 // _pData.append(1, *tmp++);
 //}
//*********************

 _pData.resize(strlen(tmp) + 1);
 int i = 1;
 while (isdigit(*tmp))
 {
  _pData[i++] = *tmp++;
 }

 if (*tmp != '\0')
 {
  //cout << "false" << endl;
  _value = 0;
  return;
 }

 //若超出INT64表示的范圍則用string管理，否則用INT64,string綜合管理
 if (!PDataIsOverINT64())
 {
  size_t i = 1;
  _value = 0;
  for (i = 1; i < _pData.size(); i++)
  {
   _value = _value * 10 + _pData[i] - '0';
  }
  if (_pData[0] == '-')
   _value *= -1;
 }

}

BigData::~BigData()
{}

bool BigData::PDataIsOverINT64()const
{
 std::string tmp("+9223372036854775807");
 if (_pData[0] == '-')
 {
  tmp = "-9223372036854775808";
 }

 if ((_pData.size() < tmp.size())||
  (_pData.size() == tmp.size() && _pData <= tmp))
 {
  return false;
 }
 return true;

}

std::ostream& operator<<(std::ostream& _cout, const BigData& bigdata)//不能在_cout前加const   ->_cout<<10<<endl;將不能通過
{
 if (!bigdata.PDataIsOverINT64())
 {
  _cout << bigdata._value;
 }
 else
 {
  char* tmp = (char*)&bigdata._pData[0];
  if ('+' == *tmp)
  {
   tmp++;
  }
  while (*tmp)
  {
   _cout << *tmp++;
  }
  //_cout << endl;
 }
 return _cout;
}

void BigData::Print()
{
 if (!PDataIsOverINT64())
 {
  cout << _value << endl;   //printf("%lld\n", _value);
  return;
 }
 if (*(char*)&_pData[0] == '+')
 {
  printf("%s\n", &_pData[1]);
  return;
 }
 printf("%s\n",&_pData[0]);
}

void Invert(string& pdata)
{
 int left = 1;
 int right = pdata.size() - 1;
 while (left < right)
 {
  swap(pdata[left++], pdata[right--]);
 }
}

BigData BigData:: operator+(const BigData bigdata)
{
 //1、都在INT64范圍內<運算后在范圍內，運算后不在范圍內>（再進行構造可以解決）
 //2、都不在INT64范圍內<運算后在范圍內，運算后不在范圍內>
 //3、一個在一個不在<運算后在范圍內，運算后不在范圍內>
 //
 //如果全部用string進行計算，就達不到數值小時用基本類型提高運算的目的
 //由于實現結構是若在INT64范圍內_value與_pData共同管理，若不在只由_pData管理

 //所以，可以將上面分化成兩類<1、都在范圍內(<運算后在范圍內，運算后不在范圍內>) 2、至少有一個不在范圍內>


 if (!PDataIsOverINT64() && !bigdata.PDataIsOverINT64())
 {
  if (_pData[0] != bigdata._pData[0])//若異號，則肯定不會溢出
  {
   return BigData(_value + bigdata._value);
  }
  else //同號
  {
   if (_pData[0] == '+')//為正
   {
    if (_value <= MAX_INT64 - bigdata._value)//結果不溢出
    {
     return BigData(_value + bigdata._value);
    }
    else //結果溢出
    {
     return BigData(Add(_pData, bigdata._pData));
    }
   }
   else //為負
   {
    if (_value >= MIN_INT64 - bigdata._value)//結果不溢出
    {
     return BigData(_value + bigdata._value);
    }
    else //結果溢出
    {
     return BigData(Add(_pData, bigdata._pData));
    }
   }
  }
 }
 else//至少有一個溢出
 {
  return BigData(Add(_pData, bigdata._pData));
 }
}



BigData BigData:: operator-(const BigData bigdata)
{
 //1、都在范圍內(運算后在范圍內，運算后不在范圍內) 
 //2、至少有一個不在范圍內

 if (!PDataIsOverINT64() && !bigdata.PDataIsOverINT64())
 {
  //同號相減不可能溢出，異號相減才可能溢出

  if (_pData[0] == bigdata._pData[0])//同號
  {
   return BigData(_value - bigdata._value);
  }
  else// 異號
  {
   if (_pData[0] == '+')//第一個為正，第二個為負
   {
    if (_value < MAX_INT64 + bigdata._value)//結果不溢出
    {
     return BigData(_value - bigdata._value);
    }
    else   //結果溢出
    {
     return Sub(_pData, bigdata._pData);
    }
   }
   else //第一個為負，第二個為正
   {
    if (_value > MIN_INT64 + bigdata._value)//結果不溢出
    {
     return BigData(_value - bigdata._value);
    }
    else   //結果溢出
    {
     return Sub(_pData, bigdata._pData);
    }
   }
  }
 }
 else
 {
  return Sub(_pData, bigdata._pData);
 }
}

void _EachAdd0(string& pdate) //各項添加'0'
{
 int size = pdate.size();
 int i = 1;
 for (i = 1; i < size; i++)
 {
  pdate[i] += '0';
 }
}

void _EachSub0(string& pdate) //各項去'0'
{
 int size = pdate.size();
 int i = 1;
 for (i = 1; i < size; i++)
 {
  pdate[i] -= '0';
 }
}

BigData BigData:: Add(string pData1, string pData2)
{
 //轉化為string中從低到高字符相加
 //若同號 就相加，若異號，轉為減

 if (pData1[0] != pData2[0])//異號
 {
  if (pData1[0] == '+')
  {
   pData2[0] = '+';
   return Sub(pData1, pData2);
  }
  else
  {
   pData1[0] = '+';
   return Sub(pData2, pData1);
  }
 }
 else//同號  
 {
  //判斷哪個位數多，放在前面
  if (pData1.size() < pData2.size())
  {
   swap(pData1, pData2);
  }

  std::string tmp;
  int size1 = pData1.size();
  int size2 = pData2.size();
  int sizet = size1 + 1;
  int flag = 0;
  tmp.resize(size1 + 1);
  tmp[0] = pData1[0];

  for (int i = 0; i < size1 - 1; i++)
  {
   flag = 0;
   char cur = '0';
   if (size2 - 1 - i > 0)
   {
    cur = pData2[size2 - 1 - i];
   }
   tmp[sizet - i-1] = pData1[size1 - 1 - i] + cur - 2 * '0';//tmp存數值而不是數字字符
   if (tmp[size1 - i] / 10 == 1)
   {
    flag = 1;
    tmp[size1 - i] %= 10;
   }
   
   pData1[size1 - i - 2] += flag;
  }
  tmp[1] = flag;
  _EachAdd0(tmp);

  return BigData(tmp);
 }
}


BigData BigData::Sub(string pData1, string pData2)
{
 //轉化為string中從低到高字符相減
 //若同號 就相減（注意前后位數不同），若異號，轉為加

 if (pData1[0] != pData2[0])//異號
 {
  if (pData1[0] == '+')
  {
   pData2[0] = '+';
   return Add(pData1, pData2);
  }
  else
  {
   pData2[0] = '-';
   return Add(pData1, pData2);
  }
 }
 else  //同號
 {
  //取數值的符號，將較大值放在前面

  if (pData1.size() < pData2.size() ||
   (pData1.size() == pData2.size() && (strcmp(pData1.c_str(), pData2.c_str()) < 0)))
  {
   if (pData1[0] == '+')
   {
    pData2[0] = '-';
   }
   else
   {
    pData2[0] = '+';
   }
   swap(pData1, pData2);   
  }
  std::string tmp;
  int size1 = pData1.size();
  int size2 = pData2.size();
  int sizet = size1;
  int flag = 0;
  tmp.resize(sizet);
  tmp[0] = pData1[0];
  for (int i = 0; i < size1 - 1; i++)
  {
   flag = 0;
   int cur = 0;
   if (i < size2 - 1)
   {
    cur = pData1[size1 - i - 1] - pData2[size2 - i - 1];
   }
   else
   {
    cur = pData1[size1 - i - 1] - '0';
   }
   if (cur < 0)
   {
    flag = 1;
    cur += 10;
   }
   tmp[sizet - 1 - i] = cur + '0';

   pData1[size1 - 2 - i] -= flag;

  }
  return BigData(tmp);
 }
}


BigData BigData:: operator*(const BigData bigdata)
{
 //1、都在INT64范圍內<運算后在范圍內，運算后不在范圍內>
 //   同號與 MAX_DATA比較  異號與MIN_DATA比較
 //2、至少一個不在范圍內
 if (0 == _value || 0 == bigdata._value)
 {
  return BigData(0);
 }
 if (!PDataIsOverINT64() && !bigdata.PDataIsOverINT64())
 {
  if (_pData[0]==bigdata._pData[0])//同號
  {
   if (_value >= 0)//為正
   {
    if (_value < MAX_INT64 / bigdata._value)//結果在范圍內
    {
     return BigData(_value*bigdata._value);
    }
    else // 結果不在范圍內
    {
     return Mul(_pData,bigdata._pData);
    }
   }
   else//為負
   {
    if (_value > MAX_INT64 / bigdata._value)//結果在范圍內
    {
     return BigData(_value*bigdata._value);
    }
    else // 結果不在范圍內
    {
     return Mul(_pData, bigdata._pData);
    }
   }
  }
  else  //異號
  {
   if (_value >= 0)//為正 負
   {
    if (_value < MIN_INT64 / bigdata._value)//結果在范圍內
    {
     return BigData(_value*bigdata._value);
    }
    else // 結果不在范圍內
    {
     return Mul(_pData, bigdata._pData);
    }
   }
   else //為 負 正
   {
    if (_value > MIN_INT64 / bigdata._value)//結果在范圍內
    {
     return BigData(_value*bigdata._value);
    }
    else // 結果不在范圍內
    {
     return Mul(_pData, bigdata._pData);
    }
   }
  }
 }
 else
 {
  return Mul(_pData, bigdata._pData);
 }
}

BigData BigData::Mul(string pData1, string pData2)
{
 //同號 異號  先大數 后小數  
 //為提高效率 外層循環次數少，內層次數多

 std::string tmp;
 int size1 = pData1.size();
 int size2 = pData2.size();
 int sizet = size1 + size2;
 tmp.resize(size1 + size2);
 tmp[0] = '+';
 if (pData1[0] != pData2[0])//同號 異號 
 {
  tmp[0] = '-';
 }

 if (size1 < size2 || (size1 == size2&&strcmp(&pData1[0], pData2.c_str()) < 0))//先大數 后小數
 {
  swap(pData1, pData2);
  swap(size1, size2);
 }

 _EachSub0(pData1);
 _EachSub0(pData2);
 //tmp初始化時 全為 0
 for (int i = 1; i < size2; i++)//小數位數  
 {
  if (pData2[size2 - i] == 0)  //若位數上為0則跳過
  {
   continue;
  }
  for (int j = 1; j < size1; j++)//大數位數
  {
   if (pData1[size1 - j] == 0)  //若位數上為0則跳過
   {
    continue;
   }
   tmp[sizet - j - i + 1] += pData1[size1 - j] * pData2[size2 - i];
   if (tmp[sizet - j - i + 1]>=10)
   {
    tmp[sizet - j - i] += tmp[sizet - j - i + 1] / 10;
    tmp[sizet - j - i + 1] %= 10;
   }
  }

 }

 for (int i = 0; i < sizet - 1; i++)
 {
  if (tmp[sizet - i - 1] >= 10)
  {
   tmp[sizet - i - 2] += tmp[sizet - i - 1] / 10;
   tmp[sizet - i - 1] %= 10;
  }
 }

 _EachAdd0(tmp);
 return BigData(tmp);
}

BigData BigData:: operator/(const BigData bigdata)
{
 //1、排除除數為0
 //2、在范圍內，不在范圍內
 //3、不在范圍內<左（被除數）比右（除數）小為0，左比右大>
 //4、正負

 if (0 == bigdata._value)
 {
  assert(false);
 }

 if (!PDataIsOverINT64() && !bigdata.PDataIsOverINT64())
 {
  return BigData(_value / bigdata._value);
 }
 else
 {
  //左（被除數）比右（除數）小為0
  if (_pData.size() < bigdata._pData.size() ||
   (_pData.size() == bigdata._pData.size() && _pData[0] == bigdata._pData[0]&&
   strcmp((char*)&_pData[0],(char*)&bigdata._pData[0]) < 0))
  {
   return BigData(0);//正0 負0 都記為0 
  }
  else //左比右大
  {
   return Div(_pData, bigdata._pData);
  }
 }
}



BigData BigData::Div(string pData1, string pData2)
{
 //正負且 參數左大右小
 char* _trueDiv(char* tp1, char* tmp2, int size, string& cur);

 string cur;
 cur.append(1, '+');
 if (pData1[0] != pData2[0])
 {
  cur[0] = '-';
 }

 char* tmp1 = (char*)malloc(pData1.size());// *tmp2 = (char*)malloc(pData2.size());
 strcpy(tmp1, &pData1[1]); //strcpy內部實現free(tmp1)
 char*tmp2 = &pData2[1];
 int size2 = strlen(tmp2);
 int sizermd = size2;
 int excursion = size2;
 char* rmd = NULL;

 while (strlen(tmp1) > strlen(tmp2) || 
  (strlen(tmp1) == strlen(tmp2) && strcmp(tmp1, tmp2) > 0))//左大于右時，循環
 {  
  while (sizermd < size2 || (sizermd == size2&&strncmp(tmp1, tmp2, sizermd)<0))//不夠 商0
  {
   cur.append(1, '0');
   sizermd++;
   ++excursion;
  }

  rmd = _trueDiv(tmp1, tmp2, sizermd, cur);// 16713  31071  
  sizermd = strlen(rmd);
  
  strcat(rmd, &pData1[++excursion]);

  tmp1 = rmd;
  sizermd++;  // 將余數與剩余被除數相接
 }

 return BigData(cur);
}

char* _trueDiv(char* tp1, char* tp2, int size1, string& cur)
{
 //只有tp1和 tp2位數相同且比tp2大，或者比tp2多一位的情況
 int size2 = strlen(tp2);

 int i = 0;
 tp1[size1] = '\0';

 char count = 0;
 int flag = 0;

 while (size1 > size2 ||
  (size1 == size2&&strcmp(tp1, tp2) > 0))//tp1大于tp2
 {
  for (i = 0; i < size1; i++)
  {
   flag = 0;
   int count = 0;
   if (i < size2)
   {
    count = tp1[size1 - i - 1] - tp2[size2 - i - 1];
   }
   else
   {
    count = tp1[size1 - i - 1] - '0';
   }
   if (count < 0)
   {
    flag = 1;
    count += 10;
   }
   tp1[size1 - 1 - i] = count + '0';

   tp1[size1 - 2 - i] -= flag;

   while (*tp1 == '0' && size1>1)//可能出現整除情況
   {
    tp1++;
    size1--;
   }

  }
  count++;
 }

 cur.append(1, count + '0');
 return tp1;
}


//<test.cpp>


#include"BIGDATA.h"

void test()
{
 BigData b0(13215156);
 BigData b10(-13215156);
 BigData b11(9787687678661325156);//當傳入的數值大于MAX_DATA且位數相等時，編譯器不能檢測，導致由正轉負
 BigData b12(-9223372036854775807);
 BigData b1("a13215jfiow");
 b1.Print();
 cout << b1<< endl;
 BigData b2("+000023215");
 cout << b2 << endl;
 b2.Print();
 BigData b3(" 33215jfiow"); //(Tab、空格鍵消除用isspace（int）)
 cout << b3 << endl;
 b3.Print();
 BigData b4("    -33215jfiow");
 cout << b4 << endl;
 b4.Print();
 BigData b5("43215jfiow");
 b5.Print();
 cout << b5 << endl;

 //BigData b6("4321537537354373783783");
 //b6.Print(); 
 //cout << b6 << endl;
 BigData b7("-43215378338735373783537");
 cout << b7 << endl;
 b7.Print();
 BigData b8("-9223372036854775808");
 cout << b8 << endl;
 b8.Print();
 BigData b9("-999999");
 cout << b9 << endl;
 b9.Print();

 BigData b101("43215378338735373783537");
 BigData b102("-43215378338735373783537");
 BigData b103("-43215378338735373783537");
 BigData b110("-43215378338735373783537");

 (b2 + b9).Print();
 cout << (b2 + b9) << endl;
}

void testAdd()
{
 BigData b1("-45353");
 BigData b2("37353753");
 BigData b3("-9223372036854775808");
 BigData b4(" 9223372036854775800");
 BigData b5("-9223372036854775810");
 BigData b6(" 9223372036854775900");

 cout << (b1 + b1) << endl; 
 cout << (b2 + b2) << endl;
 cout << (b1 + b2) << endl;
 cout << (b1 + b4) << endl;

 cout << b3 << endl;
 cout << (b1 + b3) << endl;
 cout << (b2 + b4) << endl;

 cout << (b2 + b5) << endl;
 cout << (b1 + b6) << endl;
 cout << (b6 + b1) << endl;

}

void testSub()
{
 BigData b1("-45353");
 BigData b2("37353753");
 BigData b3("-9223372036854775808");
 BigData b4(" 9223372036854775800");
 BigData b5("-9223372036854775810");
 BigData b6(" 9223372036854775900");

 cout << (b1 - b2) << endl;
 cout << (b2 - b1) << endl; 
 cout << (b3 - b1) << endl;
 cout << (b1 - b4) << endl;
 cout << (b3 - b2) << endl;
 cout << (b4 - b1) << endl;
 cout << (b1 - b3) << endl;
 cout << (b2 - b4) << endl;
 cout << endl;


 cout << (b5 - b1) << endl;
 cout << (b1 - b5) << endl;
 cout << endl;
 cout << (b6 - b2) << endl;
 cout << (b2 - b6) << endl;
 cout << endl;
 cout << (b6 - b5) << endl;
 cout << (b5 - b6) << endl;
 cout << (b2 - b5) << endl;
 cout << (b1 - b6) << endl;
 cout << (b6 - b1) << endl;

}


void testMul()
{
 BigData b1("-45353");
 BigData b2("37353753");
 BigData b3("-9223372036854775808");
 BigData b4(" 9223372036854775800");
 BigData b5("-9223372036854775810");
 BigData b6(" 9223372036854775900");

 cout << (BigData("999") * BigData("22222222222222222222222222222")) << endl;

 cout << (b2 * b1) << endl;
 cout << (b1 * b2) << endl;
 cout << (b1 * BigData(0)) << endl;
 cout << (BigData(0) * b2) << endl;
 cout << endl;
 cout << (b3 * b1) << endl;
 cout << (b1 * b3) << endl;
 cout << (b1 * b4) << endl;
 cout << (b4 * b1) << endl;
 cout << (b3 * b2) << endl;
 cout << (b2 * b4) << endl;
 cout << endl;


 cout << (BigData(0) * b6) << endl;
 cout << (b5 * BigData(0)) << endl;
 cout << (b5 * b1) << endl;
 cout << (b1* b5) << endl;
 cout << endl;
 cout << (b6 * b2) << endl;
 cout << (b2 * b6) << endl;
 cout << endl;
 cout << (b6 * b5) << endl;
 cout << (b5 * b6) << endl;
 cout << (b2 * b5) << endl;
 cout << endl;
 cout << (b1 * b6) << endl;
 cout << (b6 * b1) << endl;
 BigData b7("-203367738338252");
 cout << b7*b1 << endl;
}


void testDiv()
{
 BigData b1("-45353");
 BigData b2("37353753");
 BigData b3("-9223372036854775808");
 BigData b4(" 9223372036854775800");
 BigData b5("-9223372036854775810");
 BigData b6(" 9223372036854775900");
 BigData b7("-1231123203367738338252");


 //1、排除除數為0
 //cout << (b1 / BigData(0)) << endl;

 //2、在范圍內

 cout << (b1 / b2) << endl;
 cout << (b2 / b1) << endl;


 //3、不在范圍內<左（被除數）比右（除數）小為0，左比右大>
 cout << (b2 / b5) << endl;
 cout << (b2 / b6) << endl;

 cout << (b5 / b2) << endl;
 cout << (b6 / b2) << endl;
 cout << (b6 / b1) << endl;
 cout << (b5 / b1) << endl;

 cout << b7 / b1 << endl;
}

int main()
{
 //testAdd();
 //testSub();
 //testMul();
 testDiv();
 system("pause");
 return 0;
}