Eine lustige Herausforderung.:)
Ich nehme an, dass Sie ganze Zahlen beliebiger Länge wollen. Ich schlage folgenden Ansatz vor:
Betrachten Sie die binäre Natur des Datentyps "int". Denken Sie daran, einfache binäre Operationen zu verwenden, um zu emulieren, was die Schaltungen in Ihrer CPU tun, wenn sie Dinge hinzufügen. Wenn Sie sich intensiver dafür interessieren, lesen Sie bitte this wikipedia article on half-adders and full-adders. Sie werden etwas Ähnliches tun, aber Sie können so niedrig wie das gehen - aber faul zu sein, dachte ich, ich würde einfach verzichten und eine noch einfachere Lösung finden.
Bevor wir jedoch auf algorithmische Details zum Addieren, Subtrahieren, Multiplizieren eingehen, wollen wir eine Datenstruktur finden. Ein einfacher Weg ist natürlich, Dinge in einem std :: vector zu speichern.
template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector<BaseType> value_;
};
Vielleicht möchten Sie prüfen, ob Sie den Vektor mit einer festen Größe machen wollen und wenn es vorzubelegen. Grund dafür ist, dass Sie für verschiedene Operationen jedes Element des Vektors durchlaufen müssen - O (n). Sie möchten vielleicht wissen, wie komplex eine Operation sein wird und ein festes n genau das tut.
Aber jetzt zu einigen Algorithmen auf den Zahlen arbeiten. Sie könnten dies auf einer logischen Ebene tun, aber wir werden diese magische CPU-Leistung verwenden, um Ergebnisse zu berechnen. Aber was wir von der Logik-Illustration von Half- und FullAdders übernehmen werden, ist der Umgang mit Übertragungen. Betrachten Sie als Beispiel, wie Sie den + = Operator implementieren würden. Für jede Zahl in BigInt <> :: value_ würden Sie diese hinzufügen und sehen, ob das Ergebnis irgendeine Art von Übertrag erzeugt. Wir werden es nicht bitweise tun, sondern uns auf die Art unseres BaseType verlassen (sei es long oder int oder short oder was auch immer): es läuft über.
Sicher, wenn Sie zwei Zahlen hinzufügen, muss das Ergebnis größer sein als die größere dieser Zahlen, richtig? Wenn nicht, ist das Ergebnis übergelaufen.
template< class BaseType >
BigInt<BaseType>& BigInt<BaseType>::operator += (BigInt<BaseType> const& operand)
{
BT count, carry = 0;
for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
{
BT op0 = count < value_.size() ? value_.at(count) : 0,
op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
BT digits_result = op0 + op1 + carry;
if (digits_result-carry < std::max(op0, op1)
{
BT carry_old = carry;
carry = digits_result;
digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
}
else carry = 0;
}
return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
// not, then you must restrict BaseType to be the second biggest type
// available, i.e. a 32-bit int when you have a 64-bit long. Then use
// a temporary or a cast to the mightier type and retrieve the upper bits.
// Or you do it bitwise. ;-)
Die anderen arithmetischen Operationen gehen analog. Verdammt, du könntest sogar die stl-functors std :: plus und std :: minus, std :: times und std :: divides, ... benutzen, aber achte auf den Übertrag. :) Sie können Multiplikation und Division auch implementieren, indem Sie Ihre Plus- und Minusoperatoren verwenden, aber das ist sehr langsam, da das die Ergebnisse berechnet, die Sie bereits in früheren Aufrufen bei jeder Iteration zu Plus und Minus berechneten. Es gibt viele gute Algorithmen für diese einfache Aufgabe, usewikipedia oder das Web.
Und natürlich sollten Sie Standard-Operatoren implementieren wie operator<< (nur jeden Wert verschieben in Wert_ nach links für n Bits, am value_.size()-1 gestartet ... ach ja, und erinnere mich an die Übertrags :), operator< - Sie können sogar Hier ein wenig optimieren und die grobe Anzahl der Ziffern zuerst mit size() überprüfen. Und so weiter. Dann machen Sie Ihre Klasse nützlich, indem Sie befriendig std :: ostream operator<<.
Hoffe dieser Ansatz ist hilfreich!
Wenn dies eine Programmieraufgabe ist, starten Sie die Codierung. Sie können sonst keine Übung bekommen! –
Die erste Sache - Ziffernfolgen sind in Ordnung, aber denke in Bezug auf die Basis 2^32 (4 Milliarden ungerade unterschiedliche Ziffern). Vielleicht sogar Base 2^64 in diesen Tagen. Zweitens, arbeiten Sie immer mit vorzeichenlosen Integer "Ziffern". Sie können das Zweierkomplement für signierte Big Integers selbst durchführen, aber wenn Sie versuchen, Ihre Overflow-Behandlung usw. mit vorzeichenbehafteten Ganzzahlen auszuführen, werden Sie auf Standards stoßen - undefinierte Verhaltensprobleme. – Steve314
Für Algorithmen - für eine grundlegende Bibliothek sind diejenigen, die Sie in der Schule gelernt haben, ungefähr richtig. – Steve314