C++ の大整数
このチュートリアルでは、C++ での大きな整数の処理について説明します。 最初に、プリミティブ整数型と C++ でのその範囲について説明し、次にプリミティブ整数型の制限よりも大きい整数を処理する方法について説明します。
C++ の整数データ型
次の表に、C++ のプリミティブ データ型の一覧を示します。 最初の列にはデータ型があり、2 番目の列にはバイト単位のサイズがあり、最後の列には各データ型に格納できる整数の最大範囲があります。
| データ・タイプ | サイズ (バイト単位) | 範囲 |
|---|---|---|
短い整数 |
2 | -32,768 ～ +32,767 |
unsigned short int |
2 | 0 ～ +65,535 |
int |
4 | -2,147,483,648 ～ +2,147,483,647 |
unsigned int |
4 | 0 ～ 4,294,967,295 |
長い整数 |
4 | -2,147,483,648 ～ +2,147,483,647 |
unsigned long int |
4 | 0 ～ 4,294,967,295 |
long long int |
8 | -9,223,372,036,854,775,808 ～ 9,223,372,036,854,775,807 |
unsigned long long int |
8 | 0 ～ 18,446,744,073,709,551,615 |
範囲について混乱がある場合は、特定のタイプの範囲よりも大きい範囲を確認して格納し、同じ変数を出力して結果を確認できます。 ここでは、例を 1つだけ示します。
#include <iostream>
using namespace std;
int main() {
short int x = 35000;
cout << x << '\n';
return 0;
}
出力：
-30536
結果を見て驚くかもしれません。 ただし、2 の補数ストレージの概念を使用して、値 35000 を -30536 まで簡単にトレースできます。
とにかく、最後のデータ型、サイズ 8 バイトの unsigned long long int にジャンプします。
unsigned long long int に格納できる最大数は 18,446,744,073,709,551,615 です。 この数字の桁数は 20 です。
したがって、20 桁を超える数値をプリミティブ データ型に格納することはできませんが、大きな整数と呼ばれるそれよりも大きな整数を処理する必要がある場合があります。
C++ の大整数
C++ では、巨大なサイズの Big Integer を格納できます。 たとえば、500 桁以上の非常に大きな整数を char 配列で処理できます。この場合、各桁は 1つの文字要素として格納されます。
BigInteger クラスの完全な実装の前に、理解を深めるために、クラスのデータ メンバーから始めて、より小さな構成要素について説明しましょう。
char *digit;
int length;
Big Integer の桁数を格納するデータ メンバ 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 関数は、Big Integer の桁数を計算します。
長さに従って、動的配列は数字を格納するために宣言されます。
最後に、数字を逆順に格納するため、下位の数字は下位のインデックスに配置する必要があります。 このストレージ パターンは、算術演算をより便利にするために意図的に設計されています。
次に、ストリーム挿入演算子を見てください。
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;
}
整数を出力するには、通常は左から右に数字を表すように、左から右に上位から下位への数字を出力します。 最後に、オーバーロードされたプラス + 演算子を使用した 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;
}
プラス演算子について簡単に説明しましょう。 大整数の 2つのオペランドには 2つの可能性があります。
両方のオペランドは、同じサイズまたは異なるサイズにすることができます。
異なるサイズの可能性を想定して、両方をカバーしています。 したがって、大きなオペランドのサイズよりも大きな長さの大きな整数を取得して、carry を格納します (必要な場合とそうでない場合があります)。
より小さいサイズの整数のループを実行しています。 その後、数字 3 の ASCII コードは 51 であり、数字 0 の ASCII コードは 48 であるため、各要素から '0' 文字を減算することにより、両方のオペランドから文字を抽出します。
したがって、51 から 48 を引くと、加算演算に必要な 3 が得られます。
次に、足し算式で変数carryが使われていることに注意してください。 最初は、キャリーバリューは 0 です。 ただし、2 桁を加算すると、結果が 9 を超えてキャリーが発生する場合があります。
最初のループでは、両方のオペランドの数字を処理し、次の加算演算で使用される変数 carry にキャリーを格納しています。
最初のループの後、2つのオペランドのどちらが大きいかを決定する必要があります。 この選択の後、残りの大きい整数の数字を結果に格納します。
ただし、式全体で carry を使用しています。
その理由は、残りの桁に 9999...9 があり、前の演算からのキャリー 1 がある場合、結果のすべての桁が 0 になり、最後に、 答えに1を加えてください。
最後に、main 関数は、40 桁以上の 2つの大きな整数の例を示しています。 両方の大きな整数を出力し、後でそれらを追加して結果を出力します。
出力：
67234321234321234321234321234321234321234321234
4321234321234321234321234321234321234321234321
71555555555555555555555555555555555555555555555
出力では、両方の大きな整数を正常に出力しています。 また、正常に追加を実行しました。
結果を簡単に確認できるように、2つの整数を使用しました。 最後に、減算演算子も指定しました。
// 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;
}
減算演算子については説明しません。 ただし、中心的な仮定の 1つは、2 番目のオペランドは常に最初のオペランド以上であるということです。
最後の 1つの問題は、スペースの複雑さです。 現在、私たちの実装では、いくつかの N 桁を格納するために N バイトが必要です (各桁に文字スペースが必要なため)。
ただし、1 文字に 1 桁を格納する代わりに、1 文字に 2 桁を格納することで、このスペースを減らすことができます。 これにより、スペースのほぼ半分を節約できます。
このアイデアの実装を見てみましょう。
#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++ で Big Integer を処理するというアイデアが得られたことを願っています。これで、この実装で plus 演算子を実装できるようになりました。