Bit-Manipulation für große Integer-Klassen?

Question

Ich habe ein Problem mit einem Algorithmus für eine große Integer-Klasse in C++. Meine ursprüngliche Idee war Arrays/Listen zu verwenden, aber es ist sehr ineffizient. Ich entdeckte dann Dinge wie die folgende Klasse: http://www.codeproject.com/KB/cpp/CppIntegerClass.aspx

Allerdings finde ich diesen Ansatz wirklich verwirrend. Ich weiß nicht, wie man mit Bitmanipulationen arbeitet, und ich habe den Code kaum verstanden. Jemand erklärt mir bitte, wie man Bitmanipulation benutzt, wie es funktioniert, usw. Schließlich möchte ich meine eigene große Integer-Klasse erstellen, aber ich bin kaum ein Anfänger-Programmierer und ich habe gerade gelernt, wie man Klassen benutzt.

Grundsätzlich meine Frage ist: Wie verwende ich Bit-Manipulation, um eine große Ganzzahl-Klasse zu erstellen? Wie funktioniert es??

Danke!

Answer 1

Beginnen Sie mit Lesen auf binary numbers im Allgemeinen. Diese Seite zeigt, wie die üblichen arithmetischen Operationen (Addition, Subtraktion usw.) an Binärzahlen arbeiten, d. H. Wie die Zahlen bitweise manipuliert werden, um das gewünschte Ergebnis zu erhalten.

Das Mapping in eine Programmiersprache wie C++ sollte ziemlich einfach sein, sobald Sie wissen warum gibt es Bit-Manipulation Operationen verwendet werden.

Nach meiner Erfahrung ist die offensichtlichste Bit-orientierte Sache, die benötigt wird, wenn etwas so implementiert wird, Bit Testen, um auf Überlauf zu prüfen. Nehmen wir an, Sie repräsentieren Ihre große Binärzahl als ein Array von uint16_t, d. H. Chunks von 16 Bits. Wenn Sie die Hinzufügung implementieren, beginnen Sie mit dem am wenigsten signifikanten Ende beider Zahlen und fügen diese hinzu. Wenn die Summe größer als 65.535 ist, müssen Sie einen zum nächsten uint16_t "tragen", genau wie wenn Sie Dezimalzahlen jeweils um eine Ziffer addieren.

Dies kann wie so mit einem Test durchgeführt werden:

const uint16_t *number1; 
const uint16_t *number2; 

/* assume code goes here to set up the number1 and number2 pointers. */ 

/* Compute sum of 16 bits. */ 
uint16_t carry = 0; 
uint32_t sum = number1[0] + number2[0]; 

/* One way of testing for overflow: */ 
if (sum & (1 << 16)) 
carry = 1; 

Hier wird die 1 << 16 Ausdrücke erzeugen eine Maske durch einen 1 sechzehn Schritte nach links zu verschieben. Die & bitweise und Bediener prüft die Summe gegen die Maske; das Ergebnis ist nicht Null (d. h. wahr, in C++), wenn das Bit 16 in sum gesetzt ist.