Wie extrahiere ich die höherwertigen Bits einer 64-Bit-Ganzzahlmultiplikation in C?

Abrufen der höherwertigen Bits einer 64-Bit-Ganzzahlmultiplikation

In C das Multiplizieren zweier 64-Bit-Ganzzahlen ohne Vorzeichen (uint64_t) ergibt einen Wert, der die niederwertigen Bits der Multiplikation darstellt, wodurch das Ergebnis effektiv Modulo 2^64 ergibt. Dies wirft die Frage auf, wie man die höherwertigen Bits erhält, die oft für bestimmte Berechnungen notwendig sind.

Implementierungsansätze

1. 128- Bitmultiplikation:

Wenn Ihr Compiler 128-Bit-Zahlen (__uint128_t) unterstützt, bietet die Durchführung einer 128-Bit-Multiplikation und das Extrahieren der oberen 64 Bits die effizienteste Möglichkeit, die höhere Ordnung zu erhalten Bits.

2. 32-Bit-Multiplikation und 64-Bit-Akkumulation:

Wenn 128-Bit-Zahlen nicht unterstützt werden, eine tragbare und einfache Lösung besteht darin, jede 64-Bit-Zahl in zwei 32-Bit-Zahlen zu zerlegen, eine 32-Bit-Multiplikation mit ihnen durchzuführen und die 64-Bit-Partialprodukte sorgfältig zu akkumulieren, wobei darauf zu achten ist, dass Ganzzahlüberläufe vermieden werden.

Montageanweisungen:

Für einige Architekturen wie x86 gibt es spezielle Montageanweisungen (z. B. MULH), die für die Durchführung einer solchen 64-Bit-Ganzzahlmultiplikation entwickelt wurden. Die Verwendung dieser Anweisungen in C erfordert jedoch Kenntnisse in Assemblerprogrammierung und ist möglicherweise nicht so portabel wie die zuvor erwähnten C-Ansätze.

Beispielimplementierung:

Der folgende C-Code implementiert den 32-Bit-Multiplikations- und 64-Bit-Akkumulationsansatz:

uint64_t mulhi(uint64_t a, uint64_t b) {
  uint32_t a_lo = (uint32_t)a;
  uint32_t a_hi = a >> 32;
  uint32_t b_lo = (uint32_t)b;
  uint32_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 + a_lo * b_hi; // Avoid overflow
  uint64_t b_x_a_mid = b_hi * a_lo;
  uint64_t a_x_b_lo = a_lo * b_lo;

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

  return multhi;
}

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