language agnostic - smart - ¿Cómo funciona el intercambio de variables XOR?

solidity español

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 significa, pero ¿alguien me puede guiar por la lógica de cómo funciona?

Answer 1

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

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

, asi que:

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

Answer 2

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 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 por lo que (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 bit solo en las posiciones de bit donde a y b tienen bits opuestos. Eso es cualquiera (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
= un XOR 0 debido a [4] arriba
= a debido a la definición de XOR (ver 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 (ver 1 arriba)

Aquí encontrará información más detallada: 1

Answer 3

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 arriba de una manera difícil de leer),

El mismo razonamiento se aplica a xor swaps: a ^ b ^ b = a y a ^ b ^ a = a. Como 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 4

La mayoría de las personas cambiaría dos variables xey utilizando 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 Cambiar 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 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!

La computadora en realidad 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 de máquina):

ADD 3 A // add 3 to register A

La ALU (Unidad de 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 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.

Tomamos los datos temporales implícitos de la ALU por sentado, 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 pobre, 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 5

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 variable A, B contiene originalmente los valores 1,2, puede cambiarlos 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". 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 tiene acceso al bloque A, le da la dirección de B. Para llegar a C, toma el "puntero" en B y reste 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 extender esto a una "web vinculada" si quiere divertirse.

Answer 6

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

Digamos que comienzas con x = 11 yy = 5 en binario (y voy a usar una máquina hipotética de 4 bits), aquí están 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!

Answer 7

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 ciclo único o multiciclo, era más barato usar este truco para evitar costosas desreferencias en la memoria o derramar 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 la práctica general, el compilador puede averiguar qué es lo que realmente desea hacer cuando realiza un intercambio con una variable temp 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 8

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 completamente asociativo y conmutativo:

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

Como 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 9

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