Comment extraire la partie haute d'une multiplication entière de 64 bits en C ?

Extraction de la partie haute de la multiplication d'entiers 64 bits

En C, la multiplication de deux entiers non signés de 64 bits (uint64_t) résulte dans un uint64_t qui contient uniquement la partie inférieure du produit (c'est-à-dire (i * j) module 2 ^ 64). Si vous cherchez à obtenir la partie supérieure de la multiplication, voici quelques approches efficaces :

Utiliser des nombres 128 bits

Si votre compilateur prend en charge les nombres 128 bits ( par exemple, en utilisant __uint128_t dans GCC), vous pouvez effectuer une multiplication sur 128 bits et extraire les 64 bits supérieurs. Cette méthode est probablement la plus efficace.

Répartition des multiplications

Si votre compilateur ne prend pas en charge les nombres de 128 bits, vous pouvez décomposer chaque entier de 64 bits en parties suivantes :

• a = (a_hi
• b = (b_hi

où a_hi, a_lo, b_hi et b_lo sont des entiers non signés de 32 bits.

Algorithme

Pour calculer la partie haute de la multiplication (a_hi * b_hi), vous pouvez suivre ces étapes :

1. Calculez les produits a_hi b_hi, a_hi b_lo, b_hi a_lo, et a_lo b_lo.
2. Ajouter les produits a_hi b_hi et les 32 bits supérieurs de la somme de a_hi b_lo et b_hi * a_lo.
3. Ajoutez le résultat de l'étape 2 aux 32 bits supérieurs de a_lo * b_lo.

注意事项

Lorsque vous effectuez ces opérations, vous devez faire attention au débordement d'entier. Le code suivant illustre comment gérer le débordement :

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;

Notez que ce code n'est peut-être pas parfaitement précis, mais il fournit une bonne approximation de la partie supérieure de la multiplication.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!