Wie kann ich 128-Bit-Ganzzahlen in C oder C++ addieren und subtrahieren, wenn mein Compiler sie nicht unterstützt?
https://stackoverflow.com/questions/741301
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich schreibe einen Kompressor für einen langen Strom von 128-Bit-Zahlen.Ich möchte die Zahlen als Unterschiede speichern – und zwar nur den Unterschied zwischen den Zahlen und nicht die Zahlen selbst, weil ich die Unterschiede in weniger Bytes packen kann, weil sie kleiner sind.
Allerdings muss ich zur Komprimierung diese 128-Bit-Werte subtrahieren und zur Dekomprimierung diese Werte addieren.Die maximale Ganzzahlgröße für meinen Compiler beträgt 64 Bit.
Hat jemand eine Idee, wie man das effizient machen kann?
Lösung
Wenn Sie nur Addition und Subtraktion ist, und haben Sie bereits Ihre 128-Bit-Werte in binärer Form, könnte eine Bibliothek nützlich sein, ist aber nicht unbedingt notwendig. Diese Rechnung ist trivial selbst zu tun.
Ich weiß nicht, was Ihr Compiler für 64-Bit-Typen verwendet, also werde ich INT64 und UINT64 für signierte und unsignierte 64-Bit-Integer-Mengen verwendet werden.
class Int128
{
public:
...
Int128 operator+(const Int128 & rhs)
{
Int128 sum;
sum.high = high + rhs.high;
sum.low = low + rhs.low;
// check for overflow of low 64 bits, add carry to high
if (sum.low < low)
++sum.high;
return sum;
}
Int128 operator-(const Int128 & rhs)
{
Int128 difference;
difference.high = high - rhs.high;
difference.low = low - rhs.low;
// check for underflow of low 64 bits, subtract carry to high
if (difference.low > low)
--difference.high;
return difference;
}
private:
INT64 high;
UINT64 low;
};
Andere Tipps
Hier finden Sie aktuelle GMP .
#include <stdio.h>
#include <gmp.h>
int main (int argc, char** argv) {
mpz_t x, y, z;
char *xs, *ys, *zs;
int i;
int base[4] = {2, 8, 10, 16};
/* setting the value of x in base 10 */
mpz_init_set_str(x, "100000000000000000000000000000000", 10);
/* setting the value of y in base 16 */
mpz_init_set_str(y, "FF", 16);
/* just initalizing the result variable */
mpz_init(z);
mpz_sub(z, x, y);
for (i = 0; i < 4; i++) {
xs = mpz_get_str(NULL, base[i], x);
ys = mpz_get_str(NULL, base[i], y);
zs = mpz_get_str(NULL, base[i], z);
/* print all three in base 10 */
printf("x = %s\ny = %s\nz = %s\n\n", xs, ys, zs);
free(xs);
free(ys);
free(zs);
}
return 0;
}
Die Ausgabe ist
x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000
y = 11111111
z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001
x = 235613266501267026547370040000000000
y = 377
z = 235613266501267026547370037777777401
x = 100000000000000000000000000000000
y = 255
z = 99999999999999999999999999999745
x = 4ee2d6d415b85acef8100000000
y = ff
z = 4ee2d6d415b85acef80ffffff01
Nachdem über diese relativ alte Post ganz durch Zufall stolperte, dachte ich es passend auf Volte der vorherige Vermutung zugunsten von unerfahrenen Lesern zu erarbeiten.
Erstens der signierte Bereich einer 128-Bit-Zahl ist -2 127 2 127 -1 und -2 nicht 127 , um 2 127 als ursprünglich festgelegt.
Zum anderen wird durch die zyklische Natur der endlichen arithmetischen der größte erforderliche Differenz zwischen zwei 128-Bit-Zahlen ist, -2 127 2 127 -1, welche eine Speicher Voraussetzung von 128 Bits, 129. Obwohl nicht (2 127 -1) - (-2 127 ) = 2 128 -1 welcher deutlich größer als maximal 2 127 -1 positive ganz Zahl ist, arithmetischer Überlauf sorgt dafür, dass immer der nächste Abstand zwischen zwei beliebigen n -Bit Zahlen fallen immer im Bereich 0 bis 2 n -1 und damit implizit -2 n -1 2 n -1 -1.
Um zu klären, wollen wir zuerst prüfen, wie eine hypothetische 3-Bit-Prozessor Binäraddition implementieren würde. Als Beispiel betrachtet man die folgende Tabelle, die den absoluten unsigned Bereich einer 3-Bit-Ganzzahl abbildet.
0 = 000b
1 = 001b
2 = 010b
3 = 011b
4 = 100b
5 = 101b
6 = 110b
7 = 111b ---> [Zyklen zurück zur 000b bei Überlauf]
Aus der obigen Tabelle ist es leicht ersichtlich, dass:
001b (1) + 010b (2) = 011b (3)
Es ist auch offensichtlich, dass mit seiner numerischen Ergänzung jeden dieser Zahlen addieren immer ergibt 2 n -1:
010b (2) + 101b ([Komplement von 2] = 5) = 111 b (7) = (2 3 -1)
Aufgrund der zyklischen Überlauf, der auftritt, wenn die Addition von zwei n -Bit Zahlen ergibt sich ein ( n +1) -Bit-Ergebnis Daraus folgt, daß die Zugabe jeder dieser Zahlen mit dem numerischen Komplement + 1 wird ergeben immer 0:
010b (2) + 110b ([Komplement von 2] + 1) = 000B (0)
Wir können also sagen, dass [Komplement von n ] + 1 = - n , so dass n + [Komplement von n ] + 1 = n + (- n ) = 0, Ferner, wenn wir wissen jetzt, dass n + [Komplement von n ] + 1 = 0, dann n + [Komplement von n - x ] + 1 muss = n - ( n - x ). = x
Angewandt auf unsere ursprünglichen 3-Bit-Tabelle ergibt:
0 = 000b = [Komplement von 0] + 1 = 0
1 = 001b = [Komplement von 7] + 1 = -7
2 = 010b = [Komplement von 6] + 1 = -6
3 = 011b = [Komplement 5] + 1 = -5
4 = 100b = [Komplement von 4] + 1 = -4
5 = 101b = [Komplement von 3] + 1 = -3
6 = 110b = [Komplement von 2] + 1 = -2
7 = 111 b = [Komplement von 1] + 1 = -1 ---> [Zyklen zurück zur 000b bei Überlauf]
Ob die gegenständliche Abstraktion ist positiv, negativ oder eine Kombination aus beide als implizierte mit unterzeichneten Zweier-Komplement-Arithmetik haben wir nun 2 n n -Bit-Muster, die sich nahtlos dienen können sowohl positive als 0 bis 2 n -1 und negative 0 bis - (2 n ) - 1 reicht und bei Bedarf. In der Tat beschäftigen alle modernen Prozessoren nur ein solches System, um sowohl gemeinsame ALU-Schaltung für die Addition und Subtraktion Operationen zu implementieren. Wenn eine CPU einer i1 - i2 Subtraktionsbefehl trifft, führt er einen intern [ergänzen + 1] Betrieb auf i2 und verarbeitet anschließend die Operanden durch die Zugabe Schaltung, um i1 + [Komplement i2] + 1. Mit Ausnahme eines zusätzlichen zu berechnen tragen / sign XOR-gated Überlauf-flag, die beide mit und ohne Vorzeichen Addition und Subtraktion implizit, jeweils implizit.
Wenn wir die obige Tabelle in die Eingangssequenz anwenden [-2 n -1 2 n -1 -1, -2 n -1 ] wie in Volte ursprüngliche Antwort präsentiert, sind wir nun in der Lage, die Zusammenarbeitmpute folgende n-Bit-Differentiale:
diff # 1:
(2 n -1 -1) - (-2 n -1 ) =
3 - (-4) = 3 + 4 =
(-1) = 7 = 111 b
diff # 2:
(-2 n -1 ) - (2 n -1 -1) =
(-4) - 3 = (-4) + (5) =
(-7) = 1 = 001b
Beginnend mit unseren Samen -2 n -1 , sind wir nun in der Lage, die ursprüngliche Eingangssequenz zu reproduzieren, indem jeden der obigen Differentiale sequentiell Anwendung:
(-2 n -1 ) + (diff # 1) =
(-4) + 7 = 3 =
2 n -1 -1
(2 n -1 -1) + (diff # 2) =
3 + (-7) = (-4) =
-2 n -1
Sie können möchten natürlich einen philosophischen Ansatz für dieses Problem und Vermutungen anzunehmen, warum 2 n zyklisch aufeinanderfolgende Zahlen würden mehr als 2 erfordern n zyklisch sequenzielle Differentiale?
Taliadon.
Boost 1.53 beinhaltet jetzt Multipräzision:
#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
// Requires Boost 1.53 or higher
// build: g++ text.cpp
int main()
{
namespace mp = boost::multiprecision;
mp::uint128_t a = 4294967296;
mp::uint256_t b(0);
mp::uint512_t c(0);
b = a * a;
c = b * b;
std::cout << "c: " << c << "\n";
return 0;
}
Ausgabe:
./a.out
c: 340282366920938463463374607431768211456
Es gibt viel Literatur über große ganze Zahl math. Sie können eine der Bibliotheken frei verfügbar (siehe Links) oder Sie können Ihre eigene Rolle. Obwohl ich sollte Sie warnen, für etwas komplizierter als Addition und Subtraktion (und Verschiebungen), müssen Sie nicht-triviale Algorithmen verwenden.
Um addieren und zu subtrahieren, können Sie eine Klasse / Struktur erstellen, die zwei 64-Bit-Integer hält. Sie können einfache Schule Mathematik verwenden, um die Addition und Subtraktion zu tun. Im Grunde zu tun, was Sie mit einem Bleistift und Papier tun zu addieren oder subtrahieren, mit sorgfältiger Abwägung trägt / leiht.
Suche für große ganze Zahl ist. Btw neueren Versionen von VC ++, IntelC ++ und GCC Compiler haben 128-Bit-Integer-Typen, obwohl ich nicht sicher bin, sind sie so leicht zugänglich wie Sie vielleicht gefallen (sie mit SSE2 / xmms Register verwendet werden sollen).
TomsFastMath ist ein bisschen wie GMP (wie oben erwähnt), aber ist public domain, und war entworfen von Grund auf extrem schnell zu sein (es enthält auch Assembler-Code-Optimierungen für x86, x86-64, ARM, SSE2, PPC32 und AVR32).
Auch erwähnenswert: Wenn das Ziel lediglich ist die Komprimierung eines Stroms von Zahlen zu verbessern, indem sie eine Vorverarbeitung, dann wird der vorverarbeiteten Strom muss nicht genau arithmetische Unterschiede gemacht werden. Sie können XOR verwenden (^) statt + und -. Der Vorteil ist, dass ein 128-Bit-XOR ist genau das gleiche wie zwei unabhängige XORs auf den 64-Bit-Teile, so ist es einfach und effizient.
