Comment extraire la partie supérieure d’une multiplication entière de 64 bits en C ?

Extraire la partie haute de la multiplication d'un entier de 64 bits

En C, multiplier deux entiers de 64 bits ( uint64_t ) donne une valeur représentant les 64 bits inférieurs du produit. Cette opération est couramment utilisée pour réaliser une arithmétique modulaire, où les bits inférieurs contiennent le reste souhaité. Cependant, parfois, nous devons également calculer la partie supérieure de la multiplication. .

Solution optimale

Considérez le scénario suivant :

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

Si vous utilisez un compilateur GCC prenant en charge les nombres 128 bits, la stratégie la plus efficace is Effectuez une multiplication de 128 bits et extrayez les 64 bits supérieurs.

Alternatives sans support 128 bits

S'il n'y a pas de support 128 bits, vous pouvez utiliser la méthode fournie par Yakk. Cette méthode décompose a et b chacun en deux nombres de 32 bits, puis utilise une multiplication sur 64 bits pour calculer respectivement le produit de ces nombres plus petits.

se décompose comme suit :

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;

Désormais, le produit peut être représenté comme :

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

Cependant, calculer la formule ci-dessus en utilisant 64 bits produira un débordement . Nous devons donc effectuer un traitement spécial sur le résultat intermédiaire :

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

Avec une légère modification, si vous ne vous souciez pas du 1 supplémentaire dans la partie d'ordre supérieur, vous pouvez omettre le calcul du porter un peu.

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!