学步园

一个简单的高精度大数运算的实现，实现了加法，乘法，乘方

#include <string><br /> #include <sstream><br /> #include <iostream><br /> #include <cctype><br /> #include <algorithm><br /> using namespace std;<br /> #define sz(a) int((a).size())<br /> class BigNum {<br /> public:<br /> BigNum() : integer("0"), dec_digits("0") {}<br /> BigNum(string digit) {<br /> int n = count(digit.begin(), digit.end(), '.');<br /> if (n == 0) {<br /> get_BigNum(digit, "0");<br /> }<br /> else if (n == 1) {<br /> if (digit[0] == '.') {<br /> get_BigNum("0", digit.substr(1, sz(digit) - 1));<br /> }<br /> else {<br /> *find(digit.begin(), digit.end(), '.') = ' ';<br /> istringstream is(digit);<br /> string a, b;<br /> is >> a >> b;<br /> get_BigNum(a, b);<br /> }<br /> }<br /> else {<br /> integer = "0";<br /> dec_digits = "0";<br /> }<br /> }<br /> BigNum(string a, string b) {<br /> get_BigNum(a, b);<br /> }<br /> BigNum operator +(BigNum rhs) {<br /> int overflow = 0;<br /> string b = add_decimal(dec_digits, rhs.dec_digits, overflow);<br /> string a = add_integer(integer, rhs.integer, overflow);<br /> while ( *b.rbegin() == '0' && sz(b) != 1) {<br /> b.erase(b.end() - 1);<br /> }<br /> return BigNum(a, b);<br /> }<br /> BigNum operator *(BigNum b) {<br /> BigNum total("0");<br /> for ( int i = 0 ; i < sz(b.integer) ; ++i ) {<br /> total = total + multi_bignum_leftshift(b.integer[i] - '0', sz(b.integer) - i - 1);<br /> }<br /> for ( int i = 0 ; i < sz(b.dec_digits) ; ++i ) {<br /> total = total + multi_bignum_rightshift(b.dec_digits[i] - '0', i + 1);<br /> }<br /> return total;<br /> }<br /> BigNum operator ^(int n) {<br /> BigNum total("1");<br /> for ( int i = 0 ; i < n ; ++i ) {<br /> total = *this * total;<br /> }<br /> return total;<br /> }<br /> friend ostream &operator <<(ostream &os, BigNum a);<br /> private:<br /> string integer;<br /> string dec_digits;<br /> void get_BigNum(string a = "0", string b = "0") {<br /> if (sz(a) == 0) {<br /> a = "0";<br /> }<br /> if (sz(b) == 0) {<br /> b = "0";<br /> }<br /> integer = a;<br /> dec_digits = b;<br /> if (!valid_string(integer)) {<br /> integer = "0";<br /> }<br /> else {<br /> while (integer[0] == '0' && sz(integer) != 1 ) {<br /> integer.erase(integer.begin());<br /> }<br /> }<br /> if (!valid_string(dec_digits)) {<br /> dec_digits = "0";<br /> }<br /> else {<br /> while (*dec_digits.rbegin() == '0' && sz(dec_digits) != 1 ) {<br /> dec_digits.erase(dec_digits.end() - 1);<br /> }<br /> }<br /> }<br /> bool valid_string(const string s) {<br /> for ( int i = 0 ; i < sz(s) ; ++i ) {<br /> if (!isdigit(s[i]) ) {<br /> return false;<br /> }<br /> }<br /> return true;<br /> }<br /> string add_decimal(string a, string b, int &overflow) {<br /> int m = max(sz(a), sz(b));<br /> a += string(m - sz(a), '0');<br /> b += string(m - sz(b), '0');<br /> return add_string(a, b, overflow, false);<br /> }<br /> string add_integer(string a, string b, int &overflow) {<br /> int m = max(sz(a), sz(b));<br /> a = string(m - sz(a), '0') + a;<br /> b = string(m - sz(b), '0') + b;<br /> return add_string(a, b, overflow, true);<br /> }<br /> string add_string(string a, string b, int &overflow, bool carry) {<br /> for ( int i = sz(a) - 1; i >= 0; --i) {<br /> int k = a[i] - '0' + b[i] - '0' + overflow;<br /> overflow = k / 10;<br /> k %= 10;<br /> a[i] = char(k + '0');<br /> }<br /> if (overflow != 0 && carry) {<br /> a = char(overflow + '0') + a;<br /> }<br /> return a;<br /> }<br /> string multi_string(string a, int n, int &overflow, bool carry) {<br /> for ( int i = sz(a) - 1 ; i >= 0 ; --i ) {<br /> int k = (a[i] - '0') * n + overflow;<br /> overflow = k / 10;<br /> k %= 10;<br /> a[i] = char(k + '0');<br /> }<br /> if (overflow != 0 && carry ) {<br /> a = char(overflow + '0') + a;<br /> }<br /> return a;<br /> }<br /> BigNum multi_bignum_leftshift(int j, int n) { //*this * j * 10^n<br /> int overflow = 0;<br /> string d = multi_string(dec_digits, j, overflow, false);<br /> string i = multi_string(integer, j, overflow, true);<br /> while (sz(d) <= n ) {<br /> d += "0";<br /> }<br /> return BigNum(i + d.substr(0, n), d.substr(n, sz(d) -n));<br /> }<br /> BigNum multi_bignum_rightshift(int j, int n) { //*this * j / 10^n<br /> int overflow = 0;<br /> string d = multi_string(dec_digits, j, overflow, false);<br /> string i = multi_string(integer, j, overflow, true);<br /> while (sz(i) <= n ) {<br /> i = "0" + i;<br /> }<br /> return BigNum(i.substr(0, sz(i) - n), i.substr(sz(i) - n, n) + d);<br /> }<br /> };<br /> ostream &operator <<(ostream &os, BigNum a) {<br /> os << a.integer << "." << a.dec_digits;<br /> return os;<br /> }<br /> int main(int argc, char *argv[]) {<br /> BigNum a("111111111111111111111111111111.422");<br /> BigNum b("1.17800000000000");<br /> BigNum c(".456");<br /> BigNum d(".3x5.");<br /> cout << a << endl;<br /> cout << b << endl;<br /> cout << c << endl;<br /> cout << d << endl;<br /> cout << a + b << endl;<br /> cout << a * b << endl;<br /> cout << (a ^ 5) << endl;<br /> return 0;<br /> }

E:/>make

g++ -Wall -O2 -o a.exe BigNum.cpp

111111111111111111111111111111.422

1.178

0.456

0.0

111111111111111111111111111112.6

130888888888888888888888888889.255116

16935087808430286711036596724990939728022489796609595420753582415282223238327490

728039428594047924943690833036969296690993088119224372978373892868.6374280665456

32