Pregunta ¿Por qué el intercambio de valores con XOR falla al usar esta forma compuesta?


Encontré este código para intercambiar dos números sin usar una tercera variable, usando el XOR ^ operador.

Código: 

int i = 25;
int j = 36;
j ^= i;       
i ^= j;
j ^= i;

Console.WriteLine("i:" + i + " j:" + j);

//numbers Swapped correctly
//Output: i:36 j:25

Ahora cambié el código anterior a este código equivalente.

Mi código: 

int i = 25;
int j = 36;

j ^= i ^= j ^= i;   // I have changed to this equivalent (???).

Console.WriteLine("i:" + i + " j:" + j);

//Not Swapped correctly            
//Output: i:36 j:0

Ahora, quiero saber, ¿Por qué mi código da salida incorrecta?


76
2018-04-07 06:56


origen


Respuestas:


EDITAR: Bien, lo tengo.

El primer punto es que obviamente no deberías usar este código de todos modos. Sin embargo, cuando lo expandes, se convierte en equivalente a:

j = j ^ (i = i ^ (j = j ^ i));

(Si utilizáramos una expresión más complicada, como foo.bar++ ^= i, sería importante que el ++ solo fue evaluado una vez, pero aquí creo que es más simple).

Ahora, el orden de evaluación de los operandos siempre es de izquierda a derecha, así que para empezar obtenemos:

j = 36 ^ (i = i ^ (j = j ^ i));

Esto (arriba) es el paso más importante. Hemos terminado con 36 como LHS para la operación XOR que se ejecuta por última vez. El LHS no es "el valor de j después de que se haya evaluado el RHS ".

La evaluación de la RHS de ^ implica la expresión "un nivel anidado", por lo que se convierte en:

j = 36 ^ (i = 25 ^ (j = j ^ i));

Luego, mirando al nivel más profundo de anidación, podemos sustituir ambos i y j:

j = 36 ^ (i = 25 ^ (j = 25 ^ 36));

... que se convierte

j = 36 ^ (i = 25 ^ (j = 61));

La asignación a j en el RHS ocurre primero, pero el resultado se sobrescribe al final de todos modos, por lo que podemos ignorar eso; no hay más evaluaciones de j antes de la asignación final:

j = 36 ^ (i = 25 ^ 61);

Esto ahora es equivalente a:

i = 25 ^ 61;
j = 36 ^ (i = 25 ^ 61);

O:

i = 36;
j = 36 ^ 36;

Que se convierte en:

i = 36;
j = 0;

yo pensar eso es todo correcto, y llega a la respuesta correcta ... disculpas a Eric Lippert si algunos de los detalles sobre el orden de evaluación están un poco fuera de juego :(


76
2018-04-07 07:07



Comprueba el IL generado y arroja resultados diferentes;

El intercambio correcto genera una respuesta directa:

IL_0001:  ldc.i4.s   25
IL_0003:  stloc.0        //create a integer variable 25 at position 0
IL_0004:  ldc.i4.s   36
IL_0006:  stloc.1        //create a integer variable 36 at position 1
IL_0007:  ldloc.1        //push variable at position 1 [36]
IL_0008:  ldloc.0        //push variable at position 0 [25]
IL_0009:  xor           
IL_000a:  stloc.1        //store result in location 1 [61]
IL_000b:  ldloc.0        //push 25
IL_000c:  ldloc.1        //push 61
IL_000d:  xor 
IL_000e:  stloc.0        //store result in location 0 [36]
IL_000f:  ldloc.1        //push 61
IL_0010:  ldloc.0        //push 36
IL_0011:  xor
IL_0012:  stloc.1        //store result in location 1 [25]

El intercambio incorrecto genera este código:

IL_0001:  ldc.i4.s   25
IL_0003:  stloc.0        //create a integer variable 25 at position 0
IL_0004:  ldc.i4.s   36
IL_0006:  stloc.1        //create a integer variable 36 at position 1
IL_0007:  ldloc.1        //push 36 on stack (stack is 36)
IL_0008:  ldloc.0        //push 25 on stack (stack is 36-25)
IL_0009:  ldloc.1        //push 36 on stack (stack is 36-25-36)
IL_000a:  ldloc.0        //push 25 on stack (stack is 36-25-36-25)
IL_000b:  xor            //stack is 36-25-61
IL_000c:  dup            //stack is 36-25-61-61
IL_000d:  stloc.1        //store 61 into position 1, stack is 36-25-61
IL_000e:  xor            //stack is 36-36
IL_000f:  dup            //stack is 36-36-36
IL_0010:  stloc.0        //store 36 into positon 0, stack is 36-36 
IL_0011:  xor            //stack is 0, as the original 36 (instead of the new 61) is xor-ed)
IL_0012:  stloc.1        //store 0 into position 1

Es evidente que el código generado en el segundo método es incoherente, ya que el valor anterior de j se usa en un cálculo donde se requiere el nuevo valor.


15
2018-04-07 07:18



Cargas C # j, i, j, i en la pila, y almacena cada XOR resultado sin actualizar la pila, por lo que la izquierda XOR usa el valor inicial para j.


7
2018-04-07 07:22



Reescribiendo:

j ^= i;       
i ^= j;
j ^= i;

En expansión ^=:

j = j ^ i;       
i = j ^ i;
j = j ^ i;

Sustituir:

j = j ^ i;       
j = j ^ (i = j ^ i);

Sustituir esto solo funciona si / porque el lado izquierdo del ^ operador se evalúa primero:

j = (j = j ^ i) ^ (i = i ^ j);

Colapso ^:

j = (j ^= i) ^ (i ^= j);

Simétricamente:

i = (i ^= j) ^ (j ^= i);

0
2017-11-21 18:29