互联网面试宝典

您现在的位置是: 首页 > 数据结构

问题详情

实现一个支持任意精度计算的大数类。

面试宝典 2023-06-12 Web前端开发工程师 32
可以使用字符串或数组来存储大整数,并针对加法、减法、乘法、除法等操作进行实现。

以下是一个简单的大数类实现(使用字符串存储):

```cpp
#include <iostream>
#include <string>
using namespace std;

class BigInteger {
private:
string num;
bool isNegative;
public:
BigInteger(string str = "0") {
if (str[0] == '-') {
isNegative = true;
num = str.substr(1);
} else {
isNegative = false;
num = str;
}
}

friend BigInteger operator+(const BigInteger& left, const BigInteger& right) {
string leftNum = left.num;
string rightNum = right.num;
int leftLen = leftNum.length();
int rightLen = rightNum.length();
int carry = 0;
string result = "";

// 对齐两个数,补齐前导零
while (leftNum.length() < rightNum.length()) {
leftNum = "0" + leftNum;
}
while (rightNum.length() < leftNum.length()) {
rightNum = "0" + rightNum;
}

// 从低位向高位逐位相加,注意进位
for (int i = leftLen - 1; i >= 0; i--) {
int sum = (leftNum[i] - '0') + (rightNum[i] - '0') + carry;
result = to_string(sum % 10) + result;
carry = sum / 10;
}
if (carry > 0) {
result = to_string(carry) + result;
}

BigInteger resultInt(result);
// 判断正负号
if (left.isNegative && right.isNegative) {
resultInt.isNegative = true;
} else if (left.isNegative) {
// 左数负号,相当于右数减去左数的相反数
resultInt.isNegative = right < left;
} else if (right.isNegative) {
resultInt.isNegative = left < right;
}
return resultInt;
}

friend bool operator<(const BigInteger& left, const BigInteger& right) {
if (left.isNegative && !right.isNegative) {
return true;
} else if (!left.isNegative && right.isNegative) {
return false;
} else if (left.num.length() != right.num.length()) {
return (left.isNegative && right.isNegative) ? left.num.length() > right.num.length() : left.num.length() < right.num.length();
} else {
if (left.isNegative && right.isNegative) {
for (int i = 0; i < left.num.length(); i++) {
if (left.num[i] != right.num[i]) {
return left.num[i] > right.num[i];
}
}
return false;
} else {
for (int i = 0; i < left.num.length(); i++) {
if (left.num[i] != right.num[i]) {
return left.num[i] < right.num[i];
}
}
return false;
}
}
}

void print() const {
if (isNegative) {
cout << "-";
}
cout << num << endl;
}
};

int main() {
BigInteger a("123456789123456789");
BigInteger b("-987654321987654321");
BigInteger c("9999999999999999999");
BigInteger d("-9999999999999999999");

BigInteger sum1 = a + b; // -864197532864197532
sum1.print();
BigInteger sum2 = a + c; // 10123456789012345678
sum2.print();
BigInteger sum3 = b + d; // -19753086419753086430
sum3.print();

cout << (a < b) << endl; // false
cout << (a < c) << endl; // true
cout << (b < d) << endl; // false

return 0;
}
```

此外,还可以实现更多高精度运算,例如减法、乘法、除法等。