Formula diretta per sommare XOR

Question

Ho numeri XOR da 1 a N, esiste una formula diretta per questo?

Per esempio, se N = 6 poi 1^2^3^4^5^6 = 7 voglio farlo senza utilizzare alcun ciclo quindi ho bisogno di un O (1) formula (se presente)

Answer 1

Prova questo:

LSB viene commutato ogni volta che il N è dispari, quindi possiamo dire che

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

Lo stesso modello può essere osservato per il resto dei bit. Ogni volta che i bit B e B+1 (a partire da LSB) in N saranno diversi, il bit B nel risultato deve essere impostato.

Quindi, il risultato finale sarà (tra cui N): rez = N^(N >> 1)

EDIT: mi dispiace, era sbagliato. la risposta corretta:

per N dispari: rez = (N^(N >> 1)) & 1

anche per N: rez = (N & ~1) | ((N^(N >> 1)) & 1)

Answer 2

modificare
GSerg ha pubblicato una formula senza loop, ma eliminato per qualche motivo (non cancellato ora). La formula è perfettamente valida (a parte un piccolo errore). Ecco la versione simile a C++.

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

Si può dimostrare per induzione, controllando tutti i promemoria di divisione per 4. Anche se, non ho idea di come si possa arrivare senza generare output e vedere regolarità.

Per favore spiega il tuo approccio un po 'di più.
Poiché ciascun bit è indipendente nell'operazione xor, è possibile calcolarli separatamente.
Inoltre, se si guarda il bit k-th del numero 0..n, verrà creato un modello. Ad esempio, numeri da 0 a 7 in forma binaria.

000 
001 
010 
011 
100 
101 
110 
111 

si vede che per il bit k-esimo (k parte da 0), ci sei zeri, 2^k2^k quelli, poi 2^k zeri di nuovo, ecc
Pertanto, è possibile per ogni bit di calcolare quanti quelli che ci sono senza realmente passare attraverso tutti i numeri da 1 a n.

Ad es., Per k = 2, ci sono blocchi ripetuti di zero 2^2 == 4 e uno. Poi,

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

Answer 3

Diciamo la funzione che XOR tutti i valori da 1 a N essere XOR (N), quindi

 
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 

spero che si può vedere il modello. Dovrebbe essere simile anche per altri numeri.

Answer 4

Per dispari N, il risultato è 1 o 0 (ciclico, 0 per N=3, 1 per N=5, 0 per N=7 ecc)

Per ancor N, il risultato è N o N+1 (ciclico, N + 1 per N=2, N per N=4, N + 1 per N=6, N per N=8 ecc.).

Pseudocodice:

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 

Answer 5

La formula è 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; 
} 

uscita:

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 

Spiegazione:

1. Il bit basso è XOR tra bit basso e bit successivo.

2. Per ogni bit tranne basso bit vale quanto segue:

   • se N è dispari, allora quel bit è 0.
   • se N è pari allora che bit è uguale al bit corrisposto di N.

Così, per il caso di N dispari il risultato è sempre 0 o 1.

Answer 6

Grande answe di Alexey Malistov! Una variante della sua formula: n & 1 ? (n & 2) >> 1^1 : n | (n & 2) >> 1 o equivalente n & 1 ? !(n & 2) : n | (n & 2) >> 1.

Answer 7

questo metodo evita di usare i condizionali F(N)=(N&((N&1)-1))|((N&1)^((N&3)>>1)

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

Se si guarda lo XOR dei primi numeri si ottiene:

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

Speriamo che si nota il modello:

se N mod 4 = 1 di F(N)=1
se N mod 4 = 3 di F(N)=0
se N mod 4 = 0 di F(N)=N
se N mod 4 = 2 di F(N)=N ma con il primo bit come 1 così N|1

la parte difficile è sempre presente in una dichiarazione, senza condizionali malato spiegare la logica che ho usato per fare questo.

prendere i primi 2 bit significativi di N chiamarli:

b0 e b1 e questi si ottengono con:

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

noti che se b0 == 1 dobbiamo 0 tutti i bit, ma se non sono tutti i bit tranne il primo bit rimangono gli stessi. Possiamo fare questo comportamento:

N & (b0-1): questo funziona a causa di complemento a 2, -1 è uguale a un numero con tutti i bit impostati a 1 e 1-1=0 così quando b0=1 questo si traduce in F(N)=0 .. in modo che sia la prima parte del la funzione:

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

ora questo lavoro per per N mod 4 == 3 e 0, per gli altri 2 casi consente di guardare esclusivamente a b1, b0 e F(N)0:

0.123.516,410617 millions

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

Ok speriamo che questo tavolo della verità sembri familiare! è b0 XOR b1 (b1^b0). così ora che sappiamo come ottenere l'ultimo bit lasciare messo sulla nostra funzione:

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

e ci si va, una funzione senza usare condizionali. anche questo è utile se vuoi calcolare lo XOR da numeri positivi da a a b. puoi fare: F(a) XOR F(b).

Answer 8

Dai un'occhiata a questo. Questo risolverà il tuo problema.

https://stackoverflow.com/a/10670524/4973570

Per calcolare la somma XOR da 1 a N:

int ans,mod=N%4; 
if(mod==0) ans=N; 
else if(mod==1) ans=1; 
else if(mod==2) ans=N+1; 
else if(mod==3) ans=0; 

Answer 9

Con il cambiamento minima per la logica originale:

int xor = 0; 
for (int i = 1; i <= N; i++) { 
    xor ^= i; 
} 

possiamo avere:

int xor = 0; 
for (int i = N - (N % 4); i <= N; i++) { 
    xor ^= i; 
} 

Ha un ciclo ma ci vorrebbe un tempo costante per l'esecuzione. Il numero di volte che iteriamo attraverso il ciclo for varia tra 1 e 4.

Answer 10

Che ne dici di questo?

!(n&1)*n+(n%4&n%4<3) 

Answer 11

Se ancora qualcuno ne ha bisogno qui soluzione semplice pitone:

def XorSum(L): 
    res = 0   
    if (L-1)%4 == 0: 
     res = L-1 
    elif (L-1)%4 == 1: 
     res = 1 
    elif (L-1)%4 == 2: 
     res = (L-1)^1 
    else: #3 
     res= 0 
    return res 

Answer 12

Questo funziona bene, senza problemi per ogni n;

int xorn(int n) 
{ 

    if (n % 4 == 0) 
     return n; 
    else if(n % 4 == 1) 
     return 1; 
    else if(n % 4 == 2) 
     return n+1; 
    else 
     return 0; 
}