Kann XOR zweier Ganzzahlen außerhalb der Grenzen liegen?

Question 1

Ich hatte den Algorithmus zum Auffinden einsamer Ganzzahlen in einem Array studiert, und hier ist die Implementierung:

int arr[] = {10, 20, 30, 5, 20, 10, 30};
int LonelyInteger = 0;
for(int i=0; i< 7; i++)
{
    LonelyInteger = LonelyInteger ^ arr[i];
}

Das Ergebnis ist 5.

Meine Frage ist – angeblich die ganzen Zahlen (die von der XOR Betrieb) sind zu groß aufgrund dieser Operation:

LonelyInteger ^ arr[i]

Was zu einer potenziell großen Ganzzahl führt, die beispielsweise nicht durch den Datentyp dargestellt werden kann int in diesem Fall. Meine Fragen sind:

Ist das überhaupt möglich XOR generiert einen so großen ganzzahligen Wert, der nicht in gespeichert werden kann int Typ?

Wenn es nicht möglich ist, dass dies passieren kann, gibt es dann einen Beweis dafür?

Question 2

XOR wird niemals die Grenzen überschreiten, da es Bits kombiniert und keine neuen Bits erzeugt, wo zuvor keine Bits gesetzt wurden.

Das Ergebnis 5 ist richtig. Betrachten Sie die binäre Darstellung Ihres Wertes und die XOR Ergebnis

10    00001010
20    00010100
30    00011110
 5    00000101
20    00010100
10    00001010
30    00011110
--------------
      00000101 => 5

Eine einfache Hilfe zur Berechnung eines Ergebnisses aus vielen XORed-Werte ist: Das Ergebnis hat ein gesetztes Bit, wenn eine ungerade Anzahl von Bits kombiniert wird, kein gesetztes Bit für eine gerade Anzahl von Bits.

Wenn es nicht möglich ist, dass dies passieren kann, gibt es dann einen Beweis dafür?

XOR entspricht einer Addition ohne Übertrag auf die einzelnen Bits. Wenn Sie Bits ohne Übertrag hinzufügen, kann kein Überlauf auftreten und so weiter int Wert kann nicht außerhalb der Grenzen liegen.

Question 3

Das Ergebnis kann niemals “zu groß” in dem Sinne sein, dass seine Darstellung mehr Bits erfordert als int liefert, da die Operation so definiert ist, dass sie Bitwerte ihrer Operanden kombiniert, keine neuen Bits. Vielleicht wäre eine bessere Frage, ob das Ergebnis etwas anderes als eine gültige Wertdarstellung von an sein kann int?

Für Ganzzahlen ohne Vorzeichen nein. Alle Bitmuster und damit das Ergebnis aller bitweisen Operationen sind gültige Wertdarstellungen.

Bei Ganzzahlen mit Vorzeichen hängt dies von der implementierungsdefinierten Darstellung negativer Werte ab. Jede Implementierung, der Sie wahrscheinlich begegnen werden, verwendet Zweierkomplemente, in denen wiederum jedes Bitmuster gültig ist; Das Ergebnis jeder bitweisen Operation ist also wieder eine gültige Darstellung.

Der Standard erlaubt aber auch andere Darstellungen, bei denen ein oder mehrere ungültige Bitmuster vorkommen können. In diesem Fall ist es möglich, dass eine bitweise Operation mit zwei gültigen Operanden dieses Muster und damit ein ungültiges Ergebnis erzeugt.

Question 4

(Dieser Beitrag gilt für C, nicht C++)

Die bitweisen Operatoren können keine Trap-Darstellung durch das Setzen ungültiger Füllbits verursachen, siehe C11 6.2.6.2/1 Fußnote:

…keine arithmetische Operation auf gültige Werte kann eine Trap-Darstellung erzeugen…

(Die Bedeutung von “arithmetische Operation” ist unklar, aber der Index verweist auf 6.5.11, was die Definition von XOR ist).

In C können sie jedoch a verursachen negative Null zu generieren. Im Zweierkomplement gibt es keine negative Null. Aber sagen Sie, Sie wären auf einem System mit 1er-Komplement, dann könnten Sie eine negative Null via erzeugen ^ und dies könnte eine Trap-Darstellung verursachen. 6.2.6.2/3 sagt ausdrücklich, dass dies möglich ist:

Wenn die Implementierung negative Nullen unterstützt, dürfen sie nur generiert werden durch:

— die Operatoren &, |, ^, ~, << und >> mit Operanden, die einen solchen Wert erzeugen;

Schließlich impliziert 6.2.6.2/2 (ich bin mir sowieso ziemlich sicher), dass es nicht möglich ist, eine Kombination von Wertbits zu haben, die eine Ganzzahlüberschreitung darstellen würde INT_MAX

Zusammenfassend sind die möglichen Ergebnisse von ^ auf zwei ints sind:

Ein weiterer gültiger int Wert (möglicherweise mit anderen, aber nicht abfangenden Füllbits zu anderen Versionen desselben Werts)
Eine negative Null, die eine Falle verursachen kann oder nicht

Question 5

Genau genommen können Sie zwei Ganzzahlen nicht XORn. Sie können zwei Beutel mit Bits in ganzzahliger Größe XOR-verknüpfen, und Sie können diese Beutel mit Bits zu anderen Zeiten als ganze Zahlen behandeln. Sie können sie sogar als ganze Zahlen behandeln alle anderen Zeiten.

Aber in dem Moment, in dem Sie die XOR-Operation ausführen, behandeln Sie sie als etwas ganz anderes als ganze Zahlen oder sogar Zahlen. an sich: Sie sind nur zwei Bitfolgen, bei denen entsprechende Bits verglichen werden. Das Konzept des Überlaufs trifft darauf nicht zu, und wenn Sie sich dann entscheiden, das Ergebnis als Ganzzahl zu behandeln, kann es auch nicht überlaufen.

Question 6

Ist es überhaupt möglich, dass XOR einen so großen ganzzahligen Wert generiert, der nicht im int-Typ gespeichert werden kann?

Wenn die Operanden sind intdann nein.

Wenn es nicht möglich ist, dass dies passieren kann, gibt es dann einen Beweis dafür?

Nun, es ist von der Definition her trivial. Dies ist kaum ein mathematisch strenger Beweis, aber Sie könnten bedenken, dass ein Bit in der Ausgabe von XOR nur dann 1 ist, wenn einer der Operanden 1 an dieser Position hat. Da ein Bereichsüberschreitungsbit in den Operanden nicht 1 sein kann, gibt es kein Ausgangsbit mit dem Wert 1, das außerhalb des Bereichs liegt.

Question 7

XOR, AND, OR, NOT und alle anderen bitweisen Operatoren erzeugen bitweise Ergebnisse, wobei die Bits im Ergebnis aus den Bits an genau derselben Position in den Eingängen kombiniert werden. n-Bit-Eingänge erzeugen also n-Bit ohne höheres Bit. Wie kann es also außerhalb der Grenzen liegen?

Question 8

Nein, ich kann nicht. Im Gegensatz zu anderen Antworten wäre meine ein mathematischer Beweis.

XOR ist Abkürzung für Exklusiv oder oder exklusive Disjunktion (⊕) und kann wie folgt definiert werden:

A ⊕ B = (A ∪ B)\(A ∩ B)

Ihr Vorschlag ist das

∃x: x ∉ A ∧ x ∉ B ∧ x ∈ (A ⊕ B)

Also aus der ersten Gleichung

x ∈ (A ∪ B)\(A ∩ B)

Was kann ausgedrückt werden als

x ∈ (A ∪ B) ∧ x ∉ (A ∩ B)

Der zweite Teil kann wie folgt ausgedrückt werden:

x ∉ A ∧ x ∉ B

Der erste Teil kann wie folgt ausgedrückt werden:

x ∈ A ∨ x ∈ B

Was kollidieren mit unserer Annahme, dass x ∉ A ∧ x ∉ B also ist die Proposition für jede Menge falsch A und B.

QED