Direkte Formel zum Summieren von XOR

Ich muss XOR-Zahlen von 1 bis N, gibt es eine direkte Formel dafür?

Zum Beispiel wenn N = 6 dann 1^2^3^4^5^6 = 7 Ich möchte es tun, ohne eine Schleife zu verwenden, also brauche ich eine O (1) -Formel (falls vorhanden)

Deine Formel ist N & (N % 2 ? 0 : ~0) | ( ((N & 2)>>1) ^ (N & 1) ):

int main()
{
    int S = 0;
    for (int N = 0; N < 50; ++N) {
        S = (S^N);
        int check = N & (N % 2 ? 0 : ~0) | ( ((N & 2)>>1) ^ (N & 1) );
        std::cout << "N = " << N << ": "  << S << ", " << check << std::endl;
        if (check != S) throw;
    }

    return 0;
}

Ausgabe:

N = 0: 0, 0             N = 1: 1, 1             N = 2: 3, 3
N = 3: 0, 0             N = 4: 4, 4             N = 5: 1, 1
N = 6: 7, 7             N = 7: 0, 0             N = 8: 8, 8
N = 9: 1, 1             N = 10: 11, 11          N = 11: 0, 0
N = 12: 12, 12          N = 13: 1, 1            N = 14: 15, 15
N = 15: 0, 0            N = 16: 16, 16          N = 17: 1, 1
N = 18: 19, 19          N = 19: 0, 0            N = 20: 20, 20
N = 21: 1, 1            N = 22: 23, 23          N = 23: 0, 0
N = 24: 24, 24          N = 25: 1, 1            N = 26: 27, 27
N = 27: 0, 0            N = 28: 28, 28          N = 29: 1, 1
N = 30: 31, 31          N = 31: 0, 0            N = 32: 32, 32
N = 33: 1, 1            N = 34: 35, 35          N = 35: 0, 0
N = 36: 36, 36          N = 37: 1, 1            N = 38: 39, 39
N = 39: 0, 0            N = 40: 40, 40          N = 41: 1, 1
N = 42: 43, 43          N = 43: 0, 0            N = 44: 44, 44
N = 45: 1, 1            N = 46: 47, 47          N = 47: 0, 0
N = 48: 48, 48          N = 49: 1, 1            N = 50: 51, 51

Erläuterung:

1. Low-Bit ist XOR zwischen Low-Bit und nächstem Bit.

2. Für jedes Bit außer Low-Bit gilt:

   • wenn N ungerade ist, dann ist dieses Bit 0.
   • wenn N gerade ist, dann ist dieses Bit gleich dem entsprechenden Bit von N.

Für den Fall von ungeradem N ist das Ergebnis also immer 0 oder 1.

bearbeiten
GSerg Hat eine Formel ohne Schleifen gepostet, aber aus irgendeinem Grund gelöscht (jetzt nicht gelöscht). Die Formel ist vollkommen gültig (abgesehen von einem kleinen Fehler). Hier ist die C++-ähnliche Version.

if n % 2 == 1 {
    result = (n % 4 == 1) ? 1 : 0;
} else {
    result = (n % 4 == 0) ? n : n + 1;
}

Man kann es durch Induktion beweisen, indem man alle Erinnerungen an die Division durch überprüft 4. Obwohl, keine Ahnung, wie Sie darauf kommen können, ohne Ausgabe zu erzeugen und Regelmäßigkeit zu sehen.

Bitte erläutern Sie Ihre Vorgehensweise etwas genauer.

Da bei der xor-Operation jedes Bit unabhängig ist, können Sie sie separat berechnen.
Auch, wenn Sie sich das k-te Bit der Zahl ansehen 0..n, es wird ein Muster bilden. ZB Zahlen von 0 bis 7 in binärer Form.

000
001
010
011
100
101
110
111

Sie sehen, dass es für das k-te Bit (k beginnt bei 0) gibt 2^k Nullen, 2^k diejenigen, dann 2^k wieder Nullen usw.
Daher können Sie für jedes Bit berechnen, wie viele Einsen es gibt, ohne tatsächlich alle Zahlen von 1 bis n durchzugehen.

Bsp. für k = 2es gibt wiederholte Blöcke von 2^2 == 4 Nullen und Einsen. Dann,

int ones = (n / 8) * 4; // full blocks
if (n % 8 >= 4) { // consider incomplete blocks in the end
    ones += n % 8 - 3;
}

Für ungerade Ndas Ergebnis ist entweder 1 oder 0 (zyklisch, 0 für N=31 für N=50 für N=7 etc.)

Für sogar Ndas Ergebnis ist entweder N oder N+1 (zyklisch, N+1 für N=2N für N=4N+1 für N=6N für N=8 etc).

Pseudocode:

if (N mod 2) = 0
  if (N mod 4) = 0 then r = N else r = N+1
else
  if (N mod 4) = 1 then r = 1 else r = 0

Nehmen wir an, die Funktion, die alle Werte von 1 bis N XOR-verknüpft, ist dann XOR(N).

XOR(1) = 000 1 = 0 1 ( The 0 is the dec of bin 000)
XOR(2) = 001 1 = 1 1
XOR(3) = 000 0 = 0 0
XOR(4) = 010 0 = 2 0
XOR(5) = 000 1 = 0 1 
XOR(6) = 011 1 = 3 1
XOR(7) = 000 0 = 0 0
XOR(8) = 100 0 = 4 0
XOR(9) = 000 1 = 0 1
XOR(10)= 101 1 = 5 1
XOR(11)= 000 0 = 0 0
XOR(12)= 110 0 = 6 0

Ich hoffe, Sie können das Muster erkennen. Es sollte auch für andere Nummern ähnlich sein.

Versuche dies:

Das LSB wird jedes Mal umgeschaltet, wenn das N ungerade ist, also können wir das sagen

 rez & 1 == (N & 1) ^ ((N >> 1) & 1)

Das gleiche Muster kann für die restlichen Bits beobachtet werden. Jedes Mal die Bits B und B+1 (ab LSB) ein N wird anders sein, bisschen B im Ergebnis gesetzt werden soll.

Das Endergebnis lautet also (einschließlich N): rez = N ^ (N >> 1)

EDIT: Entschuldigung, es war falsch. die richtige Antwort:

für ungerade N: rez = (N ^ (N >> 1)) & 1

für gerade N: rez = (N & ~1) | ((N ^ (N >> 1)) & 1)

Tolle Antwort von Alexey Malistov! Eine Variation seiner Formel: n & 1 ? (n & 2) >> 1 ^ 1 : n | (n & 2) >> 1 oder gleichwertig n & 1 ? !(n & 2) : n | (n & 2) >> 1.

Diese Methode vermeidet die Verwendung von Bedingungen F(N)=(N&((N&1)-1))|((N&1)^((N&3)>>1)

F(N)= (N&(b0-1)) | (b0^b1)

Wenn Sie sich das XOR der ersten paar Zahlen ansehen, erhalten Sie:

N     |  F(N)
------+------
0001  |  0001
0010  |  0011
0011  |  0000
0100  |  0100
0101  |  0001
0110  |  0111
0111  |  0000
1000  |  1000
1001  |  0001

Hoffentlich erkennen Sie das Muster:

wenn N mod 4 = 1 als F(N)=1

wenn N mod 4 = 3 als F(N)=0

wenn N mod 4 = 0 als F(N)=N

wenn N mod 4 = 2 als F(N)=N aber mit dem ersten bisschen wie 1 Also N|1

Der knifflige Teil besteht darin, dies in einer Anweisung ohne Bedingungen zu erhalten, um die Logik zu erklären, mit der ich dies getan habe.

Nehmen Sie die ersten 2 signifikanten Bits von N, nennen Sie sie:

b0 und b1 und diese erhält man mit:

b0 = N&1
b1 = N&3>>1

Beachten Sie, dass wenn b0 == 1 wir müssen 0 alle Bits, aber wenn nicht, bleiben alle Bits mit Ausnahme des ersten Bits gleich. Wir können dieses Verhalten tun, indem wir:

N & (b0-1) : das funktioniert wegen dem 2er-Komplement, -1 ist gleich einer Zahl, bei der alle Bits auf gesetzt sind 1 und 1-1=0 also wann b0=1 das führt zu F(N)=0.. das ist also der erste Teil der Funktion:

F(N)= (N&(b0-1))...

jetzt wird dies für für funktionieren N mod 4 == 3 und 0für die anderen 2 Fälle schauen wir uns nur an b1, b0 und F(N)0:

b0|b1|F(N)0
--+--+-----
 1| 1|    0
 0| 0|    0
 1| 0|    1
 0| 1|    1

Ok, hoffentlich kommt dir diese Wahrheitstabelle bekannt vor! es ist b0 XOR b1 (b1^b0). Jetzt, da wir wissen, wie wir das letzte Bit bekommen, lassen Sie das auf unsere Funktion setzen:

F(N)=(N&(b0-1))|b0^b1

und los geht’s, eine Funktion ohne Verwendung von Bedingungen. Auch dies ist nützlich, wenn Sie das XOR von positiven Zahlen a bis b berechnen möchten. du kannst tun:
F(a) XOR F(b).