Intercambio Sin Variable Intermedia

Este algoritmo es tan sorprendente que a pesar de no ser propio no he podido evitar ponerlo. La idea esta sacada del libro "Graphics Gems, Andrew S. Glasnner". Consiste en intercambiar el valor de dos variables sin usar una tercera variable temporal. Para esto se usa el operador xor bit a bit. Este operador al trabajar a nivel de bit permite que el intercambio se realize sin importar el tipo de dato.

Este es el pseudocodigo:

a <= a xor b

b <= b xor a

a <= a xor b

La explicación1 tenemos que sacarla de las propiedades matematicas del operador xor. Este es conmutativo y asociativo por lo que podemos desarrollar las fórmulas de la siguiente manera.

Basicamente la demostración parte de las ecuaciones del algoritmo y llega a lo que queremos lograr (el intercambio de variables) usando las propiedades de xor (fórmulas 1 a 4).

Se puede ver en la demostración que se usan 5 variable a, a' ,a'', b y b'. Se hace esto para que sea la sintaxis correcta pero en la implementación se actualiza sobre la misma variable ya que esta no se vuelve a usar.

Como ejemplo pongo la inplementacion del algoritmo en C++ y ensamblador.

inline void swap(int &a,int &b){
   a^=b;
   b^=a;
   a^=b;
}

mov eax, a
mov ecx, b
xor eax, ecx
xor ecx, eax
xor eax, ecx
mov a,   eax
mov b,   ecx

Y para los que todavia no se lo crean un ejemplo de libro con a=5 y b=6.

Luis José Cabellos

1. La explicación de porque funciona si que es mia