Comment prouver que la déclaration de C -x, x + 1 ~, et ~ (x-1) donnent les mêmes résultats?

Question

Je veux connaître la logique derrière cette déclaration, la preuve. L'expression de C-x, x + 1 ~ et ~ (x-1) donné les mêmes résultats pour tout x. Je peux montrer cela est vrai pour des exemples précis. Je pense que la façon de prouver cela a quelque chose à voir avec les propriétés du complément à deux. Des idées?

Answer 1

Pensez à ce que vous obtenez lorsque vous ajoutez un numéro à son complément au niveau du bit. Le complément de bits d'un entier à n bits x 1 a un partout x est égal à 0, et vice versa. Il est donc clair pour voir:

x + x = ~ 0b11 ... 11 (valeur n-bit de toutes les)

Quel que soit le nombre de bits de x. En outre, notez que l'ajout d'un à un nombre n bits rempli de tous les envelopper, il sera à zéro. Ainsi, nous voyons:

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

De même, la note (x - 1) + ~ (x - 1) = 0b11 ... 11. Ensuite (x - 1) + ~ (x - 1) + 1 = 0, et ~ (x - 1). = -X

Answer 2

Je ne suis pas certain que vous pouvez prouver de toute sorte d'axiome utile autre que la réduction plutôt trivial revenir au fait que nous avons défini des nombres négatifs dans entier moderne UMM être en complément à deux.

Les ordinateurs ne pas Vous à mettre en œuvre avec le matériel binaire complément à deux, il est juste qu'il ya différentes propriétés intéressantes et presque tout est construit de cette façon ces jours-ci. (Mais pas à virgule flottante! Ce sont un complément à!)

Nous construisons une machine qui arrive à représenter des nombres négatifs en complément de 2. Les expressions qui montrent les nombres négatifs d'être représentés dans complément à deux sont exacts, mais seulement parce que nous les avons définis de cette façon. C'est la base axiomatique pour les nombres entiers négatifs dans les machines modernes.

Puisque nous définissons la négation en termes de complément à deux, vous faites référence essentiellement aux axiomes, bien que je suppose que ce que toutes les preuves en fin de compte faire.

Peut-être cela est la raison pour laquelle je ne suis pas vraiment un gars de la théorie. : -)

Answer 3

~ x + 1 est des représentations équivalentes à complément à 2 + 1 (c.-à-négatif) de -x, ~ (x-1) représente également le même (considérer le cas où dernier bit est 1, ~ (x-1) = ~ (b1b2.b (n-1) 1 - 0) = b1'b2' ... b (n-1) '1 = b1'b2' ... b (n-1) + 1 = 0 . ~ x + 1 prise 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.

Answer 4

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

Dans deux de la représentation du complément, afin d'avoir une représentation unique de l'élément zéro, on sacrifie un élément positif. En conséquence, il y a un nombre supplémentaire négatif qui n'a pas de miroir positif.

Donc, étant donné 2 bits, nous obtenons: {+1, 0, -1, -2} qui serait représenté en binaire comme:

-2    10
-1    11
 0    00
+1    01

Alors, on peut penser à zéro comme un miroir. Maintenant, étant donné un entier x, si l'on veut inverser le signe, nous pouvons commencer à en inversant tous les bits. Cela aurait été suffisant s'il n'y avait pas de zéro entre les points positifs et négatifs. Mais puisque le zéro fait un changement, en points positifs, nous avons compenser.

Les deux expressions mentionnées dans la question font cette compensation avant et après ~(x-1) ~x+1 inverser les bits. Vous pouvez facilement vérifier que l'utilisation +1 et -1 dans notre exemple 2 bits.

Answer 5

En général, ce n'est pas vrai, comme le standard C ne nécessite pas l'utilisation de groupes de deux se complètent pour représenter des nombres négatifs.

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

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