溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
相信大家被特別大的兩個數據做運算折磨過。當兩個操作數或者運算結果超過類型的表示范圍后會有意想不到的錯誤，這時候我們的電腦還不如我們高中用過的科學計算器，這是作為一個程序員所不能忍受的。所以我們得找到其他的方式來計算。這就是我們今天要討論的字符串模擬大數運算。
我們的運算一般使用int類型來算的，那么首先我們先復習一下各種int類型的數據表示范圍：
unsigned int 0～4294967295 int -2147483648～2147483647 unsigned long 0～4294967295 long -2147483648～2147483647 long long的最大值：9223372036854775807 long long的最小值：-9223372036854775808 unsigned long long的最大值：1844674407370955161 __int64的最大值：9223372036854775807 __int64的最小值：-9223372036854775808 unsigned __int64的最大值：18446744073709551615
可以看到，在64位操作系統下，long long int表示的最大范圍是-9223372036854775808--9223372036854775807所以當我們的兩個操作數或者運算結果超過這個范圍我們就定義它已經溢出，得用字符串來模擬運算。所以我們得有一個_IsINT64OverFlow()函數，用來判斷是否溢出：
bool BigData:: _IsINT64OverFlow()const
{
if (_value >= Min_INT64 && _value <= Max_INT64)
return false;
return true;
} 我們是用字符串來模擬的，用一個類來封裝大數運算的加減乘除這些功能，所以先設計一下BigData這個類的基本構架。
#ifndef BIGDATA1_H
#define BIGDATA1_H
#include<iostream>
#include<string>
#include<assert.h>
#define Max_INT64 9223372036854775807
#define Min_INT64 (-9223372036854775807-1)
//不能直接用-9223372036854775808，當編譯器看到9223372036854775808時直接判定
//9223372036854775808>INT64_MAX,直接用unsigned int64表示。當編譯器看到負號時，
//直接對9223372036854775808取反，直接是它本身，編譯器存不了那么大的數，報錯
#define INT64 long long int
using namespace std;
class BigData
{
public:
BigData(INT64 data);
BigData(const char *str);
BigData operator+(BigData& d);//加法
BigData operator-(BigData& d);//減法
BigData operator*(BigData& d);//乘法
BigData operator/(BigData& d);//除法
private:
friend string Add(string& left, string& right);
friend string Sub(string& left, string& right);
friend string Mul(string& left, string& right);
friend string Div(string& left, string& right);
bool _IsINT64OverFlow()const;//判斷數據是否溢出
friend ostream& operator<<(ostream& _cout, const BigData& d);
void _INT64ToString();//將long long int數據轉換成字符串
private:
string _strvalue;
INT64 _value;
};
#endif這里有一個問題就是在用-9223372036854775807表示INT64_MIN時出現了一些問題；
error C4146: 一元負運算符應用于無符號類型，結果仍為無符號類型。
那時候各種搞不懂，然后就查了一下各位大神的解釋，大體意思就是不能直用-9223372036854775808表示。當編譯器看到9223372036854775808時直接判定9223372036854775808>INT64_MAX,直接用unsigned int64表示。當編譯器看到負號時，直接對9223372036854775808取反，直接是它本身，編譯器存不了那么大的數，編譯器就報錯。詳細解釋見一元負運算符。
現在大體的框架已經搭好了。來看詳細的實現過程：
（一）兩個構造函數
BigData::BigData(INT64 data)
:_value(data)
{
_INT64ToString();
}
BigData::BigData(const char *str)
: _value(0)
{
if (str == NULL)
{
assert(false);
return;
}
char symbol;
if (str[0] == '+')
{
symbol = '+';
str++;
}
else if (str[0] == '-')
{
symbol = '-';
str++;
}
else if (str[0] >= '0'&&str[0] <= '9')
{
symbol = '+';
}
else
{
return;
}
char* tmpstr = (char*)str;
while (*tmpstr == '0')//跳過前面的‘0’
tmpstr++;
int i = 0;//剩下字符串的長度
while (*tmpstr >= '0'&& *tmpstr <= '9')
{
i++;
_value = _value * 10 + *tmpstr - '0';
tmpstr++;
}
if (symbol == '-')
{
_value = 0 - _value;
}
_strvalue.resize(i + 1);//相當于給_strvalue開辟空間
_strvalue[0] = symbol;
int j = 1;
while (i--)
{
_strvalue[j++] = *str++;
}
}
void BigData::_INT64ToString()
{
INT64 tmp = _value;
INT64 sym = tmp;
string str;
if (sym >= 0)
{
str.push_back('+');
}
else
{
str.push_back('-');
tmp = 0 - tmp;
}
while (tmp)
{
char ctmp = tmp % 10 + '0';
str.push_back(ctmp);
tmp /= 10;
}
int right = str.size()-1;
int left = 1;
while (left < right)
{
swap(str[left++], str[right--]);
}
_strvalue = str;
}使用字符串構造比較麻煩，我們在構造_strvalue的時候還要把字符串數據轉換為long long int類型的_value，方便以后計算，如果字符串表示的數據沒有溢出的話直接用內置的long long int來計算。字符串轉換為int的重點就是要從字符串的最后一個字符開始轉化，每次循環數據乘以10。最后可以算出整個字符串的值，如果是負數，用0-_value即可。
還有long long int類型轉換為字符串函數。算法不難，只是字符串的第一個字符統一保存數據的符號，方便以后好計算。
（二）加法
BigData BigData::operator+( BigData& d)
{
if (!_IsINT64OverFlow() && !d._IsINT64OverFlow()
&& (_value + d._value) <= Max_INT64 && (_value + d._value) >= Min_INT64)
{
_value += d._value;
}
else
{
OverflowFlag = true;
_strvalue = Add(_strvalue, d._strvalue);
}
return *this;
}
string Add(string& left, string& right)
{
if (left[0] != right[0])//符號不等
{
if (left[0] == '+')
{
right[0] = '+';
return Sub(left, right);
}
else
{
left[0] = '+';
return Sub(right, left);
}
}
else
{
int lsize = left.size();
int rsize = right.size();
if (lsize == rsize)
{
int carry = 0;
while (--lsize && --rsize)
{
char tmp = left[lsize];
left[lsize] = (left[lsize] - '0' + right[rsize] - '0') % 10 + carry + '0';
carry = (tmp - '0' + right[rsize] - '0') / 10;
}
if (carry == 1)
{
left.insert(1, "1");
}
return left;
}
else
{
if (lsize > rsize)
{
int carry = 0;//進位
while (--lsize && --rsize)//不能為--rsize&&-lsize
{
char tmp = left[lsize];
left[lsize] = (left[lsize] - '0' + right[rsize] - '0') % 10 + carry + '0';
carry = (tmp - '0' + right[rsize] - '0') / 10;
}
while (carry == 1)
{
left[lsize] = left[lsize] + carry;
carry = (left[lsize] - '0' + carry) / 10;
lsize--;
}
return left;
}
else
{
int carry = 0;
while (--rsize && --lsize)//注意不能為--lsize&&--rsize，
//當lsize為1時不執行--lsize直接跳出
{
char tmp = right[rsize];
right[rsize] = (left[lsize] - '0' + right[rsize] - '0') % 10
+ '0' + carry;
carry = (tmp - '0' + left[lsize] - '0') / 10;
}
while (carry == 1)//當進位為1就一直往前加進位
{
right[rsize] = right[rsize] + carry;
carry = (right[rsize] - '0' + carry) / 10;
rsize--;
}
return right;
}
}
}
}加減乘除法都是用+-*/的重載來實現，實現時自己寫的ADD，SUB，MUL，DIV。+調用ADD，-調用SUB，*調用MUL，/調用DIV。以后+-*/的重載函數我就不貼出來了，換個調用函數就行。這樣的話方便以后的相互調用，只需要修改一下符號位。因為乘法是用加法模擬的，除法使用減法模擬的，減法用加法模擬的，按理來說我們使用加法就可以實現所有的運算。但是那個效率真的是慘不忍睹。
在這里，ADD的算法核心就是要保存低位向高位的進位。和我們手算是一樣的。從兩個字符串的最后一位開始往前相加，直到有一個字符串遇到_strvalue[0]的字符位為止，最后還要記得把最后的進位加上。在這里要考慮被加數加上進位以后還有進位的情況，所以在這我們使用了while來循環加。不用擔心字符串的空間不夠，因為兩個位數一樣的數相加，最多進位為1.
（三）減法
string Sub(string& left, string& right)
{
if (left[0] != right[0])
{
if (left[0] == '+')
{
right[0] = '+';
return Add(left, right);
}
else
{
right[0] = '-';
return Add(left, right);
}
}
else
{
int lsize = left.size();
int rsize = right.size();
if (lsize == rsize)
{
int borrow =0;
while (--lsize && --rsize)
{
if (left[lsize] < right[rsize])
{
left[lsize] = left[lsize] + 10 - right[rsize] - borrow + '0';
borrow = 1;
}
else
{
left[lsize] = left[lsize] - right[rsize] - borrow + '0';
borrow = 0;
}
}
return left;
}
else if (lsize > rsize)
{
int borrow = 0;
while (--lsize && --rsize)
{
if (left[lsize] < right[rsize])
{
left[lsize] = left[lsize] + 10 - right[rsize] - borrow + '0';
borrow = 1;
}
else
{
left[lsize] = left[lsize] - right[rsize] - borrow + '0';
borrow = 0;
}
}
while ( borrow==1 )
{
if (left[lsize] == '0')
{
left[lsize] = left[lsize] - '0' + 10 - borrow + '0';//若借位為0，
//向更高位借位,eg:1000-10
lsize--;
}
else
{
left[lsize] = left[lsize] - '0' - borrow + '0';
borrow = 0;
}
}
return left;
}
else
{
int borrow = 0;
while (--rsize && --lsize)
//得先讓rsize--，若--lsize為0；將不會執行--rsize;
{
if (right[rsize] < left[lsize])
{
right[rsize] = right[rsize] + 10 - left[lsize] - borrow + '0';
borrow = 1;
}
else
{
right[rsize] = right[rsize] - left[lsize] - borrow + '0';
borrow = 0;
}
}
while (borrow == 1)
{
if (right[rsize] == '0')
{
right[rsize] = right[rsize] - '0' + 10 - borrow + '0';//若借位為0，
//向更高位借位,eg:1000-10
rsize--;
}
else
{
right[rsize] = right[rsize] - '0' - borrow + '0';
borrow = 0;
}
}
return right;
}
}
}減法的算法核心和加法差不多，每次從兩個字符串的最后一位開始計算。要定義一個借位，低位向高位的借位。只要借位borrow為1就一直循環借位。
加法和減法之間可以相互調用，當一個正數加一個負數時就可以調用減法，會很方便，而且易懂。這里就體現了我們封裝ADD,SUB,MUL,DIV的好處。
還有要注意的就是要用最大的字符串（最長的字符串)來減小的字符串。這樣可以保證結果用最長的字符串就可以保存，不用考慮空間的問題。
（四）乘法
string Mul(string& left, string& right)
{
string newstr;//創建一個臨時sting存放相乘后的結果
int lsize = left.size();
int rsize = right.size();
newstr.resize(lsize + rsize);
int newsize = newstr.size();
while (--newsize)//初始化string，如果不初始化，string里存的是‘\0’
{
newstr[newsize] = '0';
}
if (left[0] != right[0])//符號不等
{
newstr[0] = '-';
}
else
{
newstr[0] = '+';
}
int flag = 0;//標志每次積的最低位
int carry = 0;
if (lsize <= rsize)
{
while (--lsize)
{
newsize = newstr.size() - flag;
rsize = right.size();
while (--rsize)
{
char tmp = left[lsize];
newstr[--newsize] = ((left[lsize] - '0') * (right[rsize] - '0')
+ newstr[newsize]-'0') % 10 + carry + '0';
carry = ((tmp - '0') * (right[rsize] - '0')) / 10;
}
newstr[--newsize] = carry + '0';//把最后的進位存起來
flag++;
}
}
else
{
while (--rsize)
{
newsize = newstr.size() - flag;
lsize = left.size();
while (--lsize)
{
char tmp = left[lsize];
newstr[--newsize] = ((left[lsize] - '0') * (right[rsize] - '0')
+ newstr[newsize] - '0') % 10 + carry + '0';
carry = ((tmp - '0') * (right[rsize] - '0')) / 10;
}
newstr[--newsize] = carry + '0';
flag++;
}
}
return newstr;
}乘法的話就略微抽象一點，只要把握住一點，保存進位就會非常簡單。在寫之前應該想清楚的是進位的最大值，乘法中進位的最大值為9，所以也不用考慮空間的問題。最長的字符串完全可以存下來。
乘法中要注意的是不能破環兩個乘數的值，如果修改了會產生意想不到的結果。所以定義一個newstr來存放結果而不像加減法那樣直接在最長的串上操作。
（四）除法
string Div(string& left, string& right)
{
string newstr;//創建一個臨時sting存放相除后的結果
int lsize = left.size();
int rsize = right.size();
newstr.resize(lsize);
if (left[0] != right[0])
{
newstr[0] = '-';
}
else
{
newstr[0] = '+';
}
if (lsize < rsize)
{
newstr.push_back('0');
return newstr;
}
else
{
left[0] = '+';
right[0] = '+';
int i = 0;
int flag = rsize;
int j = 0;
string tmp;
tmp.resize(rsize);
while (j < flag)//將left的高位復制給臨時變量
{
tmp[j] = left[j];
j++;
}
j--;
while (j < lsize)
{
newstr[j] = '0';
while (Compare(tmp, right))
{
newstr[j]++;
tmp = Sub(tmp, right);
}
tmp.push_back(left[++j]);
}
return newstr;
}
}除法說難也難，說簡單也簡單。要想簡單的話我們直接用一個循環就可以搞定，循環相減，直到被減數小于減數。但是程序員總是不會屑于寫這種效率低到爆的代碼的。現在限于個人的知識范圍，能想到效率最高的算法就是從被除數字符串截下和除數字符串一樣長的字符串相減，使用一個newstr來標記商，newstr長度和被除數長度一樣，全部初始化為‘0’。每次在與被除數相同下標的值++。直到被除數小于除數，再將原字符串的下一位push_back()到newstr，重復以上步驟。
其他函數較為簡單，在這就不一一詳述了，現在一個字符串模擬大數運算就寫好了，可以丟棄手中的科學計算器，讓我們的代碼跑起來。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
