~ x + ~ y == ~ (x + y) est toujours faux?

153

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 -5000et 5000mais 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?

Steve
la source
6
Voulez-vous une preuve ou quelque chose?
Alvin Wong
26
Sachez que dans les cas de dépassement d'entier signé, il s'agit d'un comportement techniquement indéfini. Il est donc possible qu'il revienne truemême s'ils ne peuvent jamais supposer un complément strict à deux.
Mysticial
1
@AlvinWong oui une explication serait bien
Steve
1
@Steve: Vous pouvez démontrer que vous avez essayé tous les suspects habituels (-1, 0, 1, 2, etc.) dans toutes les combinaisons, ainsi que vos tentatives de "résoudre" le problème des petits mots ( trois bits? quatre bits?). Cela nous aiderait certainement à nous convaincre que nous ne nous contentons pas d'aider quelqu'un à obtenir quelque chose qu'il n'a pas essayé de gagner en premier. :)
sarnold
4
@AlexLockwood Lorsque j'ai posté la question pour la première fois, j'ai supposé que le fait de marquer la question comme "devoirs" demandait aux gens de fournir des indices pour m'aider à résoudre le problème (comme l'indique la description de l'étiquette "devoirs") et pas seulement de donner des réponses. C'est pourquoi j'ai simplement posé la question du problème :)
Steve

Réponses:

237

Supposons, par souci de contradiction, qu'il existe certains xet certains y(mod 2 n ) tels que

~(x+y) == ~x + ~y

Par complément à deux *, nous savons que,

      -x == ~x + 1
<==>  -1 == ~x + x

Notant ce résultat, nous avons,

      ~(x+y) == ~x + ~y
<==>  ~(x+y) + (x+y) == ~x + ~y + (x+y)
<==>  ~(x+y) + (x+y) == (~x + x) + (~y + y)
<==>  ~(x+y) + (x+y) == -1 + -1
<==>  ~(x+y) + (x+y) == -2
<==>  -1 == -2

D'où une contradiction. Par conséquent, ~(x+y) != ~x + ~ypour tous xet y(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 xet y. En effet , dans un complément à , ~x = -x. Ainsi, ~x + ~y == -x + -y == -(x+y) == ~(x+y).

Alex Lockwood
la source
47
Bien sûr, C n'a pas besoin de ce comportement; car il ne nécessite pas de représentation du complément à deux.
Billy ONeal
12
Btw, l'égalité est vraie pour son complément. L'opération NOT n'est pas vraiment définie pour le nombre en général, donc mélanger NOT avec l'addition entraîne un comportement différent en fonction de la représentation du nombre.
nhahtdh
9
On pourrait simplement reformuler le problème comme étant des entiers non signés , puis le complément à deux n'entre pas du tout en jeu.
R .. GitHub STOP HELPING ICE
5
Encore plus simple, à mon humble avis: ~x == -(x+1), donc ~(x+y) == ~x + ~yimplique -(x+y+1) == -(x+1) + -(y+1)implique-1 == -2
BlueRaja - Danny Pflughoeft
7
@BillyONeal, ne vous inquiétez pas, je plaisantais et j'apprécie que vous en ayez parlé :). Je vous achèterai un verre le jour où je rencontrerai une machine qui exécute son arithmétique complémentaire ... comment ça sonne? haha
Alex Lockwood
113

Complément à deux

Sur la grande majorité des ordinateurs, si xest un entier, alors -xest représenté par ~x + 1. De manière équivalente, ~x == -(x + 1). Faire cette substitution dans votre équation donne:

  • ~ x + ~ y == ~ (x + y)
  • - (x + 1) + - (y + 1) = - ((x + y) + 1)
  • -x - y - 2 = -x - y - 1
  • -2 = -1

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 , -xest 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 == -0même s'ils ont des modèles de bits différents, donc cela ne devrait pas être un problème. Remplacez simplement ~par -.

  • ~ x + ~ y == ~ (x + y)
  • -x + (-y) = - (x + y)

ce qui est vrai pour tous xet y.

dan04
la source
13
+1 pour une réponse qui considère réellement le complément à deux et le complément à un sur un pied d'égalité.
un CVn le
13
@ dan04, +0 == -0. Enfin quelque chose qui a du sens en C. :)
Alex Lockwood
32

Considérez uniquement le bit le plus à droite des deux xet y(IE. Si x == 13qui est 1101en base 2, nous ne regarderons que le dernier bit, a 1) Ensuite, il y a quatre cas possibles:

x = 0, y = 0:

LHS: ~ 0 + ~ 0 => 1 + 1 => 10
RHS: ~ (0 + 0) => ~ 0 => 1

x = 0, y = 1:

LHS: ~ 0 + ~ 1 => 1 + 0 => 1
RHS: ~ (0 + 1) => ~ 1 => 0

x = 1, y = 0:

Je vais vous laisser cela car c'est un devoir (indice: c'est le même que le précédent avec x et y échangés).

x = 1, y = 1:

Je vais également vous laisser celui-là.

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.

Paul
la source
27

Si le nombre de bits est n

~x = (2^n - 1) - x
~y = (2^n - 1) - y


~x + ~y = (2^n - 1) +(2^n - 1) - x - y =>  (2^n + (2^n - 1) - x - y ) - 1 => modulo: (2^n - 1) - x - y - 1.

Maintenant,

 ~(x + y) = (2^n - 1) - (x + y) = (2^n - 1) - x - y.

Par conséquent, ils seront toujours inégaux, avec une différence de 1.

Karthik Kumar Viswanathan
la source
4
@nhahtdh et comment définissez-vous l' ~opération sur des nombres de largeur non fixe?
hamstergene
1
J'ai donné cette réponse avec ce nombre de bits afin qu'il soit facile de corréler avec ce qui est enseigné en classe. Notez que ~ x dépend fortement du nombre de bits, n, utilisé pour représenter le nombre. Il est donc judicieux de s'en tenir à un, lorsque vous essayez de vérifier cela expérimentalement.
Karthik Kumar Viswanathan
1
@hamstergene: Je sais que le nombre de bits est fixe, mais ce que je veux dire, c'est qu'il n'est pas nécessaire que ce soit ces montants (8, 16, etc.).
nhahtdh
1
Ce sont des valeurs pour lesquelles il est facile d'écrire un programme pour vérifier la réponse. Cela fonctionne pour n'importe quel n, tant que ~ x et ~ y sont écrits pour correspondre à celui donné.
Karthik Kumar Viswanathan
1
@hamstergene: Je n'ai pas de problème avec la preuve, juste que les chiffres donnent la fausse implication que cela ne fonctionne que pour ces cas.
nhahtdh
27

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.

user541686
la source
2
Seulement sur deux machines complémentaires. (La norme C n'exige pas cela)
Billy ONeal
12
@Billy: C'est comme dire "uniquement pour les personnes à deux bras".
dan04
2
@ dan04: Non, ce n'est pas le cas. J'adorerais dire que toutes les magnitudes signées et les représentations complémentaires ont disparu du monde. Mais j'aurais tort de dire cela. La norme C ne vous permet pas de faire cette hypothèse; donc je dirais que le code qui fait cette supposition est un mauvais code la plupart du temps. (Surtout quand il y a généralement de meilleures façons de jouer avec les nombres signés que le twiddling; et en particulier lorsque les nombres non signés sont probablement un meilleur choix la plupart du temps de toute façon)
Billy ONeal
10

Dans le complément à un et à deux (et même dans les 42), cela peut être prouvé:

~x + ~y == ~(x + a) + ~(y - a)

Maintenant, laissez a = yet nous avons:

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

ou:

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

Donc en complément à deux ~0 = -1, la proposition est fausse.

Dans son complément ~0 = 0, la proposition est vraie.

ypercubeᵀᴹ
la source
7

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.

user1457474
la source
5

Soit MAX_INTle entier représenté par 011111...111(pour le nombre de bits qu'il y a). Alors vous le savez, ~x + x = MAX_INTet ~y + y = MAX_INTdonc vous saurez avec certitude que la différence entre ~x + ~yet ~(x + y)est 1.

Adrian Monk
la source
5

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!

user1422551
la source
3

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) - yobtiendra ce résultat.

user1472392
la source
0

Ah, les mathématiques discrètes fondamentales!

Découvrez la loi de De Morgan

~x & ~y == ~(x | y)

~x | ~y == ~(x & y)

Très important pour les preuves booléennes!

David Kaczynski
la source
Tout simplement faux. En C + est addition, * multiplication et non booléen ou ou et.
nalply le
Merci d'avoir signalé les mauvais opérateurs, nalply. Il a maintenant été mis à jour avec les bons opérateurs, bien que vous ayez raison en ce sens qu'il ne s'applique pas à la question d'origine.
David Kaczynski
1
Eh bien, si vrai est un et faux est zéro, alors + et * se comportent exactement comme ou et et, de plus le complément à deux se comporte comme non, d'où la loi s'applique néanmoins.
a1an
Merci de l'avoir signalé, a1an. J'essayais de penser à la façon dont les lois de De Morgan pourraient encore être applicables à la question initiale, mais cela fait plusieurs années que j'ai étudié la programmation C ou les mathématiques discrètes.
David Kaczynski