Wie extrahiere ich den höheren Teil der 64-Bit-Ganzzahlmultiplikation in C?

Extrahieren des oberen Teils der 64-Bit-Ganzzahlmultiplikation

In C das Multiplizieren zweier 64-Bit-Ganzzahlen ( uint64_t ) ergibt einen Wert, der die unteren 64 Bits des Produkts darstellt Die Operation wird üblicherweise verwendet, um modulare Arithmetik zu erreichen, bei der die unteren Bits den gewünschten Rest enthalten. Manchmal müssen wir jedoch auch den höheren Bitteil der Multiplikation berechnen.

Optimale Lösung

Stellen Sie sich das folgende Szenario vor:

uint64_t i = // some value
uint64_t j = // some value
uint64_t k = mulhi(i, j); // where mulhi() returns the higher part of the 64-bit multiplication

Bei Verwendung eines GCC-Compilers, der 128-Bit-Zahlen unterstützt, ist dies die effektivste Strategie ist Führen Sie eine 128-Bit-Multiplikation durch und extrahieren Sie die oberen 64 Bits.

Alternativen ohne 128-Bit-Unterstützung

Wenn keine 128-Bit-Unterstützung vorhanden ist, können Sie die von Yakk bereitgestellte Methode verwenden. Diese Methode zerlegt a und b jeweils in zwei 32-Bit-Zahlen und verwendet dann eine 64-Bit-Multiplikation, um jeweils das Produkt dieser kleineren Zahlen zu berechnen.

lässt sich wie folgt aufschlüsseln:

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;

Nun kann das Produkt wie folgt dargestellt werden:

a * b = ((a_hi << 32) + a_lo) * ((b_hi << 32) + b_lo)

      = ((a_hi * b_hi) << 64) +
        ((a_hi * b_lo) << 32) +
        ((b_hi * a_lo) << 32) +
          a_lo * b_lo

Die Berechnung der obigen Formel mit 64 Bit führt jedoch zu einem Überlauf . Daher müssen wir eine spezielle Verarbeitung des Zwischenergebnisses durchführen:

// 为防止溢出而引入的临时变量
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;

Mit geringfügigen Änderungen können Sie die Berechnung von weglassen, wenn Ihnen die zusätzliche 1 im höherwertigen Teil egal ist Tragebit.

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