¿Cómo funciona el intercambio de variables XOR?

¿Alguien puede 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 puede explicarme la lógica de cómo funciona?

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)

Debido a que xor es completamente asociativo y conmutativo:

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

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

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

Y dado que x xor 0 == xpara cualquier x,

y2 = x0
x2 = y0

Y el intercambio está hecho.

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

En el día en que teníamos CPU simples de ciclo único o ciclo múltiple, 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 canalizaciones masivas. La tubería del P4 variaba 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 detuviera. El intercambio de xor tiene algunas dependencias muy importantes entre A y B que en realidad no importan en absoluto, pero paralizan la tubería en la práctica. Una tubería detenida provoca 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 realiza un intercambio con una variable temporal y puede compilarlo en una sola instrucción XCHG. El uso de xor swap hace que sea mucho más difícil para el compilador adivinar su intención y, por lo tanto, es mucho menos probable que la optimice correctamente. Sin mencionar el mantenimiento del código, etc.

Me gusta pensar en ello 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í tienes 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!

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 si comprende que ^ se puede pensar en + o - . Tal como:

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

, entonces:

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

La mayoría de las personas intercambiarían dos variables xey 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, porque puede eliminarla haciendo un XOR nuevamente.

En la línea 2. Hacemos XOR del híbrido con y, que cancela toda la información de y, 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. Hacemos XOR 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!

En realidad, la computadora tiene una variable “temporal” implícita que almacena los 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 Aritmética Lógica) es en realidad la 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. Entonces, usamos 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 del XOR en el caso de x = x xor y, momento en el que la CPU lo almacena en el registro original de x.

Debido a que no estamos acostumbrados a pensar en las ALU pobres y desatendidas, el intercambio de 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.

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

 // 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". Suponga 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 tiene acceso al bloque A, 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 recorrer la lista, debe mantener los punteros en dos bloques consecutivos. Por supuesto, usaría XOR en lugar de suma / resta, por lo que no tendría que preocuparse por el desbordamiento.

Puede extender esto a una "web vinculada" si quiere divertirse.

@VonC tiene razón, es un buen truco matemático. Imagínese 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

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 que a 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 a partir de la definición en 1 anterior)

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 (ver 1 arriba)

Ahora podemos sustituir 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 (ver 1 arriba)

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

Como nota al margen, reinventé esta rueda de forma independiente hace varios años en forma de intercambio de 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. Dado que 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 muy claramente en mi opinión.

Solo quiero agregar una explicación matemática para que la respuesta sea más completa. En teoría de grupos , XOR es un grupo abeliano , también llamado grupo conmutativo. Significa que cumple cinco requisitos: cierre, asociatividad, elemento de identidad, elemento inverso, conmutatividad.

Fórmula de intercambio XOR:

a = a XOR b
b = a XOR b
a = a XOR b 

Expande la fórmula, sustituye a, b con la fórmula anterior:

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b

Conmutatividad significa "a XOR b" igual a "b XOR a":

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b

Asociatividad significa "(a XOR b) XOR c" igual a "a XOR (b XOR c)":

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b)
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b)

El elemento inverso en XOR es él mismo, significa que cualquier valor XOR consigo mismo da cero:

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b) 
            = a XOR 0
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b) 
            = b XOR 0 XOR 0

El elemento de identidad en XOR es cero, significa que cualquier valor XOR con cero se deja sin cambios:

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b) 
            = a XOR 0 
            = a
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b) 
            = b XOR 0 XOR 0 
            = b XOR 0
            = b

Y puede obtener más información en teoría de grupos .

Otros han publicado explicaciones, pero creo que se entendería mejor si se acompaña de un buen ejemplo.

Tabla de verdad de XOR

Si consideramos la tabla de verdad anterior y tomamos los valores A = 1100y B = 0101podemos intercambiar los valores como tales:

A = 1100
B = 0101


A ^= B;     => A = 1100 XOR 0101
(A = 1001)

B ^= A;     => B = 0101 XOR 1001
(B = 1100)

A ^= B;     => A = 1001 XOR 1100
(A = 0101)


A = 0101
B = 1100