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

Lesezeit: 7 Minuten

Steve

Wird dieser Code immer als falsch ausgewertet? Beide Variablen sind vorzeichenbehaftete Ganzzahlen im Zweierkomplement.

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

Ich denke, es sollte eine Zahl geben, die die Bedingungen erfüllt. Ich habe versucht, die Zahlen dazwischen zu testen -5000 und 5000 aber nie Gleichberechtigung erreicht. Gibt es eine Möglichkeit, eine Gleichung aufzustellen, um die Lösungen der Bedingung zu finden?

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

Willst du einen Beweis oder so?

– Alvin Wong

20. Juni 2012 um 2:18 Uhr
Beachten Sie, dass es sich bei einem Überlauf von vorzeichenbehafteten Ganzzahlen um ein technisch undefiniertes Verhalten handelt. Es ist also möglich, dass es zurückkehrt true auch wenn sie niemals das strikte Zweierkomplement annehmen können.

– Mystisch

20. Juni 2012 um 2:18 Uhr
@AlvinWong ja eine Erklärung wäre nett

– Steve

20. Juni 2012 um 2:21 Uhr
@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, was er nicht versucht hat, sich zuerst selbst zu verdienen. 🙂

– Sarnold

20. Juni 2012 um 2:22 Uhr
@AlexLockwood Als ich die Frage zum ersten Mal stellte, ging ich davon aus, dass das Markieren der Frage als “Hausaufgaben” die Leute auffordert, Hinweise zu geben, um mir bei der Lösung des Problems zu helfen (wie in der Beschreibung des Tags “Hausaufgaben” angegeben) und nicht nur Antworten zu geben. Deshalb habe ich einfach die Frage des Problems gestellt 🙂

– Steve

20. Juni 2012 um 3:21 Uhr

Alex Lockwood

Nehmen Sie zum Zwecke des Widerspruchs an, dass es welche gibt x und einige y (Mod 2ⁿ) 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. Deswegen, ~(x+y) != ~x + ~y für alle x und y (Mod 2ⁿ).

^{*Es ist interessant festzustellen, dass auf einer Maschine mit Einerkomplement-Arithmetik die Gleichheit tatsächlich für alle gilt x und y. Dies liegt daran, dass unter dem Komplement, ~x = -x. Daher, ~x + ~y == -x + -y == -(x+y) == ~(x+y).}

Natürlich erfordert C dieses Verhalten nicht; da es keine Zweierkomplementdarstellung erfordert.

– Billy ONeal

20. Juni 2012 um 2:43 Uhr
Btw, die Gleichheit ist Stimmt für seine Ergänzung. Die NOT-Operation ist im Allgemeinen nicht wirklich für Zahlen definiert, sodass das Mischen von NOT mit Addition je nach Darstellung der Zahl zu unterschiedlichem Verhalten führt.

– nhahtdh

20. Juni 2012 um 2:50 Uhr
Man könnte das Problem einfach umformulieren vorzeichenlose ganze Zahlen und dann kommt das Zweierkomplement überhaupt nicht ins Spiel.

– R.. GitHub HÖR AUF, EIS ZU HELFEN

20. Juni 2012 um 3:20 Uhr
Noch einfacher, IMHO: ~x == -(x+1)Also ~(x+y) == ~x + ~y impliziert -(x+y+1) == -(x+1) + -(y+1) impliziert -1 == -2

– BlueRaja – Danny Pflughoeft

20. Juni 2012 um 16:25 Uhr
@BillyONeal, mach dir keine Sorgen, ich habe nur Spaß gemacht und ich weiß es zu schätzen, dass du es erwähnt hast :). Ich kaufe dir einen Drink an dem Tag, an dem ich auf eine Maschine stoße, die Einer-Komplement-Arithmetik durchführt… wie hört sich das an? Haha

– Alex Lockwood

20. Juni 2012 um 18:58 Uhr

dan04

Zweierkomplement

Auf der groß Mehrheit der Computer, wenn x ist dann eine ganze Zahl -x wird dargestellt als ~x + 1. Äquivalent, ~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

was ein Widerspruch ist, also ~x + ~y == ~(x + y) ist immer FALSCH.

Die Pedanten werden jedoch darauf hinweisen, dass C kein Zweierkomplement erfordert, also müssen wir auch berücksichtigen …

Einerkomplement

Im seine Ergänzung, -x wird einfach dargestellt als ~x. Null ist ein Sonderfall, der beide nur Nullen hat (+0) und alle-1 (-0) Darstellungen, aber IIRC, C erfordert +0 == -0 auch wenn sie unterschiedliche Bitmuster haben, sollte dies kein Problem sein. Einfach ersetzen ~ mit -.

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

welches ist Stimmt für alle x und y.

+1 für eine Antwort, die sowohl das Zweierkomplement als auch das Einerkomplement tatsächlich gleichberechtigt berücksichtigt.

– Benutzer

20. Juni 2012 um 7:12 Uhr
@dan04, +0 == -0. Endlich etwas Sinnvolles in C. 🙂

– Alex Lockwood

20. Juni 2012 um 13:25 Uhr

Paul

Betrachten Sie nur das rechte Bit von beiden x und y (IE. wenn x == 13 welches ist 1101 In Basis 2 betrachten wir nur das letzte Bit, a 1) Dann gibt es vier mögliche Fälle:

x = 0, y = 0:

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

x = 0, y = 1:

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

x = 1, y = 0:

Ich überlasse dies Ihnen, da dies eine Hausaufgabe ist (Hinweis: Es ist dasselbe wie das vorherige, wobei x und y vertauscht sind).

x = 1, y = 1:

Auch dies überlasse ich Ihnen.

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, sodass Sie bewiesen haben, dass beide Seiten nicht gleich sind, da sie mindestens das eine Bit haben, das umgedreht ist von einander.

Karthik Kumar Viswanathan

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.

Benutzer541686

Hinweis:

x + ~x = -1 (Mod 2ⁿ)

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 führen.

Nur auf Zweierkomplementmaschinen. (Der C-Standard verlangt das nicht)

– Billy ONeal

20. Juni 2012 um 2:42 Uhr
@Billy: Das ist wie zu sagen “nur für Zweiarmige”.

– dan04

20. Juni 2012 um 5:03 Uhr
@dan04: Nein, ist es nicht. Ich würde gerne sagen, dass alle signierten Größen- und Komplementdarstellungen aus der Welt verschwunden sind. Aber ich wäre falsch, wenn ich das sagen würde. Der C-Standard erlaubt Ihnen diese Annahme nicht; Daher würde ich sagen, dass Code, der diese Annahme macht, meistens schlechter Code ist. (Vor allem, wenn es normalerweise bessere Möglichkeiten gibt, mit vorzeichenbehafteten Zahlen herumzuspielen, als ein bisschen herumzuspielen; und besonders, wenn vorzeichenlose Zahlen wahrscheinlich sowieso die meiste Zeit die bessere Wahl sind.)

– Billy ONeal

20. Juni 2012 um 17:53 Uhr

ypercubeᵀᴹ

Dies kann sowohl im Einer- als auch im Zweier- (und sogar im 42er-) Komplement bewiesen werden:

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

Nun lass a = y und wir haben:

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

oder:

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

Also im Zweierkomplement das ~0 = -1die Behauptung ist falsch.

In Ergänzung dazu ~0 = 0die Behauptung ist wahr.

Nur auf Zweierkomplementmaschinen. (Der C-Standard verlangt das nicht)

– Billy ONeal

20. Juni 2012 um 2:42 Uhr
@Billy: Das ist wie zu sagen “nur für Zweiarmige”.

– dan04

20. Juni 2012 um 5:03 Uhr
@dan04: Nein, ist es nicht. Ich würde gerne sagen, dass alle signierten Größen- und Komplementdarstellungen aus der Welt verschwunden sind. Aber ich wäre falsch, wenn ich das sagen würde. Der C-Standard erlaubt Ihnen diese Annahme nicht; Daher würde ich sagen, dass Code, der diese Annahme macht, meistens schlechter Code ist. (Vor allem, wenn es normalerweise bessere Möglichkeiten gibt, mit vorzeichenbehafteten Zahlen herumzuspielen, als ein bisschen herumzuspielen; und besonders, wenn vorzeichenlose Zahlen wahrscheinlich sowieso die meiste Zeit die bessere Wahl sind.)

– Billy ONeal

20. Juni 2012 um 17:53 Uhr

Benutzer1457474

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

14243400cookie-check~x + ~y == ~(x + y) ist immer falsch?

#Bit-Manipulation #c++ #unterzeichnet #Zweierkomplement