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 -5000
und 5000
doch 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?
true
selbst wenn sie niemals ein striktes Zweierkomplement annehmen können.Antworten:
Nehmen wir im Widerspruch an, dass es einige
x
und einigey
(mod 2 n ) gibt, so dassDurch das Zweierkomplement * wissen wir, dass
Unter Berücksichtigung dieses Ergebnisses haben wir:
Daher ein Widerspruch. Daher
~(x+y) != ~x + ~y
für allex
undy
(mod 2 n ).* Es ist interessant festzustellen, dass auf einer Maschine mit Komplementarithmetik die Gleichheit tatsächlich für alle
x
und gilty
. Dies liegt daran, dass unter der eigenen Ergänzung ,~x = -x
. Also ,~x + ~y == -x + -y == -(x+y) == ~(x+y)
.quelle
~x == -(x+1)
,~(x+y) == ~x + ~y
impliziert-(x+y+1) == -(x+1) + -(y+1)
also-1 == -2
Zweierkomplement
Wenn auf der überwiegenden Mehrheit der Computer
x
eine Ganzzahl vorliegt,-x
wird diese als dargestellt~x + 1
. Gleichermaßen~x == -(x + 1)
. Wenn Sie diese Substitution in Ihrer Gleichung vornehmen, erhalten Sie: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 ,
-x
ist einfach dargestellt als~x
. Null ist ein Sonderfall, der sowohl All-0- Darstellungen (+0
) als auch All-1--0
Darstellungen ( ) enthält. IIRC, C erfordert jedoch+0 == -0
auch dann, wenn sie unterschiedliche Bitmuster aufweisen, sodass dies kein Problem sein sollte. Nur Ersatz~
mit-
.das gilt für alle
x
undy
.quelle
+0 == -0
. Endlich etwas, das in C. Sinn macht :)Betrachten Sie nur das Bit ganz rechts von beiden
x
undy
(IE. Wenn sichx == 13
das1101
in Basis 2 befindet, betrachten wir nur das letzte Bit, a1
) Dann gibt es vier mögliche Fälle:x = 0, y = 0:
x = 0, y = 1:
x = 1, y = 0:
x = 1, y = 1:
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.
quelle
Wenn die Anzahl der Bits n ist
Jetzt,
Daher sind sie immer ungleich, mit einer Differenz von 1.
quelle
~
Operation für Zahlen mit nicht fester Breite?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.
quelle
Dies kann sowohl im Einsen als auch im Zweier (und sogar im 42er) nachgewiesen werden:
Jetzt lassen Sie
a = y
und wir haben:oder:
Daher ist in Zweierkomplementierung
~0 = -1
der Satz falsch.In der Ergänzung dazu
~0 = 0
ist der Satz wahr.quelle
Laut dem Buch von Dennis Ritchie implementiert C standardmäßig keine Zweierkomplemente. Daher ist Ihre Frage möglicherweise nicht immer wahr.
quelle
Lassen Sie
MAX_INT
das int dargestellt werden durch011111...111
(für wie viele Bits es gibt). Dann wissen Sie das,~x + x = MAX_INT
und~y + y = MAX_INT
deshalb werden Sie mit Sicherheit wissen, dass der Unterschied zwischen~x + ~y
und~(x + y)
ist1
.quelle
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!
quelle
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) - y
dieses Ergebnis.quelle
Ah, grundlegende diskrete Mathematik!
Schauen Sie sich De Morgans Gesetz an
Sehr wichtig für Boolesche Beweise!
quelle