迹忆客 专注技术分享

在本文中，我们将讨论在 C++ 中处理大整数。 首先，我们将讨论 C++ 中的原始整数类型及其范围，然后讨论如何处理大于原始整数类型限制的整数。

C++ 中的整数数据类型

下表列出了 C++ 中的基本数据类型。 第一列具有数据类型，第二列具有以字节为单位的大小，最后一列具有每种数据类型中可以存储的最大整数范围。

如果您对范围有一些困惑，您可以检查，将大于范围的内容存储在特定类型中，并通过打印相同的变量来查看结果； 在此，我们仅举一个例子。

#include <iostream>

using namespace std;

int main(){
    short int x = 35000;
    cout << x << '\n';
    return 0;
}

输出:

-30536

您可能会对结果感到惊讶； 但是，您可以使用二进制补码存储概念轻松跟踪值 35000 到 -30536。

无论如何，跳转到最后一个数据类型，大小为 8 字节的 unsigned long long int。

unsigned long long int 可以存储的最大数字是 18,446,744,073,709,551,615。 这个数字的位数是20。

因此，我们不能以原始数据类型存储超过 20 位的数字，而我们可能必须处理大于所谓大整数的整数。

C++ 中的大整数

在C++中，我们可以存储巨大的大整数。 例如，我们可以在 char 数组中处理 500 位甚至更多的非常大的整数，其中每个数字都存储为一个字符元素。

在完整实现 BigInteger 类之前，我们先从类的数据成员开始讨论更小的组成部分，以便更好地理解。

char *digit;
int length;

用于存储大整数位数的数据成员长度。 字符数组digit是存储Big Integer的数字。

接下来，查看构造函数。

BigInteger(const char integer[]){
    length = findLength(integer);
    digit = new char[length];
    for (int i=length-1,j=0;i>=0;i--)
        digit[j++] = integer[i];
}

此构造函数接收 char 数组中的 Big Integer（来自用户或文件的输入）。 findLength 函数计算大整数中的位数。

根据长度，声明一个动态数组来存储数字。

最后，我们以相反的顺序存储数字，因此低位数字应该有较低的索引。 这种存储模式的设计目的是使算术运算更加方便。

接下来，查看流插入运算符。

friend ostream& operator << (ostream &out, const BigInteger &integer){
    for (int i=integer.length-1;i>=0;i--)
        out << integer.digit[i];
    out << '\n';
    return out;
}

为了打印整数，我们从左到右从高位到低位打印数字，就像我们通常从左到右表示数字一样。 最后，查看具有重载的 plus + 运算符的 BigInteger 类的完整实现。

#include <iostream>

using namespace std;

class BigInteger{
        char *digit;
        int length;
        int findLength(const char integer[]){
            int length = 0;
            for (;integer[length]!=0;length++);
            return length;
        }
    public:
        BigInteger(const int SIZE){
            //This constructor is used to store results, and the length will be determined later
            length = 0;
            digit = new char[SIZE];
        }
        BigInteger(const char integer[]){
            length = findLength(integer);
            digit = new char[length];
            //store digits left to right, store higher order digits on higher index
            for (int i=length-1,j=0;i>=0;i--)
                digit[j++] = integer[i];
        }
        BigInteger operator + (const BigInteger &secondInteger){
            //Take i,j for loop, take the carry to store carry of the addition operation
            //At the start, set carry to 0; in the process of addition, we will get carry
            int i, j, result, carry = 0;     //result to store sum of addition of digits
            //Find the length of a longer integer
            int length = this -> length;
            if  (length < secondInteger.length)    length = secondInteger.length;
            //Take variable answer,  set its length greater than the length of longer integer
            //The result may have carry, which makes size greater than existing integers
            BigInteger answer (length + 1);
            for (i = 0 ; i < this->length && i < secondInteger.length ;i++){
                result = this->digit[i] + secondInteger.digit[i] + carry - '0' - '0';
                carry = result / 10;
                answer.digit[i] = result % 10 + '0';
            }
            //Take a pointer and point it to a long integer
            const BigInteger *currentInteger = this;
            if (currentInteger->length < secondInteger.length)
                currentInteger = &secondInteger;
            //Add remaining digits to answer
            for ( ;i<currentInteger->length;i++){
                result = currentInteger->digit[i] + carry - '0';
                carry = result / 10;
                answer.digit[i] = result % 10 + '0';
            }
            //set the length of an answer now
            answer.length=length+1;
            //Check if there is carry or not
            if (carry == 0)    length--;//reduce length because there is no carry
            else    answer.digit[i] = carry + '0';
            return answer;
        }
        friend ostream& operator << (ostream &out, const BigInteger &integer){
            for (int i=integer.length-1;i>=0;i--)
                out << integer.digit[i];
            out << '\n';
            return out;
        }
};
int main(){
    BigInteger integer1("67234321234321234321234321234321234321234321234");
    BigInteger integer2("4321234321234321234321234321234321234321234321");
    cout << integer1 << integer2;
    cout << integer1 + integer2;
    return 0;
}

让我们快速讨论一下加号运算符。 对于两个大整数操作数，我们有两种可能性。

两个操作数可以具有相同的大小或不同的大小。

我们将涵盖它们两者，并假设不同大小的可能性。 因此，我们采用长度大于较大操作数大小的结果大整数来存储进位（可能需要也可能不需要）。

我们正在为较小的整数运行一个循环。 之后，我们通过从每个元素中减去“0”字符来提取两个操作数中的字符，因为数字 3 的 ASCII 代码是 51，数字 0 的 ASCII 代码是 48。

因此，如果我们用 51 减去 48，我们将得到 3，这是加法运算所需要的。

接下来，注意加法表达式中使用了变量进位。 初始账面价值为0； 然而，如果两位数相加，结果可能会超过 9，从而产生进位。

在第一个循环中，我们处理两个操作数的数字并将进位存储在下一个加法运算中使用的变量进位中。

在第一个循环之后，我们必须决定两个操作数中哪一个是大的。 选择后，我们将剩余的较大整数的数字存储在结果中。

然而，我们在整个表达式中都采用进位。

原因是，如果剩下的数字有 9999...9，并且上一次运算有 1 个进位，那么结果的所有数字都会为 0，最后我们会在其中加 1 答案。

最后，主函数显示了两个具有四十多位数字的大整数的示例。 我们打印两个大整数，然后将它们相加并打印结果。

输出：

67234321234321234321234321234321234321234321234
4321234321234321234321234321234321234321234321
71555555555555555555555555555555555555555555555

在输出中，我们已成功打印了两个大整数。 此外，我们已经成功执行了加法。

我们取了两个整数，这样结果就很容易验证。 最后，我们还给出了一个减法运算符。

//Here, we are assuming that we are handling positive integers only
//Therefore, the first integer should be larger or equal to the second integer
BigInteger operator - (const BigInteger &secondInteger){
//First store result in a temporary array and later create answer object         accordingly
    int operand1, operand2;
    int i, j, result, carry = 0; //result to store sum of addition of digits
    //length of the first object will always be greater than equal to second
    char *diff = new char[this->length];
    //Copy elements of the first operand into a temporary array
    for (i = 0 ; i < this->length;i++)
        diff[i] = this->digit[i];
    //Now take a difference of diff array with the second integer
    for (i = 0 ; i < secondInteger.length;i++){
        operand1 = diff[i] - '0';
        operand2 = secondInteger.digit[i] - '0';
        if (operand1 < operand2){
            operand1 += 10;//In subtraction carry is always 10
            for(j = i+1; diff[j] == 0 ; j++);
            //at left larger than 0 digits always exist
            diff[j]--;//Take 1 carry from left non-zero digit
            for (j-- ; j > i ; j--)//shift carry to right
                diff[j] = 9;
            operand1 += 10;//Add 10 to current digit to create effect of carry
        }
        result = operand1 - operand2;
        diff[i] = result + '0';
    }
    //Find the length of array difference by finding the leading zero digits on the left side
    int length = this->length;
    for (;length>=0 && diff[length]!=0;length--);
    BigInteger answer(&diff[length]);
    return answer;
}

我们不讨论减法运算符； 然而，一个中心假设是第二个操作数总是大于或等于第一个操作数。

最后一个问题是空间复杂性。 目前，我们的实现需要 N 个字节来存储多个 N 个数字（因为每个数字都需要一个字符空间）。

但是，我们可以通过在一个字符中存储两位数字而不是在一个字符中存储一位数字来减少这一空间。 这样可以节省几乎一半的空间。

我们来看看这个想法的实现。

#include <iostream>
using namespace std;

class BigInteger {
    char* digit;
    int digitsCount, bytesCount;
    int findLength(const char integer[]) {
        int length = 0;
        for (; integer[length] != 0; length++);
        return length;
    }
public:
    BigInteger(const char integer[]) {
        digitsCount = findLength(integer);
        if (digitsCount % 2 == 0)    bytesCount = digitsCount / 2;
        else                    bytesCount = digitsCount / 2 + 1;
        digit = new char[bytesCount];
        int i = digitsCount - 1, j = 0;
        //Handle n - 1 digit in a loop
        for (; i > 0; i -= 2) {
            //After subtracting 48 or ASCII of 0, the result will be in the right 4 bits only
            digit[j] = (integer[i] - '0');//In first 4 bits store even integer
            digit[j++] += ((integer[i - 1] - '0') << 4);//In last 4 bits store odd integer
        }
        //Handle the last digit separately in case of an odd number of digits only
        if (digitsCount % 2 == 1)    digit[j] = (integer[i] - '0');
    }
    friend ostream& operator << (ostream& out, const BigInteger& integer) {
        int i = integer.bytesCount - 1;
        if (integer.digitsCount % 2 == 1) {
            out << (int)integer.digit[i];
            i--;
        }
        for (; i >= 0; i--)
            out << ((integer.digit[i] & 0xF0) >> 4) << (integer.digit[i] & 0x0F);
        out << '\n';
        return out;
    }
};


int main() {

    BigInteger integer1("67234321234321234321234321234321234321234321234");
    BigInteger integer2("4321234321234321234321234321234321234321234321");
    cout << integer1 << integer2;
    return 0;
}

输出:

67234321234321234321234321234321234321234321234
4321234321234321234321234321234321234321234321

希望您已经了解了在 C++ 中处理大整数的想法，现在您可以在此实现中实现加号运算符。