Ce code est-il toujours évalué à faux? Les deux variables sont des entiers signés du complément à deux.
~x + ~y == ~(x + y)
J'ai l'impression qu'il devrait y avoir un certain nombre qui remplisse les conditions. J'ai essayé de tester les nombres entre -5000
et 5000
mais je n'ai jamais atteint l'égalité. Existe-t-il un moyen de mettre en place une équation pour trouver les solutions à la condition?
Est-ce que l'échange de l'un pour l'autre causera un bug insidieux dans mon programme?
true
même s'ils ne peuvent jamais supposer un complément strict à deux.Réponses:
Supposons, par souci de contradiction, qu'il existe certains
x
et certainsy
(mod 2 n ) tels quePar complément à deux *, nous savons que,
Notant ce résultat, nous avons,
D'où une contradiction. Par conséquent,
~(x+y) != ~x + ~y
pour tousx
ety
(mod 2 n ).* Il est intéressant de noter que sur une machine avec l'arithmétique du complément à un, l'égalité est en fait vraie pour tous
x
ety
. En effet , dans un complément à ,~x = -x
. Ainsi,~x + ~y == -x + -y == -(x+y) == ~(x+y)
.la source
~x == -(x+1)
, donc~(x+y) == ~x + ~y
implique-(x+y+1) == -(x+1) + -(y+1)
implique-1 == -2
Complément à deux
Sur la grande majorité des ordinateurs, si
x
est un entier, alors-x
est représenté par~x + 1
. De manière équivalente,~x == -(x + 1)
. Faire cette substitution dans votre équation donne:ce qui est une contradiction,
~x + ~y == ~(x + y)
c'est toujours faux .Cela dit, les pédants feront remarquer que C ne nécessite pas de complément à deux, il faut donc aussi considérer ...
Complément à soi
Dans son complément ,
-x
est simplement représenté par~x
. Zéro est un cas particulier, ayant à la fois des représentations all-0 (+0
) et all-1's (-0
), mais IIRC, C exige+0 == -0
même s'ils ont des modèles de bits différents, donc cela ne devrait pas être un problème. Remplacez simplement~
par-
.ce qui est vrai pour tous
x
ety
.la source
+0 == -0
. Enfin quelque chose qui a du sens en C. :)Considérez uniquement le bit le plus à droite des deux
x
ety
(IE. Six == 13
qui est1101
en base 2, nous ne regarderons que le dernier bit, a1
) Ensuite, il y a quatre cas possibles:x = 0, y = 0:
x = 0, y = 1:
x = 1, y = 0:
x = 1, y = 1:
Vous pouvez montrer que le bit le plus à droite sera toujours différent du côté gauche et du côté droit de l'équation étant donné toute entrée possible, vous avez donc prouvé que les deux côtés ne sont pas égaux, car ils ont au moins ce bit qui est retourné de chacun d'eux.
la source
Si le nombre de bits est n
Maintenant,
Par conséquent, ils seront toujours inégaux, avec une différence de 1.
la source
~
opération sur des nombres de largeur non fixe?Allusion:
x + ~x = -1
(mod 2 n )En supposant que l'objectif de la question est de tester vos mathématiques (plutôt que vos compétences en lecture des spécifications C), cela devrait vous amener à la réponse.
la source
Dans le complément à un et à deux (et même dans les 42), cela peut être prouvé:
Maintenant, laissez
a = y
et nous avons:ou:
Donc en complément à deux
~0 = -1
, la proposition est fausse.Dans son complément
~0 = 0
, la proposition est vraie.la source
Selon le livre de Dennis Ritchie, C n'implémente pas le complément à deux par défaut. Par conséquent, votre question n'est peut-être pas toujours vraie.
la source
Soit
MAX_INT
le entier représenté par011111...111
(pour le nombre de bits qu'il y a). Alors vous le savez,~x + x = MAX_INT
et~y + y = MAX_INT
donc vous saurez avec certitude que la différence entre~x + ~y
et~(x + y)
est1
.la source
C n'exige pas que le complément à deux soit ce qui est implémenté. Cependant, pour les entiers non signés, des logiques similaires sont appliquées. Les différences seront toujours de 1 dans cette logique!
la source
Bien sûr, C ne nécessite pas ce comportement car il ne nécessite pas de représentation du complément à deux. Par exemple,
~x = (2^n - 1) - x
&~y = (2^n - 1) - y
obtiendra ce résultat.la source
Ah, les mathématiques discrètes fondamentales!
Découvrez la loi de De Morgan
Très important pour les preuves booléennes!
la source