Ajout de nombres entiers signés avec seulement des opérateurs bit à bit dans C (HW)

Question

Pour une affectation de devoir, je dois écrire une fonction dans C qui additionne deux entiers signés, mais retourne INT_MAX s'il y aurait un dépassement positif et INT_MIN s'il y aurait être débordement négatif. Je dois suivre des restrictions très strictes concernant les opérateurs que je peux utiliser. Tous les entiers sont sous forme de complément à deux, les décalages à droite sont arithmétiques, et la taille de l'entier est variable (je peux le trouver avec sizeof (int) < < 3). Je ne peux pas utiliser de contours, de boucles, d'opérateurs de comparaison ou de casting. Je ne peux utiliser que des opérateurs logiques et de bits, des additions et des soustractions, des tests d'égalité et les constantes entières INT_MAX et INT_MIN.

Je sais que le débordement peut être détecté si les deux entrées ont le même signe et le résultat a un signe différent. Je suis arrivé au point où j'ai un drapeau montrant si l'équation a débordé. Je n'ai aucune idée de comment aller de là au produit final. C'est ce que je jusqu'à présent:

int saturating_add(int x, int y){ 
    int w = sizeof(int)<<3; 
    int result = x+y; 
    int signX = (x>>w-1)&0x01;//Sign bit of X 
    int signY = (y>>w-1)&0x01;//Sign bit of Y 
    int resultSign = (result>>w-1)&0x01; //Sign bit of result 
    int canOverflow = ~(signX^signY); //If they're the same sign, they can overflow 
    int didOverflow = (resultSign^signX)&canOverflow; //1 if input signs are same and result sign different, 0 otherwise 

} 

Je suis en train de suivre la réponse à Bitwise saturated addition in C (HW) montré, mais je suis bloqué sur la partie où je dois remplir un entier avec le même bit pour tous, mais la bit de signe (1 passe à 0111..11 et 0 passe à 0000.00). Je n'ai aucune idée de ce que serait la «combinaison des quarts de travail et des RUP».

Answer 1

Je pense que vous avez mal compris la réponse. Ce que vous devez faire est d'étendre le bit de signe à tous des bits, y compris le MSB. Ceci peut être accompli en prenant l'int contenant le bit de signe, par ex. didOverflow, et ajouter 1 à son complément.

Ensuite, vous trouvez quelle valeur de débordement doit être retournée dans le cas d'un débordement. Cela peut être fait par XORing INT_MAX avec étendu signX (ou signY, les deux vont travailler). Appelons cette valeur overflow. Enfin, modifier overflow et result comme ceci:

overflow := (extended didOverflow) AND overflow 
result := (NOT (extended didOverflow)) AND result 

Maintenant, après ces travaux, si le didOverflow est étendu 1 ... 1, alors overflow restera évidemment inchangé. result, d'autre part, sera égale à 0.

Mais si didOverflow est 0 ... 0, est le contraire: overflow est maintenant 0, alors que result reste inchangé.

Dans le premier cas (où didOverflow était 1 ... 1, signalant un dépassement de capacité), overflow OR result correspond à overflow. Dans le second cas (où nous n'avons pas de débordement), overflow OR result est égal à result. Donc de toute façon, overflow OR result nous donnera la valeur correcte.