¿Cómo funciona el intercambio de variables XOR?

Question

¿Puede alguien explicarme cómo funciona el intercambio XOR de dos variables sin variable temporal?

void xorSwap (int *x, int *y) 
{ 
    if (x != y) { 
     *x ^= *y; 
     *y ^= *x; 
     *x ^= *y; 
    } 
} 

Entiendo QUÉ hace, pero ¿alguien me puede guiar por la lógica de cómo funciona?

Answer 1

Puede ver cómo funciona haciendo la sustitución:

x1 = x0 xor y0 
y2 = x1 xor y0 
x2 = x1 xor y2 

Sustituyendo,

x1 = x0 xor y0 
y2 = (x0 xor y0) xor y0 
x2 = (x0 xor y0) xor ((x0 xor y0) xor y0) 

Debido XOR es totalmente asociativa y conmutativa:

y2 = x0 xor (y0 xor y0) 
x2 = (x0 xor x0) xor (y0 xor y0) xor y0 

Desde x xor x == 0 para cualquier x,

y2 = x0 xor 0 
x2 = 0 xor 0 xor y0 

Y puesto x xor 0 == x para cualquier x,

y2 = x0 
x2 = y0 

Y el canje se hace.

Answer 2

mayoría de la gente intercambiar dos variables x e y utilizando una variable temporal, como este:

tmp = x 
x = y 
y = tmp 

He aquí un truco de programación ordenada para intercambiar dos valores sin necesidad de un temp:

x = x xor y 
y = x xor y 
x = x xor y 

Más detalles en Swap two variables using XOR

En la línea 1, combinamos x e y (usando XOR) para obtener este "hybri" d "y lo almacenamos en x. XOR es una excelente manera de guardar información, ya que puede eliminarla haciendo un XOR nuevamente.

En la línea 2. Nosotros XOR el híbrido con y, que cancela toda la información, dejándonos solo con x. Guardamos este resultado nuevamente en y, por lo que ahora se han intercambiado.

En la última línea, x todavía tiene el valor híbrido. Lo XOR una vez más con y (ahora con el valor original de x) para eliminar todos los rastros de x fuera del híbrido. ¡Esto nos deja con y, y el intercambio está completo!

---

El equipo tiene en realidad una implícita “temp” variable que almacena los resultados intermedios antes de escribirlos de nuevo a un registro. Por ejemplo, si se agrega 3 a un registro (en pseudocódigo en lenguaje de máquina):

ADD 3 A // add 3 to register A 

La ALU (unidad aritmética lógica) es en realidad lo que ejecuta la instrucción 3 + A. Toma las entradas (3, A) y crea un resultado (3 + A), que luego la CPU vuelve a almacenar en el registro original de A. Entonces, utilizamos la ALU como espacio temporal temporal antes de obtener la respuesta final.

Damos por hecho los datos temporales implícitos de la ALU, pero siempre están ahí. De forma similar, la ALU puede devolver el resultado intermedio del XOR en el caso de x = xx o y, en ese punto la CPU lo almacena en el registro original de x.

Como no estamos acostumbrados a pensar en la ALU descuidada y descuidada, el intercambio XOR parece mágico porque no tiene una variable temporal explícita. Algunas máquinas tienen una instrucción XCHG de intercambio de 1 paso para intercambiar dos registros.

Answer 3

Aquí hay una que debe ser un poco más fácil de asimilar:

int x = 10, y = 7; 

y = x + y; //x = 10, y = 17 
x = y - x; //x = 7, y = 17 
y = y - x; //x = 7, y = 10 

Ahora, uno puede entender el XOR engañar un poco más fácil de entender que ^ puede ser pensado como +o-. Así como:

x + y - ((x + y) - x) == x 

, por lo que:

x^y^((x^y)^x) == x 

Answer 4

Otras personas lo han explicado, ahora quiero explicar por qué era una buena idea, pero ahora no lo es.

En la época en que teníamos CPU simples de ciclo único o multiciclo, era más barato usar este truco para evitar las costosas desreferencias de memoria o el derrame de registros en la pila. Sin embargo, ahora tenemos CPU con tuberías masivas en su lugar. La cartera de P4 varió de 20 a 31 (más o menos) etapas en sus tuberías, donde cualquier dependencia entre leer y escribir en un registro podría hacer que todo se estanque. El intercambio xor tiene algunas dependencias muy pesadas entre A y B que en realidad no importan pero que detienen la tubería en la práctica. Una tubería estancada causa una ruta de código lenta, y si este intercambio está en su bucle interno, se moverá muy lentamente.

En general, su compilador puede averiguar lo que realmente quiere hacer cuando realiza un intercambio con una variable de temperatura y puede compilarlo en una sola instrucción XCHG. Usar el intercambio xor hace que sea mucho más difícil para el compilador adivinar su intento y, por lo tanto, es mucho menos probable que lo optimice correctamente. Sin mencionar mantenimiento de código, etc.

Answer 5

@VonC lo tiene claro, es un truco matemático. Imagine palabras de 4 bits y vea si esto ayuda.

word1 ^= word2; 
word2 ^= word1; 
word1 ^= word2; 


word1 word2 
0101  1111 
after 1st xor 
1010  1111 
after 2nd xor 
1010  0101 
after 3rd xor 
1111  0101 

Answer 6

Básicamente hay 3 pasos en el enfoque XOR:

A '= un XOR b (1)
b' = a' XOR b (2)
un”= a' XOR b'(3)

Para entender por qué esto funciona primera nota que:

1. XOR producirá un 1 solo si uno de sus operandos es 1 y el otro es cero;
2. XOR es conmutativa por lo que a XOR b = b XOR a;
3. XOR es asociativo tan (a XOR b) XOR c = a XOR (b XOR c); y
4. un XOR a = 0 (esto debería ser obvio a partir de la definición en 1 anteriormente)

después del paso (1), la representación binaria de un tendrá bits 1 sólo en las posiciones de bit donde una yb tienen bits opuestos. Eso es cualquiera (ak = 1, bk = 0) o (ak = 0, bk = 1). Ahora cuando hacemos la sustitución en la Etapa (2), obtenemos:

b'= (a b XOR) XOR b
= a XOR (b XOR b) porque XOR es asociativa
= a XOR 0 debido [4] anterior
= a debido a la definición de XOR (ver 1 arriba)

Ahora podemos sustituir en la Etapa (3):

a”= (a XOR b) XOR un
= (b XOR a) XOR a porque XOR es comm utative
= b XOR (a XOR a) porque XOR es asociativa
= b XOR 0 debido a [4] anteriormente
= b debido a la definición de XOR (ver 1 anteriormente)

información más detallada aquí : Necessary and Sufficient

Answer 7

La razón por la que funciona es porque XOR no pierde información. Podrías hacer lo mismo con las sumas y restas ordinarias si pudieras ignorar el desbordamiento. Por ejemplo, si el par de variables A, B contiene inicialmente los valores de 1,2, se puede intercambiarlos como esto:

// A,B = 1,2 
A = A+B // 3,2 
B = A-B // 3,1 
A = A-B // 2,1 

Por cierto hay un viejo truco para codificar una lista enlazada de 2 vías en un solo puntero" ". Suponga que tiene una lista de bloques de memoria en las direcciones A, B y C. La primera palabra de cada bloque es, respectivamente:

// first word of each block is sum of addresses of prior and next block 
0 + &B // first word of block A 
&A + &C // first word of block B 
&B + 0 // first word of block C 

Si tiene acceso al bloque A, se le da la dirección de B Para llegar a C, toma el "puntero" en B y resta A, y así sucesivamente. Funciona igual de bien al revés. Para ejecutar a lo largo de la lista, debe mantener los punteros en dos bloques consecutivos.Por supuesto, usaría XOR en lugar de sumar/sumar, por lo que no tendría que preocuparse por el desbordamiento.

Puede ampliar esto a una "web vinculada" si desea divertirse.

Answer 8

Como nota al margen reinventé esta rueda hace de forma independiente desde hace varios años en forma de números enteros intercambiando haciendo:

a = a + b 
b = a - b (= a + b - b once expanded) 
a = a - b (= a + b - a once expanded). 

(Esto se menciona anteriormente, en un difícil de leer cierto),

El exactamente el mismo razonamiento se aplica a xor swaps: a^b^b = a y a^b^a = a. Desde XOR es conmutativa, x^x = 0 y x^0 = x, esto es bastante fácil de ver desde

= a^b^b 
= a^0 
= a 

y

= a^b^a 
= a^a^b 
= 0^b 
= b 

Espero que esto ayude. Esta explicación ya ha sido dada ... pero no muy claramente.

Answer 9

Me gusta pensar en ella gráficamente en lugar de numéricamente.

Digamos que usted comienza con x = 11 ey = 5 en binario (y voy a utilizar una máquina hipotética de 4 bits), aquí está xey

 x: |1|0|1|1| -> 8 + 2 + 1 
     y: |0|1|0|1| -> 4 + 1 

Ahora para mí, XOR es una operación de inversión y hacerlo dos veces es un espejo:

 x^y: |1|1|1|0| 
(x^y)^y: |1|0|1|1| <- ooh! Check it out - x came back 
(x^y)^x: |0|1|0|1| <- ooh! y came back too!