Comment extraire les bits de poids fort d'une multiplication entière de 64 bits en C ?

Récupération des bits de poids fort d'une multiplication entière de 64 bits

En C, multiplication de deux entiers non signés de 64 bits (uint64_t) donne une valeur qui représente les bits de poids faible de la multiplication, donnant effectivement le résultat modulo 2^64. Cela pose la question de savoir comment obtenir les bits de poids fort, souvent nécessaires à certains calculs.

Approches de mise en œuvre

1. 128- Multiplication de bits :

Si votre compilateur prend en charge les nombres de 128 bits (__uint128_t), effectuer une multiplication de 128 bits et extraire les 64 bits supérieurs constitue le moyen le plus efficace d'obtenir les bits de poids fort.

2. Multiplication de 32 bits et accumulation de 64 bits :

Si les nombres 128 bits ne sont pas pris en charge, une solution portable et simple consiste à décomposer chaque nombre de 64 bits en deux nombres de 32 bits, à effectuer une multiplication de 32 bits sur ceux-ci et à accumuler soigneusement les produits partiels de 64 bits, en prenant soin d'éviter les débordements d'entiers.

Instructions d'assemblage :

Pour certaines architectures comme x86, il existe des instructions d'assemblage spécifiques (par exemple, MULH) conçues pour effectuer de telles Multiplication entière de 64 bits. Cependant, l'utilisation de ces instructions en C nécessite des connaissances en programmation assembleur et peut ne pas être aussi portable que les approches C mentionnées précédemment.

Exemple d'implémentation :

Le code C suivant implémente l'approche de multiplication 32 bits et d'accumulation 64 bits :

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;
}

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!