fórmula directa para sumar XOR

Question

tengo que XOR números de 1 a N, ¿existe una fórmula directa para ello?

Por ejemplo, si N = 6 entonces 1^2^3^4^5^6 = 7 Quiero hacerlo sin utilizar ningún bucle así que necesito un O (1) fórmula (si los hay)

Answer 1

Prueba esto:

el LSB obtiene toggled cada vez que el N es impar, por lo que podemos decir que

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

El mismo patrón se puede observar para el resto de los bits. Cada vez que los bits de B y B+1 (a partir de LSB) en N será diferente, el bit B en el resultado se debe establecer.

Por lo tanto, el resultado final será (incluyendo N): rez = N^(N >> 1)

Edit: Lo siento, no era correcto. la respuesta correcta:

para n impar: rez = (N^(N >> 1)) & 1

incluso para N: rez = (N & ~1) | ((N^(N >> 1)) & 1)

Answer 2

edición
GSerg ha publicado una fórmula sin bucles, pero eliminado por alguna razón (sin borrar ahora) La fórmula es perfectamente válida (aparte de un pequeño error). Aquí está la versión similar a C++.

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

Uno puede demostrar por inducción, la comprobación de todos los recordatorios de la división por 4. Sin embargo, no tiene idea de cómo se puede lograr sin generar resultados y ver la regularidad.

Por favor explique su enfoque un poco más.
Dado que cada bit es independiente en funcionamiento xor, puede calcularlos por separado.
Además, si nos fijamos en el bit k-ésimo número de 0..n, que va a formar un patrón. Por ejemplo, números del 0 al 7 en forma binaria.

000 
001 
010 
011 
100 
101 
110 
111 

se ve que para el bit de orden k (k comienza en 0), hay 2^k ceros, 2^k los ceros, entonces 2^k otra vez, etc.
Por lo tanto, se puede para cada bit calcular cuántos los hay sin pasar realmente todos los números del 1 al n.

P. ej., Para k = 2, hay bloques repetidos de 2^2 == 4 ceros y unos. Entonces,

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

Answer 3

permite decir que la función XOR todos los valores de 1 a N ser XOR (N), entonces

 
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 

espero que puedan ver el patrón. Debería ser similar para otros números también.

Answer 4

Para impar N, el resultado es o bien 1 o 0 (cíclico, 0 para N=3, 1 para N=5, 0 para N=7 etc.)

Para aún N, el resultado es o bien N o N+1 (cíclico, N + 1 para N=2, N para N=4, N + 1 para N=6, N para N=8, etc.).

Pseudocódigo:

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

Su fórmula es 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; 
} 

de salida:

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 

Explicación:

1. El bit bajo es XOR entre bit bajo y bit siguiente.

2. Para cada bit excepto bajo bit se cumple lo siguiente:

   • si N es impar entonces ese bit es 0.
   • si N es par entonces que bit es igual a poco correspondido de N.

Así, para el caso de impar N el resultado siempre es 0 o 1.

Answer 6

Great answe ¡por Alexey Malistov! Una variación de su fórmula: n & 1 ? (n & 2) >> 1^1 : n | (n & 2) >> 1 o equivalente n & 1 ? !(n & 2) : n | (n & 2) >> 1.

Answer 7

este método evita el uso de los condicionales F(N)=(N&((N&1)-1))|((N&1)^((N&3)>>1)

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

Si nos fijamos en el XOR de los primeros números que se obtiene:

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

Con suerte se observa el patrón:

si N mod 4 = 1 que F(N)=1
si N mod 4 = 3 que F(N)=0
si N mod 4 = 0 que F(N)=N
si N mod 4 = 2 que F(N)=N pero con el primer bit como 1 por lo N|1

la parte difícil es conseguir esto en una declaración sin condicionales enferma explicar la lógica Solía para hacer esto.

dar los primeros 2 bits significativos de N llamarlos:

b0 y b1 y éstos se obtienen con:

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

Tenga en cuenta que si b0 == 1 tenemos que 0 todos los bits, pero si no todos los bits excepto el primer bit permanecen igual. Podemos hacer este comportamiento:

N & (b0-1): esto funciona porque de complemento a 2, -1 es igual a un número con todos los bits puestos a 1 y 1-1=0 así que cuando b0=1 esto se traduce en F(N)=0 .. por lo que es la primera parte de la función:

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

ahora esto funcionará para N mod 4 == 3 para 0 y, para los otros 2 casos permite mirar únicamente a b1, b0 y F(N)0:

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

Bueno, con suerte esta tabla de verdad parece familiar! es b0 XOR b1 (b1^b0). Así que ahora que sabemos cómo sacar el último bit dejar que poner eso en nuestra función:

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

y ahí lo tienes, una función sin necesidad de utilizar los condicionales. también esto es útil si desea calcular el XOR a partir de los números positivos a a b. usted puede hacer: F(a) XOR F(b).

Answer 8

Echa un vistazo a esto. Esto resolverá su problema.

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

Para calcular la suma XOR de 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 el cambio mínimo a la lógica original:

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

podemos tener:

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

Tiene un bucle pero llevaría un tiempo constante ejecutarlo. El número de veces que iteramos a través del for-loop variaría entre 1 y 4.

Answer 10

¿Qué tal esto?

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

Answer 11

Si todavía alguien lo necesita solución pitón aquí simple:

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

Esto funciona bien sin ningún problema para cualquier 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; 
}