Wie erhalte ich die obere Hälfte einer 64-Bit-Ganzzahlmultiplikation in C?

Ermitteln der oberen Hälfte der 64-Bit-Ganzzahlmultiplikation

In C ergibt die Multiplikation zweier 64-Bit-Ganzzahlen (uint64_t) Folgendes: ein Wert, der die unteren 64 Bits des Produkts darstellt, d. h. (i * j) mod (2^64). Um die oberen 64 Bits zu erhalten, können verschiedene Ansätze verwendet werden.

Verwendung von 128-Bit-Zahlen

Wenn Ihr Compiler 128-Bit-Ganzzahlen (__uint128_t) unterstützt, am meisten Ein effizienter Ansatz besteht darin, die Multiplikation mit 128-Bit-Arithmetik durchzuführen und die oberen 64 Bits zu extrahieren.

Portabler Ansatz für 64-Bit-Arithmetik

Für Compiler, die dies nicht unterstützen Bei 128-Bit-Zahlen besteht eine tragbare Lösung darin, jede 64-Bit-Ganzzahl in zwei 32-Bit-Hälften aufzuteilen und diese mithilfe der 64-Bit-Multiplikation zu multiplizieren. Die oberen und unteren Hälften werden dann kombiniert, um das vollständige 128-Bit-Produkt zu berechnen.

Diese Berechnung kann jedoch bei Verwendung der 64-Bit-Arithmetik zu Überläufen führen. Der folgende Code stellt eine Implementierung bereit, die Überläufe bei der Berechnung der oberen 64 Bits behandelt:

uint64_t mulhi(uint64_t a, uint64_t b) {
    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;
    uint64_t    b_x_a_mid = b_hi * a_lo;
    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 >> 32) + (b_x_a_mid >> 32) +
                         carry_bit;

    return multhi;
}

Beachten Sie, dass das Weglassen der Berechnung von Carry_bit zu einem oberen 64-Bit-Wert führen würde, der um 1 abweichen kann.

Das obige ist der detaillierte Inhalt vonWie erhalte ich die obere Hälfte einer 64-Bit-Ganzzahlmultiplikation in C?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!