¿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 lo que hace, pero ¿alguien puede guiarme a través de la lógica de cómo funciona?

Answer 1

Puedes 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)

Porque xor es totalmente asociativo y conmutativo:

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

Dado que x xor x == 0 para cualquier x,

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

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

y2 = x0
x2 = y0

Y el intercambio está hecho.

Answer 2

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

En la época en que teníamos CPU simples de un solo ciclo o de varios ciclos, era más barato usar este truco para evitar costosas desreferencias de memoria o derramar registros en la pila. Sin embargo, ahora tenemos CPU con tuberías masivas en su lugar. La tubería del P4 varió desde tener 20 a 31 (más o menos) etapas en sus tuberías, donde cualquier dependencia entre la lectura y la escritura en un registro podría hacer que todo se paralizara. El intercambio xor tiene algunas dependencias muy pesadas entre A y B que en realidad no importan en absoluto, sino que paralizan 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 la práctica general, su compilador puede averiguar qué es lo que realmente quiere hacer cuando hace un intercambio con una variable temporal y puede compilarlo en una sola instrucción XCHG. El uso del intercambio xor hace que sea mucho más difícil para el compilador adivinar su intención y, por lo tanto, es mucho menos probable que lo optimice correctamente. Sin mencionar el mantenimiento del código, etc.

Answer 3

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

Digamos que comienzas con x = 11 e y = 5 En binario (y voy a usar una máquina hipotética de 4 bits), aquí están x e y

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

Ahora, para mí, XOR es una operación invertida 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!

Answer 4

Aquí hay uno que debería 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 truco de XOR un poco más fácilmente entendiendo que ^ puede pensarse como + o - . Así como:

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

, entonces:

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

Answer 5

La razón por la que funciona es porque XOR no pierde información. Podría hacer lo mismo con sumas y restas ordinarias si pudiera ignorar el desbordamiento. Por ejemplo, si el par de variables A, B originalmente contiene los valores 1,2, podría intercambiarlos de esta manera:

 // 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 bidireccional en un solo " puntero " ;. Supongamos que tiene una lista de bloques de memoria en las direcciones A, B y C. La primera palabra en 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 tienes acceso al bloque A, te da la dirección de B. Para llegar a C, toma el " puntero " en B y restar A, y así sucesivamente. Funciona igual de bien al revés. Para seguir la lista, debe mantener los punteros en dos bloques consecutivos. Por supuesto, usaría XOR en lugar de agregar / restar, por lo que no tendría que preocuparse por el desbordamiento.

Puede extender esto a una "web vinculada" si quisieras divertirte un poco.

Answer 6

La mayoría de las personas intercambiarían dos variables x y y usando una variable temporal, como esta:

tmp = x
x = y
y = tmp

Aquí hay un buen truco de programación para intercambiar dos valores sin necesidad de una temperatura:

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

Más detalles en Intercambiar dos variables usando XOR

  

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

     

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

     

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

---

  

La computadora realmente tiene una variable "temporal" implícita que almacena resultados intermedios antes de volver a escribirlos en un registro. Por ejemplo, si agrega 3 a un registro (en pseudocódigo en lenguaje de máquina):

ADD 3 A // add 3 to register A

  

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

     

Damos por sentado los datos temporales implícitos de la ALU, pero siempre están ahí. De manera similar, la ALU puede devolver el resultado intermedio de XOR en el caso de x = x xor y, en cuyo punto la CPU lo almacena en el registro original de x.

     

Debido a que no estamos acostumbrados a pensar en la ALU pobre 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 7

@VonC tiene razón, es un buen 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 8

Básicamente, hay 3 pasos en el enfoque XOR:

a ’= a XOR b (1)
b ’= a’ XOR b (2)
a "= a 'XOR b' (3)

Para entender por qué esto funciona primero, tenga en cuenta que:

1. XOR producirá un 1 solo si exactamente uno de sus operandos es 1, y el otro es cero;
2. XOR es conmutativo por lo tanto, un XOR b = b XOR a;
3. XOR es asociativo , entonces (a XOR b) XOR c = a XOR (b XOR c); y
4. a XOR a = 0 (esto debería ser obvio por la definición en 1 arriba)

Después del Paso (1), la representación binaria de a tendrá 1 bits solo en las posiciones de bit donde a y b tienen bits opuestos. Es decir (ak = 1, bk = 0) o (ak = 0, bk = 1). Ahora cuando hacemos la sustitución en el Paso (2) obtenemos:

b ’= (a XOR b) XOR b
    = a XOR (b XOR b) porque XOR es asociativo
   = a XOR 0 debido a [4] arriba
   = a debido a la definición de XOR (consulte 1 arriba)

Ahora podemos sustituirlo en el Paso (3):

a ”= (a XOR b) XOR a
    = (b XOR a) XOR a porque XOR es conmutativo
    = b XOR (a XOR a) porque XOR es asociativo
    = b XOR 0 debido a [4] arriba
    = b debido a la definición de XOR (consulte 1 arriba)

Información más detallada aquí: Necesario y suficiente

Answer 9

Como nota al margen, reinventé esta rueda de forma independiente hace varios años en la forma de intercambiar enteros haciendo:

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

(Esto se menciona anteriormente de una manera difícil de leer),

El mismo razonamiento se aplica exactamente a los intercambios xor: a ^ b ^ b = a y a ^ b ^ a = a. Como xor es conmutativo, x ^ x = 0 y x ^ 0 = x, esto es bastante fácil de ver ya que

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

y

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

Espero que esto ayude. Esta explicación ya se ha dado ... pero no es muy clara en mi opinión.