~ x + ~ y == ~ (x + y) ist immer falsch?

153

Wird dieser Code immer als falsch ausgewertet? Beide Variablen sind Zweierkomplement-Ints.

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

Ich denke, es sollte eine Nummer geben, die die Bedingungen erfüllt. Ich habe versucht , die Zahlen zwischen Prüfung -5000und 5000doch nie erreicht Gleichheit. Gibt es eine Möglichkeit, eine Gleichung aufzustellen, um die Lösungen für die Bedingung zu finden?

Wird das Austauschen eines gegen das andere einen heimtückischen Fehler in meinem Programm verursachen?

Steve
quelle
6
Willst du einen Beweis oder so?
Alvin Wong
26
Beachten Sie, dass es sich bei einem vorzeichenbehafteten Ganzzahlüberlauf um ein technisch undefiniertes Verhalten handelt. Es ist also möglich, dass es zurückkehrt, trueselbst wenn sie niemals ein striktes Zweierkomplement annehmen können.
Mysticial
1
@ AlvinWong ja eine Erklärung wäre schön
Steve
1
@Steve: Sie könnten zeigen, dass Sie alle üblichen Verdächtigen (-1, 0, 1, 2 usw.) in allen Kombinationen ausprobiert haben, sowie Ihre Versuche, das Problem für kleine Wortgrößen zu "lösen" ( drei Bits? vier Bits?). Das würde uns definitiv davon überzeugen, dass wir nicht nur jemandem helfen, etwas zu bekommen, das er nicht zuerst für sich selbst verdienen wollte. :)
Sarnold
4
@AlexLockwood Als ich die Frage zum ersten Mal gepostet habe, habe ich angenommen, dass das Markieren der Frage als "Hausaufgabe" die Leute auffordert, Hinweise zur Lösung des Problems zu geben (wie in der Beschreibung des Tags "Hausaufgaben" angegeben) und nicht nur Antworten zu geben. Deshalb habe ich einfach die Frage des Problems gestellt :)
Steve

Antworten:

237

Nehmen wir im Widerspruch an, dass es einige xund einige y(mod 2 n ) gibt, so dass

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

Durch das Zweierkomplement * wissen wir, dass

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

Unter Berücksichtigung dieses Ergebnisses haben wir:

      ~(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

Daher ein Widerspruch. Daher ~(x+y) != ~x + ~yfür alle xund y(mod 2 n ).


* Es ist interessant festzustellen, dass auf einer Maschine mit Komplementarithmetik die Gleichheit tatsächlich für alle xund gilt y. Dies liegt daran, dass unter der eigenen Ergänzung , ~x = -x. Also , ~x + ~y == -x + -y == -(x+y) == ~(x+y).

Alex Lockwood
quelle
47
Natürlich benötigt C dieses Verhalten nicht. da es keine Zweierkomplementdarstellung erfordert.
Billy ONeal
12
Btw, ist die Gleichheit wahr für Einerkomplement. Die NOT-Operation ist im Allgemeinen nicht wirklich für die Zahl definiert, daher führt das Mischen von NOT mit Addition je nach Darstellung der Zahl zu einem unterschiedlichen Verhalten.
nhahtdh
9
Man könnte das Problem nur für vorzeichenlose ganze Zahlen wiederholen, und dann kommt das Zweierkomplement überhaupt nicht ins Spiel.
R .. GitHub STOP HELPING ICE
5
Noch einfacher, IMHO : ~x == -(x+1), ~(x+y) == ~x + ~yimpliziert -(x+y+1) == -(x+1) + -(y+1)also-1 == -2
BlueRaja - Danny Pflughoeft
7
@ BillyONeal, keine Sorge, ich habe nur Spaß gemacht und ich schätze, dass du es erwähnt hast :). Ich werde dir an dem Tag ein Getränk kaufen, an dem ich auf eine Maschine stoße, die die komplementäre Arithmetik ausführt ... wie klingt das? haha
Alex Lockwood
113

Zweierkomplement

Wenn auf der überwiegenden Mehrheit der Computer xeine Ganzzahl vorliegt, -xwird diese als dargestellt ~x + 1. Gleichermaßen ~x == -(x + 1). Wenn Sie diese Substitution in Ihrer Gleichung vornehmen, erhalten Sie:

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

Das ist ein Widerspruch, also ~x + ~y == ~(x + y)immer falsch .


Das heißt, die Pedanten werden darauf hinweisen, dass C kein Zweierkomplement benötigt, also müssen wir auch berücksichtigen ...

Komplement

In Einerkomplement , -xist einfach dargestellt als ~x. Null ist ein Sonderfall, der sowohl All-0- Darstellungen ( +0) als auch All-1- -0Darstellungen ( ) enthält. IIRC, C erfordert jedoch +0 == -0auch dann, wenn sie unterschiedliche Bitmuster aufweisen, sodass dies kein Problem sein sollte. Nur Ersatz ~mit -.

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

das gilt für alle xund y.

dan04
quelle
13
+1 für eine Antwort, bei der sowohl das Zweierkomplement als auch das Zweierkomplement gleichermaßen berücksichtigt werden.
Ein CVn
13
@ dan04 , +0 == -0. Endlich etwas, das in C. Sinn macht :)
Alex Lockwood
32

Betrachten Sie nur das Bit ganz rechts von beiden xund y(IE. Wenn sich x == 13das 1101in Basis 2 befindet, betrachten wir nur das letzte Bit, a 1) Dann gibt es vier mögliche Fälle:

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:

Ich werde dies Ihnen überlassen, da dies Hausaufgaben sind (Hinweis: Es ist dasselbe wie das vorherige mit x und y getauscht).

x = 1, y = 1:

Ich werde dies auch Ihnen überlassen.

Sie können zeigen, dass das Bit ganz rechts auf der linken Seite und der rechten Seite der Gleichung bei jeder möglichen Eingabe immer unterschiedlich ist. Sie haben also bewiesen, dass beide Seiten nicht gleich sind, da mindestens das eine Bit gespiegelt ist von einander.

Paul
quelle
27

Wenn die Anzahl der Bits n ist

~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.

Jetzt,

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

Daher sind sie immer ungleich, mit einer Differenz von 1.

Karthik Kumar Viswanathan
quelle
4
@nhahtdh und wie definieren Sie die ~Operation für Zahlen mit nicht fester Breite?
Hamstergen
1
Ich habe diese Antwort mit dieser Anzahl von Bits gegeben, damit es leicht ist, mit dem zu korrelieren, was in Klassen gelehrt wird. Beachten Sie, dass ~ x stark von der Anzahl der Bits n abhängt, die zur Darstellung der Anzahl verwendet werden. Es ist also sinnvoll, sich an eine zu halten, wenn Sie versuchen, dies experimentell zu überprüfen.
Karthik Kumar Viswanathan
1
@hamstergene: Ich weiß, dass die Anzahl der Bits festgelegt ist, aber mein Punkt ist, dass es nicht diese Menge sein muss (8, 16 usw.).
nhahtdh
1
Dies sind Werte, für die es einfach ist, ein Programm zu schreiben, um die Antwort zu überprüfen. Es funktioniert für jedes n, solange ~ x und ~ y so geschrieben sind, dass sie mit dem angegebenen übereinstimmen.
Karthik Kumar Viswanathan
1
@hamstergene: Ich habe kein Problem mit dem Beweis, nur dass die Zahlen die falsche Implikation geben, dass es nur für diese Fälle funktioniert.
nhahtdh
27

Hinweis:

x + ~x = -1(mod 2 n )

Angenommen, das Ziel der Frage besteht darin, Ihre Mathematik zu testen (und nicht Ihre Fähigkeiten zum Lesen der C-Spezifikationen), sollte dies Sie zur Antwort bringen.

user541686
quelle
2
Nur auf Zweierkomplementmaschinen. (Der C-Standard verlangt das nicht)
Billy ONeal
12
@ Billy: Das ist so, als würde man "nur für zweiarmige Leute" sagen.
dan04
2
@ dan04: Nein, das ist es nicht. Ich würde gerne sagen, dass alle signierten Größen und Ergänzungsdarstellungen von der Welt verschwunden sind. Aber ich würde mich irren, wenn ich das sage. Der C-Standard erlaubt Ihnen nicht, diese Annahme zu treffen. Daher würde ich sagen, dass Code, der diese Annahme macht, die meiste Zeit schlechter Code ist. (Besonders wenn es normalerweise bessere Möglichkeiten gibt, mit vorzeichenbehafteten Zahlen herumzuspielen als mit Bit Twiddling; und besonders wenn vorzeichenlose Zahlen wahrscheinlich sowieso die meiste Zeit die bessere Wahl sind)
Billy ONeal
10

Dies kann sowohl im Einsen als auch im Zweier (und sogar im 42er) nachgewiesen werden:

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

Jetzt lassen Sie a = yund wir haben:

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

oder:

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

Daher ist in Zweierkomplementierung ~0 = -1der Satz falsch.

In der Ergänzung dazu ~0 = 0ist der Satz wahr.

ypercubeᵀᴹ
quelle
7

Laut dem Buch von Dennis Ritchie implementiert C standardmäßig keine Zweierkomplemente. Daher ist Ihre Frage möglicherweise nicht immer wahr.

user1457474
quelle
5

Lassen Sie MAX_INTdas int dargestellt werden durch 011111...111(für wie viele Bits es gibt). Dann wissen Sie das, ~x + x = MAX_INTund ~y + y = MAX_INTdeshalb werden Sie mit Sicherheit wissen, dass der Unterschied zwischen ~x + ~yund ~(x + y)ist 1.

Adrian Monk
quelle
5

C erfordert nicht, dass das Zweierkomplement das ist, was implementiert wird. Für vorzeichenlose Ganzzahlen wird jedoch eine ähnliche Logik angewendet. Unterschiede werden unter dieser Logik immer 1 sein!

user1422551
quelle
3

Natürlich erfordert C dieses Verhalten nicht, da es keine Zweierkomplementdarstellung erfordert. Zum Beispiel erhält ~x = (2^n - 1) - x& ~y = (2^n - 1) - ydieses Ergebnis.

user1472392
quelle
0

Ah, grundlegende diskrete Mathematik!

Schauen Sie sich De Morgans Gesetz an

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

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

Sehr wichtig für Boolesche Beweise!

David Kaczynski
quelle
Einfach falsch. In C + ist Addition, * Multiplikation und nicht boolesch oder oder und.
Nalply
Vielen Dank, dass Sie auf die falschen Operatoren hingewiesen haben. Es wurde jetzt mit den richtigen Operatoren aktualisiert, obwohl Sie insofern richtig sind, als es nicht für die ursprüngliche Frage gilt.
David Kaczynski
1
Nun, wenn wahr eins ist und falsch null ist, dann verhalten sich + und * genau wie oder und und außerdem verhält sich das Zweierkomplement wie nicht, daher gilt das Gesetz trotzdem.
a1an
Danke, dass Sie darauf hingewiesen haben, a1an. Ich habe versucht zu überlegen, wie De Morgans Gesetze noch auf die ursprüngliche Frage anwendbar sein könnten, aber es ist einige Jahre her, seit ich entweder C-Programmierung oder Diskrete Mathematik studiert habe.
David Kaczynski