Große ganze Zahl in C++
In diesem Tutorial besprechen wir den Umgang mit großen Ganzzahlen in C++. Zuerst werden wir primitive Integer-Typen und ihren Bereich in C++ diskutieren, dann werden wir diskutieren, wie Integer behandelt werden, die größer als die Grenzen primitiver Integer-Typen sind.
Integer-Datentypen in C++
Die folgende Tabelle enthält die Liste der primitiven Datentypen in C++. Die erste Spalte hat Datentypen, die zweite Spalte hat ihre Größe in Bytes und die letzte Spalte hat den maximalen Bereich von Ganzzahlen, die in jedem Datentyp gespeichert werden können.
| Datentyp | Größe in Byte | Bereich |
|---|---|---|
kurz int |
2 | -32.768 bis +32.767 |
unsigned short int |
2 | 0 bis +65.535 |
int |
4 | -2.147.483.648 bis +2.147.483.647 |
unsigned int |
4 | 0 bis 4.294.967.295 |
lang int |
4 | -2.147.483.648 bis +2.147.483.647 |
unsigned long int |
4 | 0 bis 4.294.967.295 |
lang lang int |
8 | -9.223.372.036.854.775.808 bis 9.223.372.036.854.775.807 |
unsigned long long int |
8 | 0 bis 18.446.744.073.709.551.615 |
Wenn Sie etwas Verwirrung über den Bereich haben, können Sie überprüfen, größer als der Bereich in einem bestimmten Typ speichern und das Ergebnis anzeigen, indem Sie dieselbe Variable drucken. hier geben wir nur ein Beispiel.
#include <iostream>
using namespace std;
int main() {
short int x = 35000;
cout << x << '\n';
return 0;
}
Ausgang:
-30536
Sie werden erstaunt sein, die Ergebnisse zu sehen; Sie können den Wert 35000 jedoch leicht auf -30536 zurückverfolgen, indem Sie das Zweierkomplement-Speicherkonzept verwenden.
Springen Sie trotzdem zum letzten Datentyp, unsigned long long int der Größe 8 Bytes.
Die maximale Anzahl, die wir in unsigned long long int speichern können, ist 18,446,744,073,709,551,615. Die Anzahl der Ziffern in dieser Nummer ist 20.
Daher können wir keine Zahl mit mehr als 20 Ziffern in einem primitiven Datentyp speichern, während wir möglicherweise mit ganzen Zahlen umgehen müssen, die größer sind als die, die als große ganze Zahlen bezeichnet werden.
Große ganze Zahl in C++
In C++ können wir Big Integer von enormer Größe speichern. Beispielsweise können wir eine sehr große Ganzzahl mit 500 Ziffern oder sogar mehr in einem char-Array verarbeiten, in dem jede Ziffer als ein Zeichenelement gespeichert wird.
Lassen Sie uns vor der vollständigen Implementierung der Klasse BigInteger zum besseren Verständnis auf kleinere Bestandteile eingehen, beginnend mit Datenmitgliedern der Klasse.
char *digit;
int length;
Datenelement Länge, um die Anzahl der Stellen in Big Integer zu speichern. Das Zeichenfeld Ziffer dient zum Speichern von Ziffern von Big Integer.
Sehen Sie sich als Nächstes den Konstruktor an.
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];
}
Dieser Konstruktor erhält eine Big Integer im Array char (Eingabe vom Benutzer oder der Datei). Die Funktion findLength berechnet die Anzahl der Stellen in Big Integer.
Je nach Länge wird ein dynamisches Array zum Speichern von Ziffern deklariert.
Schließlich speichern wir Ziffern in umgekehrter Reihenfolge, sodass Ziffern niedrigerer Ordnung einen niedrigeren Index haben sollten. Dieses Speichermuster wurde gezielt entwickelt, um arithmetische Operationen handlicher zu machen.
Sehen Sie sich als Nächstes den Stream-Einfügungsoperator an.
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;
}
Um Ganzzahlen zu drucken, drucken wir Ziffern von höherer Ordnung zu niedrigerer Ordnung von links nach rechts, da wir normalerweise Zahlen von links nach rechts darstellen. Sehen Sie sich abschließend die vollständige Implementierung der Klasse BigInteger mit dem überladenen Plusoperator + an.
#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;
}
Lassen Sie uns schnell den Plus-Operator besprechen. Wir haben zwei Möglichkeiten für zwei Operanden einer großen Ganzzahl.
Beide Operanden können gleich groß oder unterschiedlich groß sein.
Wir decken beide ab und gehen von der Möglichkeit unterschiedlicher Größen aus. Daher haben wir die resultierende große Ganzzahl mit einer Länge größer als die Größe des größeren Operanden genommen, um Übertrag zu speichern (kann erforderlich sein oder nicht).
Wir führen eine Schleife für kleinere Ganzzahlen aus. Danach extrahieren wir Zeichen aus beiden Operanden, indem wir das Zeichen 0 von jedem Element subtrahieren, da der ASCII-Code der Ziffer 3 51 und der ASCII-Code der Ziffer 0 48 ist.
Wenn wir also 48 von 51 subtrahieren, erhalten wir 3, was für die Additionsoperation erforderlich ist.
Als nächstes wird die Notizvariable carry als zusätzlicher Ausdruck verwendet. Der Buchwert beträgt zu Beginn 0; Durch das Hinzufügen von zwei Ziffern kann das Ergebnis jedoch 9 überschreiten, was zu einem Übertrag führt.
In der ersten Schleife behandeln wir die Ziffern beider Operanden und speichern den Übertrag in einer Variablen Übertrag, die in der nächsten Additionsoperation verwendet wird.
Nach der ersten Schleife müssen wir entscheiden, welcher der beiden Operanden der große ist. Nach dieser Auswahl speichern wir Ziffern der verbleibenden größeren Ganzzahl im Ergebnis.
Wir nehmen jedoch im gesamten Ausdruck Übertrag.
Der Grund dafür ist, dass, wenn wir 9999...9 in den verbleibenden Ziffern haben und wir 1 von der vorherigen Operation übertragen haben, alle Ziffern des Ergebnisses 0 werden, und am Ende werden wir es tun haben einen Zusatz von 1 in der Antwort.
Schließlich zeigt die Hauptfunktion ein Beispiel für zwei große ganze Zahlen mit mehr als vierzig Stellen. Wir drucken beide großen Ganzzahlen, und später addieren wir sie und drucken das Ergebnis.
Ausgang:
67234321234321234321234321234321234321234321234
4321234321234321234321234321234321234321234321
71555555555555555555555555555555555555555555555
In der Ausgabe haben wir beide großen Ganzzahlen erfolgreich gedruckt. Außerdem haben wir die Addition erfolgreich durchgeführt.
Wir haben zwei ganze Zahlen genommen, damit das Ergebnis leicht verifiziert werden kann. Schließlich haben wir auch einen Subtraktionsoperator angegeben.
// 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;
}
Wir gehen nicht auf die Diskussion des Subtraktionsoperators ein; Eine zentrale Annahme ist jedoch, dass der zweite Operand immer größer oder gleich dem ersten Operanden ist.
Ein letztes Problem ist die räumliche Komplexität. Derzeit benötigt unsere Implementierung N Bytes, um mehrere N-Ziffern zu speichern (da für jede Ziffer ein Zeichenraum erforderlich ist).
Wir können diesen Platz jedoch verringern, indem wir zwei Ziffern in einem Zeichen speichern, anstatt eine Ziffer in einem Zeichen zu speichern. Dadurch kann fast die Hälfte des Platzes eingespart werden.
Schauen wir uns die Umsetzung dieser Idee an.
#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;
}
Ausgang:
67234321234321234321234321234321234321234321234
4321234321234321234321234321234321234321234321
Ich hoffe, Sie haben die Idee, Big Integer in C++ zu handhaben, und jetzt können Sie den Plus-Operator in dieser Implementierung implementieren.