实现大整数类

雨点打透心脏的1/2处 2022-09-30 14:56 367阅读 0赞

//copyright@ 2011/03/06 yansha //实现大整数类 \#include <string> \#include <vector> \#include <iostream> using namespace std; class CBigInt \{ public: // input friend istream& operator >> (istream &, CBigInt &); // output friend ostream& operator << (ostream &os, const CBigInt &value) \{ if (value.bigInt\[0\] == '-') os << value.bigInt; else \{ // 正数不输出符号 os << value.bigInt.substr(1); \} return os; \} friend bool operator == (const CBigInt &, const CBigInt &); friend bool operator < (const CBigInt &lValue, const CBigInt &rValue) \{ if (lValue.bigInt\[0\] != rValue.bigInt\[0\]) \{ // '+'ASCII码为43，'-'ASCII码为45 return lValue.bigInt\[0\] > rValue.bigInt\[0\]; \} else \{ if (lValue.bigInt\[0\] == '+') return lValue.smaller(rValue.bigInt); // 正数的情况 else return lValue.greater(rValue.bigInt); // 负数的情况 \} \} friend bool operator > (const CBigInt &lValue, const CBigInt &rValue) \{ if (lValue.bigInt\[0\] != rValue.bigInt\[0\]) return lValue.bigInt\[0\] < rValue.bigInt\[0\]; else \{ if (lValue.bigInt\[0\] == '+') return lValue.greater(rValue.bigInt); else return lValue.smaller(rValue.bigInt); \} \} string bigInt; public: CBigInt(); CBigInt(int); CBigInt(const string &); CBigInt(const CBigInt &); CBigInt(const char \*); CBigInt& operator = (const CBigInt &); CBigInt& operator += (const CBigInt &); CBigInt& operator -= (const CBigInt &); CBigInt& operator \*= (const CBigInt &); CBigInt& operator /= (const CBigInt &); CBigInt& operator %= (const CBigInt &); // prefix increment CBigInt& operator ++ (); // prefix decrement CBigInt& operator -- (); // postfix increment CBigInt operator ++ (int); // postfix decrement CBigInt operator -- (int); private: // unsigned += void plus(const string &); // unsigned -= void minus(const string &); // unsigned == bool equal(const string &) const; // unsigned < bool smaller(const string &) const; // unsigned > bool greater(const string &) const; \}; /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/ /\* 构造函数 /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/ // 默认构造函数 inline CBigInt::CBigInt() : bigInt("+0") \{\} // 构造函数 inline CBigInt::CBigInt(const string &str) : bigInt(str) \{ if (bigInt.size() > 0) \{ // 没有正负符号 if (bigInt\[0\] != '+' && bigInt\[0\] != '-') \{ string::size\_type i = 0; for (; i < bigInt.size() - 1 && bigInt\[i\] == '0'; i++); if (i > 0) bigInt.replace((string::size\_type)0, i, "+"); else bigInt.insert((string::size\_type)0, 1, '+'); \} else \{ if (bigInt.size() == 1) bigInt = "+0"; else \{ string::size\_type j = 1; // 去掉多余的0 for (; j < bigInt.size() - 1 && bigInt\[j\] == '0'; j++); if (j > 1) bigInt.erase((string::size\_type)1, j - 1); if (bigInt == "-0") bigInt = "+0"; \} \} \} else bigInt = "+0"; \} // 复制构造函数 inline CBigInt::CBigInt(const CBigInt &value) : bigInt(value.bigInt) \{\} inline CBigInt::CBigInt(int num) \{ if (num == 0) bigInt = "+0"; else if (num > 0) bigInt = '+'; else \{ bigInt = '-'; num \*= -1; \} string temp = ""; while (num != 0) \{ temp += num % 10 + '0'; num = num / 10; \} for (int i = temp.size() - 1; i >= 0; i--) bigInt += temp\[i\]; \} inline CBigInt::CBigInt(const char \*str) : bigInt(str) \{ if (bigInt.size() > 0) \{ if (bigInt\[0\] != '+' && bigInt\[0\] != '-') \{ string::size\_type i = 0; // 去除多余的0 for (; i < bigInt.size() - 1 && bigInt\[i\] == '0'; i++); if (i > 0) bigInt.replace((string::size\_type)0, i, "+"); else bigInt.insert((string::size\_type)0, 1, '+'); \} else \{ if (bigInt.size() == 0) bigInt = "+0"; else \{ string::size\_type j = 1; for (; j < bigInt.size() - 1 && bigInt\[j\] == '0'; j++); if (j > 1) bigInt.erase((string::size\_type)1, j - 1); // 处理特殊情况“-0” if (bigInt == "-0") bigInt = "+0"; \} \} \} else bigInt = "+0"; \} inline bool operator == (const CBigInt &lValue, const CBigInt &rValue) \{ return lValue.bigInt == rValue.bigInt; \} inline bool operator != (const CBigInt &lValue, const CBigInt &rValue) \{ return !(lValue.bigInt == rValue.bigInt); \} inline bool operator <= (const CBigInt &lValue, const CBigInt &rValue) \{ return !(lValue > rValue); \} inline bool operator >= (const CBigInt &lValue, const CBigInt &rValue) \{ return !(lValue < rValue); \} inline CBigInt& CBigInt::operator = (const CBigInt &value) \{ bigInt = value.bigInt; return \*this; \} // unsigned == inline bool CBigInt::equal(const string &value) const \{ return bigInt.substr(1) == value.substr(1); \} // unsigned < inline bool CBigInt::smaller(const string &value) const \{ if (bigInt.size() == value.size()) return bigInt.substr(1) < value.substr(1); else return bigInt.size() < value.size(); \} // unsigned > inline bool CBigInt::greater(const string &value) const \{ if (bigInt.size() == value.size()) return bigInt.substr(1) > value.substr(1); else return bigInt.size() > value.size(); \} /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/ /\* 实现+,-,\*,/运算 /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/ void CBigInt::plus(const string &value) \{ if (bigInt.size() < value.size()) bigInt.insert((string::size\_type)1, (value.size() - bigInt.size()), '0'); string::size\_type i = bigInt.size() - 1; string::size\_type j = value.size() - 1; while (j > 1) \{ bigInt\[i\] += value\[j\] - '0'; if (bigInt\[i\] > '9') \{ bigInt\[i\] -= 10; ++bigInt\[i-1\]; \} i--; j--; \} // 最高位进位 bigInt\[i\] += value\[1\] - '0'; while (i > 1 && bigInt\[i\] > '9') \{ bigInt\[i\] -= 10; i--; ++bigInt\[i\]; \} if (bigInt\[1\] > '9') \{ bigInt\[1\] -= 10; bigInt.insert((string::size\_type)1, 1, '1'); \} \} void CBigInt::minus(const string &vlaue) \{ string::size\_type i = bigInt.size() - 1; string::size\_type j = vlaue.size() - 1; while (j >= 1) \{ bigInt\[i\] -= vlaue\[j\] - '0'; if (bigInt\[i\] < '0') \{ bigInt\[i\] += 10; --bigInt\[i-1\]; \} i--; j--; \} // 向前借位 while (i > 1 && bigInt\[i\] < '0') \{ bigInt\[i\] += 10; i--; --bigInt\[i\]; \} // 去除多余的0 string::size\_type k = 1; for (; k < bigInt.size() - 1 && bigInt\[k\] == '0'; k++); if (k > 1) bigInt.erase((string::size\_type)1, k - 1); \} CBigInt& CBigInt::operator += (const CBigInt &value) \{ if (bigInt\[0\] == value.bigInt\[0\]) plus(value.bigInt); else \{ // 互为相反数的情况 if (equal(value.bigInt)) bigInt = "+0"; // 绝对值小于的情况 else if (smaller(value.bigInt)) \{ string temp = bigInt; bigInt = value.bigInt; minus(temp); \} else minus(value.bigInt); \} return \*this; \} CBigInt& CBigInt::operator -= (const CBigInt &value) \{ // 处理过程与+=类似 if (bigInt\[0\] == value.bigInt\[0\]) \{ if (equal(value.bigInt)) bigInt = "+0"; else if (smaller(value.bigInt)) \{ string temp = bigInt; bigInt = value.bigInt; minus(temp); if (bigInt\[0\] == '+') bigInt\[0\] = '-'; else bigInt\[0\] = '+'; \} else minus(value.bigInt); \} else plus(value.bigInt); return \*this; \} CBigInt operator + (const CBigInt &lValue, const CBigInt &rValue) \{ CBigInt sum(lValue); sum += rValue; return sum; \} CBigInt operator - (const CBigInt &lValue, const CBigInt &rValue) \{ CBigInt diff(lValue); diff -= rValue; return diff; \} // prefix increment CBigInt& CBigInt::operator ++ () \{ string::size\_type i = bigInt.size() - 1; if (bigInt\[0\] == '+') \{ ++bigInt\[i\]; while (i > 1 && bigInt\[i\] > '9') \{ bigInt\[i\] -= 10; i--; ++bigInt\[i\]; \} if (bigInt\[i\] > '9') \{ bigInt\[i\] -= 10; bigInt.insert((string::size\_type)1, 1, '1'); \} \} else \{ --bigInt\[i\]; while(i > 1 && bigInt\[i\] < '0') \{ bigInt\[i\] += 10; i--; --bigInt\[i\]; \} string::size\_type j = 1; for (; j < bigInt.size() - 1 && bigInt\[j\] == '0'; j++); if (j > 1) bigInt.erase(1, j - 1); if (bigInt\[1\] == '0') bigInt\[0\] = '+'; \} return \*this; \} CBigInt& CBigInt::operator -- () \{ string::size\_type i = bigInt.size() - 1; // 对正数和负数分别处理 if (bigInt\[0\] == '+') \{ // 对0进行处理 if (bigInt\[1\] == '0') bigInt = "-1"; else \{ --bigInt\[i\]; while (i > 1 && bigInt\[i\] < '0') \{ bigInt\[i\] += 10; i--; --bigInt\[i\]; \} string::size\_type j = 1; for (; j < bigInt.size() - 1 && bigInt\[j\] == '0'; j++); if (j > 1) bigInt.erase(1, j - 1); \} \} else \{ ++bigInt\[i\]; while (i > 1 && bigInt\[i\] > '9') \{ bigInt\[i\] -= 10; i--; ++bigInt\[i\]; \} if (bigInt\[1\] > '9') \{ bigInt\[1\] += 10; bigInt.insert((string::size\_type)1, 1, '1'); \} \} return \*this; \} // postfix increment CBigInt CBigInt::operator ++ (int) \{ CBigInt temp(\*this); ++(\*this); return temp; \} // postfix decrement CBigInt CBigInt::operator -- (int) \{ CBigInt temp(\*this); --(\*this); return temp; \} // 模拟笔算过程 CBigInt& CBigInt::operator \*= (const CBigInt &value) \{ // 乘数或被乘数有一方为0则返回结果0 if (bigInt\[1\] == '0' || value.bigInt\[1\] == '0') \{ bigInt = "+0"; return \*this; \} string::size\_type sizeofMultiplicand = bigInt.size(); string::size\_type sizeofMultiplier = value.bigInt.size(); vector<unsigned int> product(sizeofMultiplier + sizeofMultiplicand - 1); // 初始化 for (string::size\_type i = 1; i < sizeofMultiplicand; ++i) bigInt\[i\] -= '0'; // 笔算乘法过程 for (string::size\_type j = sizeofMultiplier - 1; j > 0; --j) \{ if (value.bigInt\[j\] > '0') \{ for (string::size\_type k = sizeofMultiplicand - 1; k > 0; --k) product\[k+j\] += bigInt\[k\] \* (value.bigInt\[j\] - '0'); \} \} // 处理符号 if (bigInt\[0\] == value.bigInt\[0\]) product\[0\] = '+'; else product\[0\] = '-'; vector<unsigned int>::size\_type sizeofProduct = product.size(); bigInt = string(sizeofProduct, '0'); bigInt\[0\] = product\[0\]; // 处理进位问题 for (vector<unsigned int>::size\_type n = sizeofProduct - 1; n > 1; --n) \{ product\[n-1\] += product\[n\] / 10; product\[n\] %= 10; bigInt\[n\] += product\[n\]; \} if (product\[1\] == 0) bigInt.erase(1, 1); else bigInt\[1\] += product\[1\]; return \*this; \} // 重复做差法求商 CBigInt& CBigInt::operator /= (const CBigInt &value) \{ // 除数为0 if (value.bigInt == "+0") \{ bigInt = "\*Error!"; return \*this; \} // 被除数大于除数 if (value.smaller(bigInt) == true) \{ string::size\_type sizeofDividend = bigInt.size(); string::size\_type sizeofDivisor = value.bigInt.size(); string answer(sizeofDividend, '0'); // 符号处理 if (bigInt\[0\] == value.bigInt\[0\]) answer\[0\] = '+'; else answer\[0\] = '-'; string::size\_type start = 1; string::size\_type end = sizeofDivisor - 1; while (end < sizeofDividend) \{ // 试商过程，从高位到低位 while (value.greater(bigInt.substr(start - 1, end - start + 2)) == false) \{ string::size\_type j = end; // 减法过程 for (string::size\_type i = sizeofDivisor - 1; i > 0; i--, j--) \{ bigInt\[j\] -= value.bigInt\[i\] - '0'; if (bigInt\[j\] < '0') \{ bigInt\[j\] += 10; --bigInt\[j-1\]; \} \} // 商的相应位加1 ++answer\[end\]; // 以除数做边界去掉前缀0 while (start <= end && bigInt\[start\] == '0') ++start; \} // 以被除数做边界去掉前缀0 while (start < sizeofDividend && bigInt\[start\] == '0') ++start; // 如果end-start+1 < sizeofDivisor - 1,则进行补位 if (end - start + 2 < sizeofDivisor) end = sizeofDivisor + start - 2; else ++end; \} start = 1; for (; start < answer.size() - 1 && answer\[start\] == '0'; ++start); if (start > 1) answer.erase(1, start - 1); bigInt = answer; \} // 绝对值相等的情况 else if (value.equal(bigInt) == true) \{ string answer = "-1"; if (bigInt\[0\] == value.bigInt\[0\]) answer = "+1"; bigInt = answer; \} else bigInt = "+0"; return \*this; \} // 求余，与上面去商过程基本一致 CBigInt& CBigInt::operator %= (const CBigInt &value) \{ if (value.bigInt == "+0") \{ bigInt = "\*Error!"; return \*this; \} // 求余，余数为剩余bigInt值 if (value.smaller(bigInt) == true) \{ string::size\_type sizeofDivident = bigInt.size(); string::size\_type sizeofDivisor = value.bigInt.size(); string::size\_type start = 1; string::size\_type end = sizeofDivisor - 1; while (end < sizeofDivident) \{ // 除数的值不大于被除数的值 while (value.greater(bigInt.substr(start - 1, end - start + 2)) == false) \{ string::size\_type j = end; for (string::size\_type i = sizeofDivisor - 1; i > 0; --i, --j) \{ bigInt\[j\] -= value.bigInt\[i\] - '0'; if (bigInt\[j\] < '0') \{ bigInt\[j\] += 10; --bigInt\[j-1\]; \} \} while (start <= end && bigInt\[start\] == '0') ++start; \} while (start < sizeofDivident && bigInt\[start\] == '0') ++start; if (end - start + 2 < sizeofDivisor) end = sizeofDivisor + start - 2; else ++end; \} start = 1; for (; start < sizeofDivident - 1 && bigInt\[start\] == '0'; start++); if (start > 1) bigInt.erase(1, start - 1); if (bigInt == "-0") bigInt\[0\] = '+'; \} else if (value.equal(bigInt)) bigInt = "+0"; return \*this; \} CBigInt operator \* (const CBigInt &lValue, const CBigInt &rValue) \{ CBigInt product(lValue); product \*= rValue; return product; \} CBigInt operator / (const CBigInt &lValue, const CBigInt &rValue) \{ CBigInt quotient(lValue); quotient /= rValue; return quotient; \} CBigInt operator % (const CBigInt &lValue, const CBigInt &rValue) \{ CBigInt mod(lValue); mod %= rValue; return mod; \}