Wie um zu beweisen, dass die C-Anweisung -x ~ x + 1, und ~ (x-1) die gleichen Ergebnisse erzielen?

Question

Ich mag die Logik hinter dieser Aussage wissen, der Beweis. Der Ausdruck C -X, ~ x + 1, und ~ (x-1) all-Ausbeute der gleichen Ergebnisse für jeden x. Ich kann zeigen dies für spezifische Beispiele wahr ist. Ich denke, die Art und Weise dies etwas mit den Eigenschaften des Zweier-Komplements zu tun hat, zu beweisen. Irgendwelche Ideen?

Answer 1

Überlegen Sie, was Sie bekommen, wenn Sie eine Nummer seiner bitweise Komplement hinzuzufügen. Das bitweise Komplement einer n-Bit-Ganzzahl x ein 1 x hat überall ein 0 ist, und umgekehrt. So ist es klar, zu sehen:

x + ~ x = 0b11 ... 11 (n-Bit-Wert von nur Einsen)

Unabhängig von der Anzahl von Bits in x. Ferner, dass Zettel mit allen Einsen gefüllt man zu einer n-Bit-Zahl hinzugefügt wird es auf Null wickeln machen. So sehen wir:

x + ~ x + 1 = 0b11 ... 11 + 1 = 0 und ~ x + 1 = x.

In ähnlicher Weise Notiz (x - 1) + ~ (x - 1) = 0b11 ... 11. Dann (x - 1) + ~ (x - 1) + 1 = 0 und ~ (x - 1). = -X

Answer 2

Ich bin nicht sicher, dass Sie diese von jeder Art von nützlichem Axiom andere als die eher triviale Reduktion auf die Tatsache zurück nachweisen können, dass wir negative Zahlen in der modernen integer ALUs definiert haben in Zweier-Komplement zu sein.

Computer nicht Haben mit Zweier-Komplement-Binär-Hardware implementiert werden, es ist nur, dass es verschiedene attraktive Eigenschaften und fast alles ist in diesen Tagen auf diese Weise gebaut. (Aber nicht floating point! Das ist Einerkomplement!)

So wir eine Maschine bauen, die negativen Zahlen im 2er-Komplement repräsentieren geschieht. Ausdrücke, die negativen Zahlen zeigen, wird in Zweierkomplement dargestellt ist genau, aber nur, weil wir sie auf diese Weise definiert. Das ist die axiomatische Grundlage für negative ganze Zahlen in modernen Maschinen.

Da wir definieren Negation in Bezug auf die Zweier-Komplement, Sie sind im Wesentlichen auf die Axiome beziehen, obwohl ich das mal an, was alle Beweise schließlich tun.

Vielleicht ist der Grund, warum ich nicht wirklich eine Theorie Typ bin. : -)

Answer 3

~ x + 1 ist äquivalent zu 2-Komplement + 1 (dh negative Zahl) Darstellungen von -X, ~ (x-1) auch das gleiche darstellt (der Fall betrachtet, in dem letzten Bit 1 ist, ~ (x-1) = ~ (b1b2.b (n-1) mit 1 - 0) = b1'b2' ... b (n-1) '1 = b1'b2' ... b (n-1) '0 + 1 = . ~ x + 1 ähnlicher Fall Halt für letzten Bit ist 0 ~ (x-1) = ~ (b1b2..bi100..00 - 1) = ~ b1b2..bi011..11 = b1'b2' .. bi '100..00 = b1'b2' .. bi'011..11 + 1 = ~ x + 1.

Answer 4

Ich werde versuchen, eine intuitive explaination zu präsentieren, dass jeder praktisch finden sollte. Wenn Sie darauf bestehen, können wir einen formalen Ansatz versuchen.

In Zweier-Komplement-Darstellung, um eine eindeutige Darstellung des Null-Elements zu haben, opfern wir ein positives Element. Als Ergebnis gibt es eine zusätzliche negative Zahl, die keinen positiven Spiegel hat.

So, 2 Bits gegeben, erhalten wir: {+1, 0, -1, -2} die binär dargestellt werden würde, wie:

-2    10
-1    11
 0    00
+1    01

So können wir die Null denken wie ein Spiegel. Nun, eine ganze Zahl x, wenn wir ihr Vorzeichen invertieren möchten wir durch Invertierung aller Bits beginnen. Dies hätte genügt, wenn es keine Null zwischen den positiven und negativen ist. Da aber die Null eine Verschiebung macht, in positiven Ergebnisse haben wir für das kompensieren.

Die beiden in der Frage erwähnten Ausdrücke machen diese Kompensation vor ~(x-1) und nach ~x+1 die Bits zu invertieren. Sie können ganz einfach überprüfen, ob +1 und -1 in unserem 2-Bit-Beispiel.

Answer 5

Generell dies nicht der Fall ist, da der C-Standard ergänzen nicht die Verwendung von Zweien erfordern negative Zahlen darzustellen.

Insbesondere das Ergebnis der Anwendung ~ zu einem signierten Typ nicht definiert ist.

Allerdings, soweit ich weiß, alle modernen Maschinen Zweierkomplement für ganze Zahlen verwenden.