Comment obtenir la moitié supérieure d'une multiplication entière de 64 bits en C ?

Obtention de la moitié supérieure de la multiplication d'un entier de 64 bits

En C, la multiplication de deux entiers de 64 bits (uint64_t) donne une valeur qui représente les 64 bits inférieurs du produit, c'est-à-dire (i * j) mod (2 ^ 64). Pour obtenir les 64 bits supérieurs, diverses approches peuvent être utilisées.

Utilisation de nombres de 128 bits

Si votre compilateur prend en charge les entiers de 128 bits (__uint128_t), le plus Une approche efficace consiste à effectuer la multiplication en utilisant l'arithmétique 128 bits et à extraire les 64 bits supérieurs. bits.

Approche portable pour l'arithmétique 64 bits

Pour les compilateurs qui ne prennent pas en charge les nombres 128 bits, une solution portable consiste à diviser chaque entier de 64 bits en deux moitiés de 32 bits et multipliez-les en utilisant une multiplication de 64 bits. Les moitiés supérieures et inférieures sont ensuite combinées pour calculer le produit complet de 128 bits.

Cependant, ce calcul peut entraîner des débordements lors de l'utilisation de l'arithmétique 64 bits. Le code ci-dessous fournit une implémentation qui gère les débordements lors du calcul des 64 bits supérieurs :

uint64_t mulhi(uint64_t a, uint64_t b) {
    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;
    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;
}

Notez que l'omission du calcul de carry_bit entraînerait une valeur supérieure de 64 bits qui peut être décalée de 1.

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!