Wie kann ich 128-Bit-Ganzzahlen in C oder C ++ addieren und subtrahieren, wenn mein Compiler sie nicht unterstützt?

Schreibe ich einen Kompressor für einen langen Strom von 128-bit-zahlen. Ich möchte zum speichern der zahlen als Unterschiede-speichern nur den Unterschied zwischen den zahlen, anstatt der zahlen selbst, da kann ich pack die Unterschiede in den weniger bytes, weil Sie kleiner sind.

Jedoch für die Kompression dann muss ich abziehen, diese 128-bit-Werte, und für die Dekompression, die ich brauche um diese Werte. Maximale integer-Größe für meinen compiler 64 bit breit.

Jemand irgendwelche Ideen für die dies effizient?

InformationsquelleAutor der Frage Billy ONeal | 2009-04-12

128bit c++integer

Wenn alles, was Sie brauchen, ist die addition und die Subtraktion, und schon haben Sie Ihre 128-bit-Werte in binärer form, eine Bibliothek kann nützlich sein, ist aber nicht unbedingt notwendig. Diese Mathematik ist trivial, sich selbst zu tun.

Ich weiß nicht, was dein compiler verwendet für 64-bit-Typen, also werde ich INT64 und UINT64 für signierte und unsignierte 64-bit-integer-Mengen.

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;
};

InformationsquelleAutor der Antwort Mark Ransom

Werfen Sie einen Blick auf 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

InformationsquelleAutor der Antwort Chas. Owens

8

Haben stolperte über dieses relativ alte post ganz durch Zufall, ich dachte, es sinnvoll zu erarbeiten, Volte früheren Vermutung zugunsten der unerfahrene Leser.

Erstens, die unterzeichneten Reichweite einer 128-bit-Zahl -2¹²⁷ 2¹²⁷-1 und nicht -2¹²⁷ 2¹²⁷ als ursprünglich vorgesehen.

Zweitens, aufgrund der zyklischen Natur der endlichen Arithmetik die größte erforderliche Differenzdruck zwischen zwei 128-bit-zahlen ist -2¹²⁷ 2¹²⁷-1, die eine Lagerung Voraussetzung für 128-bits, nicht 129. Obwohl (2¹²⁷-1) - (-2¹²⁷) = 2¹²⁸-1, was deutlich größer ist, als unser maximum 2¹²⁷-1 positive ganze Zahl ist, arithmetischer überlauf sorgt stets dafür, dass der nächste Abstand zwischen zwei n-bit-zahlen fällt immer im Bereich 0, 2ⁿ-1 und damit implizit -2^n-1 2^n-1-1.

Um zu klären, lassen Sie uns zunächst untersuchen, wie sich eine hypothetische 3-bit-Prozessor realisieren binären neben. Als Beispiel betrachten wir die folgende Tabelle zeigt die absolute unsigned range eines 3-bit-integer.

   0 = 000b

   1 = 001b

   2 = 010b

   3 = 011b

   4 = 100b

   5 = 101b

   6 = 110b

   7 = 111b ---> [- Zyklen zurück zu 000b auf overflow]

Aus der obigen Tabelle ist es offensichtlich, dass:

   001b(1) + 010b(2) = 011b(3)

Es ist auch offensichtlich, dass das hinzufügen von einigen dieser zahlen mit den numerischen Ergänzung bringt immer 2ⁿ-1:

   010b(2) + 101b([Ergänzung 2] = 5) = 111b(7) = (2³-1)

Aufgrund der zyklischen overflow, der Auftritt, wenn die beiden n-bit-Zahl ergibt eine (n+1)-bit-Ergebnis, es folgt also, dass das hinzufügen von einigen dieser zahlen mit den numerischen ergänzen + 1 wird immer Ertrag 0:

   010b(2) + 110b([Ergänzung 2] + 1) = 000b(0)

So können wir sagen, dass [Ergänzung von n] + 1 = -nso dass n + [Ergänzung von n] + 1 = n + (-n) = 0. Außerdem, wenn wir jetzt wissen, dass n + [Ergänzung von n] + 1 = 0, dann ist n + [Ergänzung von n - x] + 1 = n - (n-x) = x.

Anwendung dieser unserer ursprünglichen 3-bit-Tabelle ergibt:

   0 = 000b = [Ergänzung 0] + 1 = 0

   1 = 001b = [Ergänzung 7] + 1 = -7

   2 = 010b = [Ergänzung 6] + 1 = -6

   3 = 011b = [Ergänzung 5] + 1 = -5

   4 = 100b = [Ergänzung 4] + 1 = -4

   5 = 101b = [Ergänzung 3] + 1 = -3

   6 = 110b = [Ergänzung 2] + 1 = -2

   7 = 111b = [Ergänzung von 1] + 1 = -1 ---> [Zyklen zurück zu 000b auf overflow]

Ob das gegenständliche Abstraktion, die positiv, negativ oder eine Kombination von beiden, wie angedeutet, mit unterzeichnet zweier-Komplement-Arithmetik, wir haben nun 2ⁿ n-bit-Muster, die nahtlos dienen sowohl positive, 0, 2ⁿ-1, und negativ 0 bis -(2ⁿ)-1 reicht, wie und Wann erforderlich. In Punkt der Tatsache, dass alle modernen Prozessoren beschäftigen genau so ein system um die Durchführung der gemeinsamen ALU-Schaltung für beide addition und Subtraktion Operationen. Wenn eine CPU auf einen i1 - i2 Subtraktion Anweisung, es führt intern eine [Ergänzung + 1] - Betrieb auf i2 und anschließend verarbeitet die Operanden durch die addition Schaltung zur Berechnung i1 + [Ergänzung von i2] + 1. Mit der Ausnahme einer zusätzlichen carry/Zeichen XOR-gesteuerter überlauf-flag, sowohl signierte als auch unsignierte hinaus, und durch Implikation, Subtraktion, werden jeweils implizit.

Wenn wir die obige Tabelle der input-Sequenz [-2^n-12^n-1-1, -2^n-1], wie Sie in Volte ursprünglichen Antwort, wir sind jetzt in der Lage zu berechnen, die folgende n-bit-Differentiale:

diff #1:

   (2^n-1-1) - (-2^n-1) =

   3 - (-4) = 3 + 4 =

   (-1) = 7 = 111b

diff #2:

   (-2^n-1) - (2^n-1-1) =

   (-4) - 3 = (-4) + (5) =

   (-7) = 1 = 001b

Beginnend mit unserem Saatgut -2^n-1wir sind jetzt in der Lage zu reproduzieren die ursprüngliche Eingabe-Sequenz durch die Anwendung jeder der obigen differentialquotienten der Reihe nach:

   (-2^n-1) + (diff #1) =

   (-4) + 7 = 3 =

   2^n-1-1

   (2^n-1-1) + (diff #2) =

   3 + (-7) = (-4) =

   -2^n-1

Natürlich können Sie einführen wollen mehr philosophischen Ansatz für dieses problem und Vermutungen, warum die 2ⁿ zyklisch-sequentielle zahlen würde erfordern mehr als 2ⁿ zyklisch-sequenzielle Unterschiede?

Taliadon.

InformationsquelleAutor der Antwort Taliadon

Boost 1.53 enthält jetzt multiprecision:

#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

InformationsquelleAutor der Antwort

3

Gibt es eine Menge Literatur zu großen integer-math. Sie können verwenden Sie eine der Bibliotheken, die frei verfügbar (siehe links), oder Sie können Rollen Sie Ihre eigenen. Obwohl ich sollte Sie warnen, für alles, was komplizierter als die addition und die Subtraktion (und Schichten), müssen Sie die Verwendung von nicht-trivialen algorithmen.

Hinzufügen und subtrahieren, können Sie erstellen Sie eine Klasse/Struktur mit zwei 64-bit-Ganzzahlen. Sie können einfache Schulmathematik zu tun, die die addition und die Subtraktion. Im Grunde genommen tun, was Sie tun, mit einem Bleistift und Papier zu addieren oder zu subtrahieren, mit bedacht zu trägt/leiht.

Suche nach großen integer. Btw neueren Versionen von VC++, IntelC++ und GCC-Compiler 128-bit-integer-Typen, obwohl ich nicht sicher bin, Sie sind so leicht zugänglich, wie Sie mögen (Sie sollen verwendet werden, mit sse2/xmms-Register).
InformationsquelleAutor der Antwort Ash
2

TomsFastMath ist ein bisschen wie GMP (oben erwähnt), aber ist public domain und wurde entworfen vom Boden bis zu extrem schnell (es enthält sogar Assembler-code-Optimierungen für die x86, x86-64, ARM, SSE2, PPC32, und AVR32).

InformationsquelleAutor der Antwort Sophie Alpert
0

Ebenfalls erwähnenswert: wenn das Ziel lediglich die Verbesserung der Kompression von einem Strom von zahlen, die von der Vorverarbeitung ist es, dann den verarbeiteten stream muss nicht aus genau arithmetischen Unterschiede. Sie können verwenden Sie XOR (^) statt + und -. Der Vorteil ist, dass eine 128-bit-XOR ist genau das gleiche wie zwei unabhängige XORs auf die 64-bit-Teile, so ist es sowohl einfach als auch effizient.

InformationsquelleAutor der Antwort Armin Rigo

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.