Problèmes arithmétiques non signés / signés du manuel d’un programmeur

int x = random(); int y = random(); unsigned ux = (unsigned) x; unsigned uy = (unsigned) y; 

Pour chacune des expressions C suivantes, vous devez indiquer si l’expression donne toujours 1. Si elle donne toujours 1, décrivez les principes mathématiques sous-jacents. Sinon, donnez un exemple d’arguments qui lui donnent 0.

 A. (x-y) B. ((x+y)<> 2) << 2) <= x 

Pour ces questions, j’ai compris que seul A pouvait céder 0 tandis que le rest donnait toujours 1.

Je sais que c’est probablement faux et que je ne cherche pas de réponses directes, mais j’espérais obtenir des connaissances générales / des conseils sur la manière d’aborder ces problèmes.

J’ai un très mauvais professeur et j’essaie de trouver des ressources en ligne, mais je ne sais pas vraiment par où commencer ni quoi rechercher. Je connais les bases de l’arithmétique du complément non signé / deux et du transfert de bits, mais je ne sais pas comment l’appliquer pour trouver des solutions à ces problèmes.

Le langage de programmation C ne spécifie pas le résultat d’un débordement de quantités intégrales signées; il ne définit pas non plus x << n si x est signé et négatif.

Cependant, il n'est pas rare que des opérations arithmétiques soient effectuées quel que soit le signe, considérant à la fois les entiers à n bits binarys signés et non signés comme des nombres modulo 2 ^ n représentés dans le système du complément à deux.

Ceci doit être supposé pour votre exercice, ce qui n'a presque aucun sens autrement.

Exemple pour les entiers 8 bits:

 unsigned domain: (0..127), ( 128..255) signed domain: (0..127), (-128..-1) 

en représentation binary:

 unsigned domain: 00000000..01111111 and 10000000..11111111 signed domain: 00000000..01111111 and 10000000..11111111 

Entre signé et non signé, seul le système représentatif des entiers modulo 2 ^ n diffère, ce qui est pertinent pour l'impression, mais pas pour les calculs internes (tant que seules les opérations + , - , * et au niveau du bit sont utilisées).

Pour les entiers signés, exactement le premier bit des entiers négatifs est défini sur 1. Les transferts entre signés et non signés ne sont pas pertinents, sauf pour l'impression.

J'insiste pour dire que cela est supposé pour vos exercices, mais le langage de programmation C ne spécifie pas la plupart de mes revendications.

A. (x-y)

Est réfuté par x == INT_MIN , y == INT_MIN + 1 , car INT_MIN == -INT_MIN .

B. ((x+y)<<4) + yx == 17*y+15*x

Vrai:

  ((x+y) << 4 ) + yx == ((x+y) * 0x10000) + yx == ((x+y) * 16 ) + yx == 17 * y + 15 * x 

C. ~x+~y+1 == ~(x+y)

Vrai:

 x + ~x + 1 == 0 ~x + 1 == -x ~(x+y) + 1 == -(x+y) ~(x+y) + 1 == -x + -y ~(x+y) + 1 == ~x + 1 + ~y + 1 ~(x+y) == ~x + ~y + 1 

D. ((unsigned)x-(unsigned)y) == -(unsigned)(yx)

True: la conversion de signé en non signé est supposée ne pas changer la représentation interne et les opérateurs sont supposés ignorer la signature des entiers. En d'autres termes, xy == -(yx) est valable partout.

E. ((x >> 2) << 2) <= x

Vrai:

  x == (x >> 2) << 2 + two_last_significant_bits_of_x == (x >> 2) << 2 + positive >= (x >> 2) << 2 

Exemples avec des entiers 32 bits signés:

 x == 5 x == 00000000000000000000000000000101 in base2 x >> 2 == 00000000000000000000000000000001 in base2 (x >> 2) << 2 == 00000000000000000000000000000100 in base2 (x >> 2) << 2 == 4 x == -5 x == 11111111111111111111111111111011 in base2 x >> 2 == 11111111111111111111111111111110 in base2 (x >> 2) << 2 == 11111111111111111111111111111000 in base2 (x >> 2) << 2 == -8