Ich versuche, eine BigInteger-Klasse in C++ zu implementieren. Aber zuerst habe ich eine Grundfrage, wie die "Basisdaten" dargestellt werden können? Zum Beispiel ist der dümmste Weg, ein festes (oder dynamisches) Array von Zeichen zu haben und jede einzelne Zahl einer Ganzzahl in einem Zeichen zu speichern. Aber, ok, das ist eine sehr dumme Art und ich bin hier für deine Vorschläge.C++ Big Integer
Es gibt eine Reihe von Vorschlägen hier für bestehende Implementierungen: C++ handling very large integers
Wenn Sie Ihren eigenen (zB für Hausaufgaben) haben zu implementieren, dann müssen Sie den besten Weg entscheiden, und wie „groß“ Sie müssen Griff. Sie könnten ein Array von DWORDs verwenden und von einem zum nächsten überlaufen.
Obwohl für einige der Projekt Euler Zeug, ich tatsächlich implementiert eine BigNumber-Klasse auf einer Zeichenfolge aufgebaut. Es stellte sich heraus, dass es am einfachsten für + - */zu implementieren war und auf wesentlich längere Zahlen skaliert wurde als mit einigen wenigen unsigned long long s. Und die Performance war vollkommen ausreichend, um diese Rätsel zu lösen.
Sie stehen also vor einem Kompromiss zwischen einfacher Implementierung und optimaler Leistung. Viel Spaß ;-)
Sie können eine große Ganzzahl genau so erstellen, wie Sie es beschreiben. In der Tat, das erste Mal, dass ich eine solche Klasse implementiert habe, genau so habe ich es gemacht. Es half mir, die arithmetischen Operationen (+, -, usw.) zu implementieren, da es in der Basis (10) war, die ich gewohnt war.
Eine natürliche Verbesserung für Ihre "Array von Zeichen" ist es in der Basis 10 zu halten, aber 4 Bits für die Ziffer anstelle des ganzen Bytes zu verwenden. Somit könnte die Zahl 123,456 durch die Bytes 12 34 56 anstelle der Zeichenkette 123456 dargestellt werden. (Drei Bytes im Gegensatz zu sechs.)
Von dort können Sie den Speicher für die Nummer in der zweiten Basis machen. Die grundlegenden arithmetischen Operationen, wie die Addition, arbeiten in der Basis 2 genauso wie in der Basis 10. Somit könnte die Zahl 65565 unter Verwendung der Bytes FF FF gespeichert werden. (Zum Beispiel in einem Vektor von unsigned char s.) Einige Implementierungen von BigInts verwenden zur Effizienz größere Blöcke, wie short oder long.
Base-10-Big-Ints können nützlich sein, wenn Sie eine Vielzahl von Anzeigen und/oder Serialisierung auf Basis-10 durchführen und die Konvertierung in Base-2 vermeiden möchten.
möglich Duplikat von [Wie Big Int in C++ zu implementieren] (http://StackOverflow.com/Questions/269268/How-to-Implement-Big-int-in-C) – darioo
Wenn Sie die Multi ausführen möchten -precision math yourself, dann schlage ich vor, dass Sie sich Donald Knuths [Kunst der Computerprogrammierung] (https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming) ansehen. Ich glaube, dass Sie an Volume II, Seminumerical Algorithms, Kapitel 4, Multiple Precision Arithmetic, interessiert sind. Siehe auch [Wie fügt man 2 beliebige Integer in C++ hinzu?] (Https://stackoverflow.com/q/2926219/608639), die Code für einige C++ - Bibliotheken und OpenSSL bereitstellt. – jww