Wie extrahiere ich den hohen Teil einer 64-Bit-Ganzzahlmultiplikation in C?

Extrahieren des oberen Teils der 64-Bit-Ganzzahlmultiplikation

In C ergibt sich die Multiplikation zweier 64-Bit-Ganzzahlen ohne Vorzeichen (uint64_t). in einem uint64_t, das nur den unteren Teil des Produkts enthält (d. h. (i * j) mod 2^64). Wenn Sie den höheren Teil der Multiplikation erhalten möchten, finden Sie hier einige effiziente Ansätze:

Verwendung von 128-Bit-Zahlen

Wenn Ihr Compiler 128-Bit-Zahlen unterstützt ( (z. B. mit __uint128_t in GCC) können Sie eine 128-Bit-Multiplikation durchführen und die oberen 64 Bits extrahieren. Diese Methode ist wahrscheinlich die effizienteste.

Multiplikationsaufschlüsselung

Wenn Ihr Compiler keine 128-Bit-Zahlen unterstützt, können Sie jede 64-Bit-Ganzzahl in zerlegen folgende Teile:

• a = (a_hi
• b = (b_hi

wo a_hi, a_lo, b_hi und b_lo sind 32-Bit-Ganzzahlen ohne Vorzeichen.

Algorithmus

Um den hohen Teil der Multiplikation (a_hi * b_hi) zu berechnen, können Sie Befolgen Sie diese Schritte:

1. Berechnen Sie die Produkte a_hi b_hi, a_hi b_lo, b_hi a_lo und a_lo b_lo.
2. Fügen Sie die Produkte hinzu a_hi b_hi und die oberen 32 Bits der Summe von a_hi b_lo und b_hi * a_lo.
3. Füge das Ergebnis aus Schritt 2 zu den oberen 32 Bits von a_lo * b_lo hinzu.

注意事项

Beim Ausführen dieser Vorgänge müssen Sie auf einen Ganzzahlüberlauf achten. Der folgende Code veranschaulicht, wie mit einem Überlauf umgegangen wird:

uint64_t a_lo = (uint32_t)a;
uint64_t a_hi = a >> 32;
uint64_t b_lo = (uint32_t)b;
uint64_t b_hi = b >> 32;

uint64_t a_x_b_hi = a_hi * b_hi;
uint64_t a_x_b_mid = (a_hi * b_lo) >> 32;
uint64_t b_x_a_mid = (b_hi * a_lo) >> 32;
uint64_t a_x_b_lo = a_lo * b_lo;

uint64_t carry_bit = ((uint64_t)(uint32_t)a_x_b_mid +
                       (uint64_t)(uint32_t)b_x_a_mid +
                       (a_x_b_lo >> 32)) >> 32;

uint64_t multhi = a_x_b_hi + a_x_b_mid + b_x_a_mid + carry_bit;

return multhi;

Beachten Sie, dass dieser Code möglicherweise nicht ganz genau ist, aber eine gute Annäherung an den höheren Teil der Multiplikation bietet.

Das obige ist der detaillierte Inhalt vonWie extrahiere ich den hohen Teil einer 64-Bit-Ganzzahlmultiplikation in C?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!