【大数据】大数据字符串的加减乘除

在日常计算中，一般来说，数据不会太大，即使再大long long 8个字节也够用，但是现在来说数据很大，一般的数据类型都表示不了，那么就用字符串来表示数据。

那么就有字符串数据的加减乘除运算。

基本结构BigData.h

有两种成员变量; long long _value; string _strData;

两种构造函数：字符串，int 构造函数已经处理过字符串，正数的字符串是，”+…….”,负数的字符串是”-……….”。

#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> using namespace std; typedef long long INT64; class BigData { public: BigData(INT64 data); BigData(const string& str); BigData operator+(const BigData& b); BigData operator-(const BigData& b); BigData operator*(const BigData& b); BigData operator/(const BigData& b); BigData& operator=(const BigData& b); friend ostream& operator<<(ostream& out, const BigData& bigdata); private: //判断是否越界 bool IsINT64Overflow()const; //Add 这些函数的参数 肯定都带符号， string Add(string left, string right); string Sub(string left, string right); string Mul(string left, string right); string Div(string left, string right); //判断被除数大于除数 bool isLeftBig(char* left, size_t Lsize, char* right, size_t Rsize);//left前面不为0 //计算商值，并且返回余数 char loopsub(char*& left, size_t& Lsize, char*& right, size_t Rsize); private: INT64 _value; string _strData; };

构造函数以及输出运算符重载

INT64 UN_INT = 0xcccccccccccccccc; const INT64 MaxValue = 9223372036854775807; const INT64 MinValue = -9223372036854775807; ostream& operator<<(ostream& out, const BigData& bigdata) { char* pData = (char*)bigdata._strData.c_str(); if (*pData == '+') pData++; out << pData; return out; } BigData::BigData(INT64 data = UN_INT) :_value(data) { //数字放入字符串中 _strData = "+"; INT64 temp = _value; if (temp < 0) { _strData[0] = '-'; temp = 0 - temp; } else if (temp == 0) _strData = "+0"; while (temp != 0) { _strData += temp % 10 + '0'; temp /= 10; } reverse(_strData.begin() + 1, _strData.end()); } //模拟atoi BigData::BigData(const string& strData) : _value(0) , _strData("+0") { // "123456789" "+123456890" "12345asdfg123456" // "000001234567" " 12345678" // "aa12345689" "000000000000000000" " " if (strData.empty()) return; char* pData = (char*)strData.c_str(); char symbol = *pData; if (*pData == '-' || *pData == '+') pData++; //处理前置空格 while (isspace(*pData)) pData++; if ('\0' == *pData) return; //处理 前置0 while ('0' == *pData) pData++; if ('\0' == *pData) return; //处理前置非数字 if (*pData > '9' || *pData < '0') return; //处理剩余部分 size_t Length = strlen(pData); _strData.resize(Length + 1);//多加一个符号位 if (symbol == '-') _strData[0] = '-'; size_t count = 1; while (*pData >= '0' && *pData <= '9') { _value = _value * 10 + *pData - '0'; _strData[count++] = *pData++; } _strData.resize(count); if (symbol == '-') _value = 0 - _value; } //判断是否越界 bool BigData::IsINT64Overflow()const { std::string strTemp("+9223372036854775807"); if (_strData[0] == '-') strTemp = "-9223372036854775808"; if (_strData.size() < strTemp.size()) return false; else if (_strData.size() == strTemp.size() && _strData < strTemp) return false; return true; } BigData& BigData::operator=(const BigData& b) { if (this != &b) { BigData temp(b); std::swap(_value, temp._value); std::swap(_strData, temp._strData); } return *this; }

加法 只有当符号位相同时，才进行加法。

字符串相加，比较容易实现， (1)结果的字符串的位数要最大的那位，要多加一位，防止最后一位进位。 (1) 将字符串 位数大的 放在外面， (2)设置一个进位累加器，相加。

string Add(string left, string right) { size_t Lsize = left.size(); size_t Rsize = right.size(); string res; char symbol = 0; //正常调用add的为同号， //当为-时候，异号调用Add,位数相同时，符号位为left[0],位数不同时，符号位交换之前的left[0] if (Lsize < Rsize) //使left的位数大 { if (left[0] != right[0]) //异号 symbol = left[0]; std::swap(Lsize, Rsize); std::swap(left, right); } res.resize(Lsize + 1); //可能最后产生进位 if (symbol != 0) res[0] = symbol; else res[0] = left[0]; char takeover = 0;//进位 for (size_t idx = 1; idx < Lsize; ++idx) { char temp = left[Lsize - idx] - '0' + takeover; if (Rsize > idx) temp += right[Rsize - idx] - '0'; takeover = temp / 10; res[Lsize + 1 - idx] = temp % 10 + '0'; } res[1] = takeover + '0'; return res; } BigData BigData::operator+(const BigData& b) { if (!IsINT64Overflow() && !b.IsINT64Overflow()) { //没有超出范围 if (_strData[0] != b._strData[0])//异号 return BigData(_value + b._value); else { //10 - 2 = 8, 7 //-10 - -2 = -8,-7 //同号 但是没有超出范围 if ((_strData[0] == '+' && MaxValue - _value >= b._value) || (_strData[0] == '-' && MinValue - _value <= b._value)) return BigData(_value + b._value); } } if (_strData[0] == b._strData[0]) //同号 return BigData(Add(_strData, b._strData)); return BigData(Sub(_strData, b._strData)); }

减法 (1) 位数大的放在外面， (2)在减法过程中，注意借位问题。

string Sub(string left, string right) { size_t Lsize = left.size(); size_t Rsize = right.size(); char symbol = 0; if (Lsize < Rsize || (Lsize == Rsize && strcmp(left.c_str() + 1, right.c_str() + 1) < 0)) { std::swap(Lsize, Rsize); std::swap(left, right); if (left[0] == right[0] && left[0] == '+')//小的减去大的，且同号的话，比如left = 5，right = 10， symbol = '-'; if (left[0] == right[0] && left[0] == '-')//比如left = -5，right = -10， symbol = '+'; } string res; res.resize(Lsize);// 减去不可能产生进位 if (symbol != 0) res[0] = symbol; else res[0] = left[0]; for (size_t idx = 1; idx < Lsize; ++idx) { char temp = left[Lsize - idx] - '0'; if (Rsize > idx) temp -= right[Rsize - idx] - '0'; if (temp < 0) { int step = 1;//向前step位借位 while ((Lsize >(idx + step)) && left[Lsize - idx - step] == 0) { left[Lsize - idx - step] = '9'; step++; } left[Lsize - idx - step]--; //不为0时 要-1 temp += 10; } res[Lsize - idx] = temp % 10 + '0'; } return res; } BigData BigData::operator-(const BigData& b) { if (!IsINT64Overflow() && !b.IsINT64Overflow()) { //没有超出范围 if (_strData[0] == b._strData[0])//同号号 return BigData(_value - b._value); else { // [10,-10] 2和 -7 // -10 +2 = -8 // 10 + -7 = 3 //异号 但是没有超出范围 if ((_strData[0] == '+' && MinValue + _value <= b._value) || (_strData[0] == '-' && MaxValue + _value >= b._value)) return BigData(_value - b._value); } } if (_strData[0] == b._strData[0]) //同号 return BigData(Sub(_strData, b._strData)); return BigData(Add(_strData, b._strData)); }

乘法 (1) 同样大的放在外层left (2)内层的每个位于外层left相乘，然后与res中相加，

string Mul(string left, string right) { size_t LSize = left.size(); size_t RSize = right.size(); if (LSize > RSize) //位数小的放到外层循环 { std::swap(LSize, RSize); std::swap(left, right); } char takeover = 0; //进位 size_t resSize = LSize + RSize - 1; string res(resSize, '0');//全都初始化'0'; size_t offset = 0;//结果移位 for (size_t i = 1; i < LSize; ++i) { char cleft = left[LSize - i] - '0';// 外层循各个位的值 takeover = 0; for (size_t j = 1; j < RSize; ++j) { char resBit = res[resSize - offset - j] - '0'; char mulBit = (right[RSize - j] - '0') * cleft + takeover + resBit; takeover = mulBit / 10; res[resSize - offset - j] = mulBit % 10 + '0'; } offset++; } //最后一次进位没有写入到结果中 res[1] = takeover + '0'; //符号 if (left[0] == right[0]) res[0] = '+'; else res[0] = '-'; return res; } BigData BigData::operator*(const BigData& b) { if (_value == 0 || b._value == 0) return BigData(0); else if (strcmp(_strData.c_str() + 1, "1") == 0) return BigData(b._strData); else if (strcmp(b._strData.c_str() + 1, "1") == 0) return BigData(_strData); return BigData(Mul(_strData, b._strData)); }

除法 借助两个函数， isLeftBig：判断左边的数据是否大于右边的数据 loopsub：循环减去右边的值，计算差值。直到需要借位。

//判断被除数大于除数 bool isLeftBig(char* left, size_t Lsize, char* right, size_t Rsize)//left前面不为0 { if (Lsize == Rsize && strncmp(left, right, Rsize) >= 0) return true; else if (Lsize > Rsize) return true; return false; } //计算商值，并且返回余数 char loopsub(char*& left, size_t& Lsize, char*& right, size_t Rsize) { char count = '0';//相当于商值 while (isLeftBig(left, Lsize, right, Rsize)) { for (size_t i = 0; i < Lsize; ++i) { char temp = left[Lsize - 1 - i] - '0'; if (i < Rsize) temp -= (right[Rsize - 1 - i] - '0'); if (temp < 0) { //向前借位 size_t step = 1;//借的步数 while ((1 + i + step < Lsize) && left[Lsize - 1 - i - step] == 0) //肯定可以借到，因为左边大于右边 { left[Lsize - 1 - i - step] = '9'; step++; } left[Lsize - 1 - i - step]--; temp += 10; } left[Lsize - 1 - i] = temp + '0'; } count++; while (Lsize > 0 && *left == '0') //去除前面的0 { left++; Lsize--; } if (Lsize == 0) break; } return count; } string Div(string left, string right) { char symbol = '+'; if (left[0] != right[0]) symbol = '-'; string res; res.append(1, symbol); char* pleft = (char*)left.c_str() + 1; char* pright = (char*)right.c_str() + 1; size_t Lsize = left.size() - 1; size_t Rsize = right.size() - 1; size_t len = Rsize; while (*(pleft + len - 1) != '\0') //感觉这可能越界 { if (!isLeftBig(pleft, len, pright, Rsize)) { if (*pleft == '0') pleft++; else len++; res.append(1, '0'); continue; } else { res.append(1, loopsub(pleft, len, pright, Rsize)); len++; } } return res; } BigData BigData::operator/(const BigData& b) { //商值为0,1，-1 char* left = (char *)_strData.c_str(); char* right = (char *)b._strData.c_str(); //除数不能为0 if (b._value == 0) { cout << "除数不能为0" << endl; return BigData(0); } //商值为0 if (_strData.size() < b._strData.size()) return BigData(0); else if (_strData.size() == b._strData.size() && strcmp(_strData.c_str() + 1, b._strData.c_str() + 1) < 0) return BigData(0); //商值为 1 if (strcmp(left, right) == 0) return BigData(1); //商值为-1 if (strcmp(_strData.c_str() + 1, b._strData.c_str() + 1) == 0 && *left != *right) return BigData(-1); else if (b._value == 1) //被除数为1 return BigData(_strData); else if (b._value == -1) //被除数为-1 return BigData(b._strData); return BigData(Div(_strData, b._strData)); }