Comment prouver que les énoncés C -x, ~ x + 1 et ~ (x-1) donnent les mêmes résultats?

Je veux connaître la logique derrière cette affirmation, la preuve. Les expressions C -x, ~ x + 1 et ~ (x-1) donnent les mêmes résultats pour tous les x. Je peux montrer que cela est vrai pour des exemples spécifiques. Je pense que la façon de prouver cela a quelque chose à voir avec les propriétés du complément de deux. Des idées?

Considérez ce que vous obtenez lorsque vous ajoutez un nombre à son complément binary. Le complément au bit d’un entier de n bits x a un 1 partout x a un 0 et vice versa. Donc, il est clair de voir:

x + ~ x = 0b11 … 11 (valeur à n bits de tous les uns)

Quel que soit le nombre de bits dans x. De plus, notez que l’ajout d’un à un nombre à n bits rempli avec tous les uns le fera revenir à zéro. Ainsi on voit:

x + ~ x + 1 = 0b11 … 11 + 1 = 0 et ~ x + 1 = -x.

De même, notez (x – 1) + ~ (x – 1) = 0b11 … 11. Alors (x – 1) + ~ (x – 1) + 1 = 0 et ~ (x – 1) = -x.

Je ne suis pas sûr que vous puissiez le prouver avec un axiome utile autre que la réduction assez sortingviale du fait que nous avons défini des nombres négatifs dans des ALU modernes entières comme étant complémentaires.

Les ordinateurs ne doivent pas nécessairement être mis en œuvre avec du matériel binary complémentaire, c’est simplement qu’il existe diverses propriétés attrayantes et que presque tout est construit de cette façon de nos jours. (Mais pas de virgule flottante! Ce sont son complément!)

Nous construisons donc une machine qui représente des nombres négatifs en complément de 2. Les expressions qui montrent que les nombres négatifs doivent être représentés dans le complément à deux sont exactes, mais uniquement parce que nous les avons définies de cette façon. C’est la base axiomatique des nombres entiers négatifs dans les machines modernes.

Puisque nous définissons la négation en termes de complément à deux, vous faites essentiellement référence aux axiomes, même si je suppose que c’est ce que toutes les preuves font en fin de compte.

C’est peut-être pour cela que je ne suis pas vraiment un théoricien. 🙂

~ x + 1 est équivalent au complément à 2 + 1 (c’est-à-dire un nombre négatif). Les représentations de -x, ~ (x-1) représentent également la même chose (considérons le cas où le dernier bit est 1, ~ (x-1) = ~ ( b1b2.b (n-1) 1 – 0) = b1’b2 ‘… b (n-1)’ 1 = b1’b2 ‘… b (n-1)’ 0 + 1 = ~ x + 1. Un cas similaire pour le dernier bit est 0. ~ (x-1) = ~ (b1b2..bi100..00 – 1) = ~ b1b2..bi011..11 = b1’b2 ‘.. bi’100. .00 = b1’b2 ‘.. bi’011..11 + 1 = ~ x + 1.

Je vais essayer de présenter une explication intuitive que tout le monde devrait trouver pratique. Si vous insistez, nous pouvons essayer une approche plus formelle.

Dans la représentation du complément à deux, afin d’avoir une représentation unique de l’élément zéro, nous sacrifions un élément positif. En conséquence, il existe un nombre négatif supplémentaire qui n’a pas de miroir positif.

Donc, pour 2 bits, nous obtenons: {+1, 0, -1, -2} qui serait représenté en binary par:

 -2 10 -1 11 0 00 +1 01 

Nous pouvons donc considérer le zéro comme un miroir. Maintenant, étant donné un entier x, si nous voulons inverser son signe, nous pouvons commencer par inverser tous les bits. Cela aurait été suffisant s’il n’y avait pas eu de zéro entre les points positifs et négatifs. Mais depuis que le zéro fait un virage positif, nous avons compensé cela.

Les deux expressions mentionnées dans la question effectuent cette compensation avant ~(x-1) et après ~x+1 inversant les bits. Vous pouvez facilement vérifier cela en utilisant +1 et -1 dans notre exemple à 2 bits.

En général, cela n’est pas vrai, car le standard C n’exige pas l’utilisation de complément à deux pour représenter des nombres négatifs.

En particulier, le résultat de l’application de ~ à un type signé n’est pas défini.

Cependant, autant que je sache, toutes les machines modernes utilisent le complément à deux pour les entiers.