Wie kann man den hohen Teil einer 64-Bit-Ganzzahlmultiplikation in C erhalten?

Ermitteln des oberen Teils der 64-Bit-Ganzzahlmultiplikation

Wenn i und j in C 64-Bit-Ganzzahlen ohne Vorzeichen sind, i * j ergibt die unteren 64 Bits ihres Produkts, d. h. (i * j) mod 2^64. Um den höheren Teil des Produkts zu erhalten, ziehen Sie die folgenden Ansätze in Betracht:

Verwendung der 128-Bit-Multiplikation:

Wenn der Compiler 128-Bit-Ganzzahlen unterstützt (z. B. __uint128_t ), die Durchführung einer 128-Bit-Multiplikation und das Extrahieren der oberen 64 Bits ist die effizienteste Methode.

YAKs Ansatz (unter Verwendung der 32-Bit-Multiplikation):

Dies beinhaltet Zerlegen Sie jede 64-Bit-Ganzzahl in zwei 32-Bit-Hälften, multiplizieren Sie sie mit der 64-Bit-Multiplikationsoperation und kombinieren Sie die Ergebnisse:

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 multhi = a_hi * b_hi + (a_hi * b_lo >> 32) + (b_hi * a_lo >> 32) + a_lo * b_lo;

Überlaufbehandlung:

Die obige Berechnung führt jedoch eine 128-Bit-Arithmetik durch, was zu einem Überlauf führen kann. Um dies bei der Beschränkung auf 64-Bit-Arithmetik zu handhaben, passt die folgende Implementierung den Überlauf an:

uint64_t a_x_b_hi = a_hi * b_hi;
uint64_t a_x_b_mid = a_hi * b_lo;
uint64_t b_x_a_mid = b_hi * a_lo;
uint64_t a_x_b_lo = a_lo * b_lo;

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

uint64_t multhi = a_x_b_hi + (a_x_b_mid >> 32) + (b_x_a_mid >> 32) + carry_bit;

Hinweis: Wenn ein Fehler von 1 Bit in den oberen 64 Bits akzeptabel ist, wird der Die Berechnung des Übertragsbits kann entfallen.

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