Débordement d'une variable de 32 bits

Question

Actuellement, je mets en œuvre une équation (2^A)[X + Y*(2^B)] dans l'une de mes applications.

Le problème concerne le débordement d'une valeur de 32 bits et je ne peux pas utiliser un type de données de 64 bits.

Supposons que lorsque B = 3 y Y = 805306367 , il déborde la valeur de 32 bits, mais lorsque X = -2147483648 le résultat revient à la plage de 32 bits.
Je veux donc stocker le résultat de (Y*2^B) . Quelqu'un peut-il suggérer une solution à ce problème ? .... A et B ont une valeur de -15 a 15 y X , Y peut avoir des valeurs comprises entre 2147483647..-2147483648 .
La production peut varier de 0...4294967295 .

Answer 1

Si le nombre est trop grand pour une variable de 32 bits, il faut soit utiliser plus de bits (soit en stockant dans une variable plus grande, soit en utilisant plusieurs variables), soit renoncer à la précision et le stocker dans un flottant. Puisque Y peut être MAX_INT, par définition, vous ne pouvez pas le multiplier par un nombre supérieur à 1 et le faire tenir dans un int 32 bits.

Answer 2

Dans ce cas, j'utiliserais la boucle au lieu de la multiplication. Quelque chose comme ceci :

int newX = X;
int poweredB = ( 1 << B ); // 2^B
for( int i = 0; i < poweredB ; ++i )
{
    newX += Y; // or change X directly, if you will not need it later.
}
int result = ( 1 << A ) * newX;

Mais note : cela fonctionnera seulement dans certaines situations - uniquement si vous disposez de la garantie pour que ce résultat ne déborde pas. Dans votre cas, lorsque Y est un grand nombre positif et que X est un grand nombre négatif ("grand" - argh, c'est trop subjectif), cela fonctionnera certainement. Mais si X est un grand nombre positif et Y un grand nombre positif, il y aura à nouveau un débordement. Et pas seulement dans ce cas, mais dans beaucoup d'autres.

Answer 3

Sur la base des valeurs de A et B dans le devoir, je suppose que la solution attendue serait la suivante :

• les opérations suivantes sont mieux réalisées sans signe, de sorte que les signes de X et Y sont stockés et que l'opération porte sur leur valeur absolue

• Stocker X et Y dans deux variables, l'une contenant les 16 bits de poids fort, l'autre les bits de poids faible. quelque chose comme
  int hiY = Y & 0xFFFF0000 ;

  int loY = Y & 0x0000FFFF ;

• Décaler les parties hautes vers la droite de façon à ce que toutes les variables aient les bits de poids fort à 0

• Y*(2^B) est en fait un décalage de Y vers la gauche de B bits. Cela équivaut à décaler les parties haute et basse de B bits et, puisque vous avez décalé la partie haute, les deux opérations tiendront dans leur entier de 32 bits.

• Processus X de manière similaire dans les parties haute et basse

• En tenant compte des signes de X et Y, calculer X + Y*(2^B) pour les parties haute et basse.

• Décaler à nouveau les résultats haut et bas de A bits

• Réunir les parties hautes et basses dans le résultat final

Answer 4

Si vous ne pouvez pas utiliser les 64 bits parce que votre système C local ne les prend pas en charge et non pour une autre raison impérieuse, vous pouvez envisager les solutions suivantes La bibliothèque GNU d'arithmétique de précision multiple à http://gmplib.org/