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

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

En C , si i et j sont des entiers non signés de 64 bits, i * j donne les 64 bits inférieurs de leur produit, c'est-à-dire (i * j) mod 2^64. Pour obtenir la partie supérieure du produit, envisagez les approches suivantes :

Utilisation de la multiplication 128 bits :

Si le compilateur prend en charge les entiers 128 bits (par exemple, __uint128_t ), effectuer une multiplication sur 128 bits et extraire les 64 bits supérieurs est la méthode la plus efficace.

Approche de YAK (utilisation de la multiplication sur 32 bits) :

Cela implique diviser chaque entier de 64 bits en deux moitiés de 32 bits, les multiplier à l'aide de l'opération de multiplication de 64 bits et combiner les résultats :

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 multhi = a_hi * b_hi + (a_hi * b_lo >> 32) + (b_hi * a_lo >> 32) + a_lo * b_lo;

Gestion du débordement :

Cependant, le calcul ci-dessus effectue une arithmétique de 128 bits, ce qui peut entraîner un débordement. Pour gérer cela lorsqu'il est limité à l'arithmétique 64 bits, l'implémentation suivante s'ajuste en cas de débordement :

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 = ((uint32_t)a_x_b_mid + (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;

Remarque : Si une erreur de 1 bit dans les 64 bits supérieurs est acceptable, le le calcul du bit de retenue peut être omis.

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!