常用于计算大的正整数之间的四则运算。
在王道机试指南基础上，有修改其中存在的bug
#include<iostream>
using namespace std;
const int MAXN = 1000;
struct BitInteger {
int digit[MAXN];
int length;
BitInteger() {
memset(digit, 0, sizeof(digit));
length = 0;
}
BitInteger(int x) {
memset(digit, 0, sizeof(digit));
length = 0;
if (x == 0)
digit[length++] = x;
while (x != 0) {
digit[length++] = x % 10;
x /= 10;
}
}
BitInteger(string str) {
memset(digit, 0, sizeof(digit));
length = str.size();
for (int i = 0; i < length; ++i)
digit[i] = str[length - i - 1] - '0';
}
BitInteger operator=(int x) {
memset(digit, 0, sizeof(digit));
length = 0;
if (x == 0)
digit[length++] = x;
while (x != 0) {
digit[length++] = x % 10;
x /= 10;
}
return *this;
}
BitInteger operator=(string str) {
memset(digit, 0, sizeof(digit));
length = str.size();
for (int i = 0; i < length; ++i)
digit[i] = str[length - i - 1] - '0';
return *this;
}
bool operator<=(const BitInteger& b) {
if (length < b.length)
return true;
else if (b.length < length)
return false;
else {
for (int i = length - 1; i >= 0; --i) {
if (digit[i] != b.digit[i])
return digit[i] < b.digit[i];
}
}
return true;
}
bool operator>(const BitInteger b) {
if (length > b.length)
return true;
else if (length < b.length)
return false;
else {
for (int i = length - 1; i >= 0; --i) {
if (digit[i] != b.digit[i])
return digit[i] > b.digit[i];
}
}
return true;
}
bool operator<(const BitInteger b) {
if (length < b.length)
return true;
else if (length > b.length)
return false;
else {
for (int i = length - 1; i >= 0; --i) {
if (digit[i] != b.digit[i])
return digit[i] < b.digit[i];
}
}
return true;
}
BitInteger operator+(const BitInteger b) {
int carry = 0;
BitInteger ans;
for (int i = 0; i < length || i < b.length; ++i) {
int cur = digit[i] + b.digit[i] + carry;
carry = cur / 10;
ans.digit[ans.length++] = cur % 10;
}
if (carry != 0)
ans.digit[ans.length++] = carry;
return ans;
}
BitInteger operator-(BitInteger &b) {
int remain = 0,temp;
bool minus = false;
BitInteger ans;
if (*this < b) {
for (int i = max(length, b.length) - 1; i >= 0; --i) {
temp = digit[i];
digit[i] = b.digit[i];
b.digit[i] = temp;
}
temp = length;
length = b.length;
b.length = temp;
minus = true;
}
for (int i = 0; i < length; ++i) {
int cur = digit[i] - b.digit[i] - remain;
if (cur < 0) {
cur += 10;
remain = 1;
}
else
remain = 0;
ans.digit[ans.length++] = cur;
}
while (ans.digit[ans.length - 1] == 0 && ans.length > 1)
ans.length--;
if(minus)
ans.digit[ans.length - 1] *= -1;
return ans;
}
BitInteger operator*(const BitInteger& b) {
//* 简便方法一，借助加法进行运算
/*BitInteger ans;
int cnt;
for (int j = 0; j < b.length; ++j) {
cnt = b.digit[j] * int(pow(10,j));
while (cnt--)
ans = ans + *this;
}
return ans;*/
//* 方法二，借助加法进行运算
BitInteger ans;
ans.length = length + b.length;
for (int i = 0; i < length; ++i) {
for (int j = 0; j < b.length; ++j) {
ans.digit[i + j] = digit[i] * b.digit[j];
}
}
//最多向前进一位数值
for (int i = 0; i < ans.length; ++i) {
ans.digit[i + 1] += ans.digit[i] / 10;
ans.digit[i] = ans.digit[i] % 10;
}
//除去多余的前导数字0
while (ans.length > 1 && ans.digit[ans.length - 1] == 0)
ans.length--;
return ans;
}
BitInteger operator/(const BitInteger& b) {
BitInteger ans;
ans.length = length;
BitInteger remainder = 0;
BitInteger temp = b;
for (int i = length - 1; i >= 0; --i) {
if (!(remainder.length == 1 && remainder.digit[0] == 0)) {
for (int j = remainder.length - 1; j >= 0; --j)
remainder.digit[j + 1] = remainder.digit[j];
remainder.length++;
}
remainder.digit[0] = digit[i];
while (temp <= remainder) {
remainder = remainder - temp;
ans.digit[i]++;
}
}
while (ans.length > 1 && ans.digit[ans.length - 1] == 0)
ans.length--;
return ans;
}
BitInteger operator%(const BitInteger b) {
BitInteger remainder = 0;
BitInteger temp = b;
for (int i = length - 1; i >= 0; --i) {
if (!(remainder.length == 1 && remainder.digit[0] == 0)) {
for (int j = remainder.length - 1; j >= 0; --j)
remainder.digit[j + 1] = remainder.digit[j];
remainder.length++;
}
remainder.digit[0] = digit[i];
while (temp <= remainder)
remainder = remainder - temp;
}
return remainder;
}
friend istream& operator>>(istream& in, BitInteger& x) {
string str;
cin >> str;
x = str;
return in;
}
friend ostream& operator<<(ostream& out, const BitInteger& x) {
for (int i = x.length - 1; i >= 0; --i)
out << x.digit[i];
return out;
}
};
int main()
{
BitInteger a,b;
cin >> a;
cin >> b;
cout << "a = " << a << endl;
cout << "b = " << b << endl;
cout << "a + b = " << a + b << endl;
cout << "a - b = " << a - b << endl;
cout << "a * b = " << a * b << endl;
cout << "a / b = " << a / b << endl;
cout << "a % b = " << a % b << endl;
}
运行示例：
