Sie erhalten einen großen Bereich [a, b], in dem 'a' und 'b' normalerweise zwischen 1 und 4.000.000.000 einschließlich liegen können. Sie müssen das XOR aller Zahlen im angegebenen Bereich ermitteln.

Dieses Problem wurde in TopCoder SRM verwendet. Ich habe eine der im Spiel eingereichten Lösungen gesehen und kann nicht herausfinden, wie sie funktioniert.

Könnte jemand helfen, die Gewinnerlösung zu erklären:

long long f(long long a) {
     long long res[] = {a,1,a+1,0};
     return res[a%4];
}

long long getXor(long long a, long long b) {
     return f(b)^f(a-1);
}

Hier getXor()ist die eigentliche Funktion zum Berechnen des xor aller Zahlen im übergebenen Bereich [a, b] und "f ()" ist eine Hilfsfunktion.

Dies ist eine ziemlich clevere Lösung - sie nutzt die Tatsache aus, dass die laufenden XORs ein Ergebnismuster aufweisen. Die f()Funktion berechnet den XOR-Gesamtlauf aus [0, a]. In dieser Tabelle finden Sie 4-Bit-Zahlen:

0000 <- 0  [a]
0001 <- 1  [1]
0010 <- 3  [a+1]
0011 <- 0  [0]
0100 <- 4  [a]
0101 <- 1  [1]
0110 <- 7  [a+1]
0111 <- 0  [0]
1000 <- 8  [a]
1001 <- 1  [1]
1010 <- 11 [a+1]
1011 <- 0  [0]
1100 <- 12 [a]
1101 <- 1  [1]
1110 <- 15 [a+1]
1111 <- 0  [0]

Dabei ist die erste Spalte die Binärdarstellung und dann das Dezimalergebnis und seine Beziehung zu seinem Index (a) in der XOR-Liste. Dies geschieht, weil alle oberen Bits alle 4 abgebrochen werden und die unteren zwei Bits alle 4 durchlaufen. So gelangen Sie zu dieser kleinen Nachschlagetabelle.

Betrachten Sie nun einen allgemeinen Bereich von [a, b]. Wir können verwenden f(), um das XOR für [0, a-1] und [0, b] zu finden. Da jeder Wert, den XOR mit sich selbst hat, Null ist, löscht das f(a-1)Just alle Werte im XOR-Lauf kleiner als aund lässt Sie mit dem XOR des Bereichs [a, b] zurück.

Neben der großartigen Antwort von FatalError return f(b)^f(a-1);könnte die Zeile besser erklärt werden. Kurz gesagt, weil XOR diese wunderbaren Eigenschaften hat:

• Es ist assoziativ - Platzieren Sie Klammern, wo immer Sie möchten
• Es ist kommutativ - das heißt, Sie können die Operatoren bewegen (sie können "pendeln").

Hier ist beides in Aktion:

(a ^ b ^ c) ^ (d ^ e ^ f) = (f ^ e) ^ (d ^ a ^ b) ^ c

• Es kehrt sich um

So was:

a ^ b = c
c ^ a = b

Addieren und multiplizieren sind zwei Beispiele für andere assoziative / kommutative Operatoren, die sich jedoch nicht umkehren. Ok, warum sind diese Eigenschaften wichtig? Ein einfacher Weg besteht darin, es auf das zu erweitern, was es wirklich ist, und dann können Sie diese Eigenschaften bei der Arbeit sehen.

Definieren wir zunächst, was wir wollen, und nennen es n:

n      = (a ^ a+1 ^ a+2 .. ^ b)

Wenn es hilft, denken Sie an XOR (^), als wäre es ein Add.

Definieren wir auch die Funktion:

f(b)   = 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ b

bist größer als a, also können wir auch Folgendes sagen, indem wir sicher ein paar zusätzliche Klammern einfügen (was wir können, weil es assoziativ ist):

f(b)   = ( 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ (a-1) ) ^ (a ^ a+1 ^ a+2 .. ^ b)

Was vereinfacht zu:

f(b)   = f(a-1) ^ (a ^ a+1 ^ a+2 .. ^ b)

f(b)   = f(a-1) ^ n

Als nächstes verwenden wir diese Umkehreigenschaft und Kommutivität, um uns die magische Linie zu geben:

n      = f(b) ^ f(a-1)

Wenn Sie XOR als Add betrachtet haben, hätten Sie dort einen Subtrahieren vorgenommen. XOR ist zu XOR, was addieren ist zu subtrahieren!

Wie komme ich selbst darauf?

Denken Sie an die Eigenschaften logischer Operatoren. Arbeiten Sie mit ihnen fast wie Addieren oder Multiplizieren, wenn es hilft. Es fühlt sich ungewöhnlich an, dass und (&), xor (^) und oder (|) assoziativ sind, aber sie sind!

Führen Sie zuerst die naive Implementierung durch, suchen Sie in der Ausgabe nach Mustern und suchen Sie dann nach Regeln, die bestätigen, dass das Muster wahr ist. Vereinfachen Sie Ihre Implementierung noch weiter und wiederholen Sie den Vorgang. Dies ist wahrscheinlich der Weg, den der ursprüngliche Ersteller eingeschlagen hat, was durch die Tatsache hervorgehoben wird, dass er nicht vollständig optimal ist (dh eine switch-Anweisung anstelle eines Arrays verwenden).

Ich fand heraus, dass der folgende Code auch wie die in der Frage angegebene Lösung funktioniert.

Vielleicht ist dies wenig optimiert, aber es ist genau das, was ich durch das Beobachten von Wiederholungen erhalten habe, wie in der akzeptierten Antwort angegeben.

Ich möchte den mathematischen Beweis hinter dem gegebenen Code kennen / verstehen, wie in der Antwort von @Luke Briggs erklärt

Hier ist dieser JAVA-Code

public int findXORofRange(int m, int n) {
    int[] patternTracker;

    if(m % 2 == 0)
        patternTracker = new int[] {n, 1, n^1, 0};
    else
        patternTracker = new int[] {m, m^n, m-1, (m-1)^n};

    return patternTracker[(n-m) % 4];
}

Ich habe das Problem mit der Rekursion gelöst. Ich teile den Datensatz einfach für jede Iteration in einen fast gleichen Teil.

public int recursion(int M, int N) {
    if (N - M == 1) {
        return M ^ N;
    } else {
        int pivot = this.calculatePivot(M, N);
        if (pivot + 1 == N) {
            return this.recursion(M, pivot) ^ N;
        } else {
            return this.recursion(M, pivot) ^ this.recursion(pivot + 1, N);
        }
    }
}
public int calculatePivot(int M, int N) {
    return (M + N) / 2;
}

Lassen Sie mich Ihre Gedanken über die Lösung wissen. Freut mich über Verbesserungsrückmeldungen. Die vorgeschlagene Lösung berechnet das XOR in der Komplexität 0 (log N).

Danke dir

Um XOR von 0 bis N zu unterstützen, musste der angegebene Code wie folgt geändert werden:

int f(int a) {
    int []res = {a, 1, a+1, 0};
    return res[a % 4];
}

int getXor(int a, int b) {
    return f(b) ^ f(a);
}