Hacer un swap con XORs en C/C++

elira Programación Leave a Comment

En alguna ocasión encontré un código con una forma muy curiosa de hacer un swap, veamos un código de ejemplo:

#include <stdio.h>
int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    printf("%d %d\n", a, b);
    return 0;
}

La razón por la que esto funciona puede ser deducida si se conoce como funciona un XOR, así que recordemos rápidamente la tabla de verdad para XOR

A B A^B
0 0 0
0 1 1
1 0 1
1 1 0

Ahora veamos que sucede con un ejemplo ilustrativo, usando los número 10 y 12.

VAR DEC BIN
a 10 1010
b 12 1100

En el primer paso

a = a ^ b;

Obtenemos lo siguiente:

VAR DEC BIN
a 6 0110
b 12 1100

En el segundo paso

b = a ^ b;

Obtenemos lo siguiente:

VAR DEC BIN
a 6 0110
b 10 1010
¿Qué ha pasado aquí?

Como podemos ver el valor de a ha pasado a b, pero ¿como ha sido esto posible?, pues muy simple, si nos fijamos en la tabla de verdad del XOR podemos ver que solo devuelve verdadero al momento de tener dos bits distintos, así que si hacemos algo del tipo a^a obtendremos un montón de ceros (dado que todos los bits son iguales). El valor que se asignó a b en el paso anterior es igual a a^b^b, y sabemos que b^b es igual a muchos ceros, por lo tanto tenemos a^0 lo cual es igual a a.

Recuerda las propiedades del XOR

Dos propiedades importantes del XOR y que sirven para este pequeño truco son la asociatividad y la conmutatividad, lo que quiere decir que las operaciones de XOR con más de dos operandos pueden ser calculadas en el orden que sea y agrupando como sea conveniente.

Visto como un ejemplo, tenemos:

a^b^c = c^b^a = (c^b)^a = a^(b^c) = (a^b)^c = c^(a^b) = …

 

En el tercer paso tenemos:

a = a ^ b;

Que nos da como resultado:

VAR DEC BIN
a 12 1100
b 10 1010

Y hemos terminado de hacer el swap. El valor que se asigna a a en la ultima operación es a = a^b^a, que es igual a a^a^b que es igual a b.

Dentro de las ventajas que tenemos al usar este método es que no necesitamos usar una nueva variable, ni usar llamados a otras funciones.