nemediano

Este es otro de los trucos que me enseño Eduardo Lemus cuando me estaba preparando para mis entrevistas en Microsoft. Se trata de hacer un cambio swap entre dos variables con la restricción de que no podemos usar ninguna variable temporal como buffer.

Antes que nada quiero aclarar que este truco es una mala practica, en la mayoría de los lugares donde lo he visto (mientras me documentaba para escribir este post) aconsejan no hacerlo. La razón, aunque el truco funciona (y como veremos adelante tiene un fundamento solido) es confuso. Es decir según los IS la ganancia en performance es muy poca comparada con la complicación en entender el código escrito. Además de que en computadoras modernas este truco puede ser mas lento que la solución estándar (estúpidos optimizadores de memoria).

Así que solo ocuparlo en código que quieran usar con fin de hacer faramalla, show e impresionar chicas. O en caso de que algún entrevistador para alguna chamba se pase de listo y les pregunte como hacerlo.

Entendiendo el problema

En muchos algoritmos (por ejemplo en ordenación) es necesario intercambiar los valores de dos variables. Para simplificar el resto de la explicación asumiré sin perdida de generalidad (como me gusta usar esa frase ) que se tienen valores numéricos y enteros.

Es decir al principio tenemos algo como.

A = 2
B = 4

Queremos llevar a cabo la operación de intercambio y obtener una situación como:

A = 4
B = 2

Como lo haría una persona normal

Pues como nos enseñaron en la escuela XD. En todos los lenguajes de programación al asignación es una operación destructiva. Es decir al momento de asignar un valor a una variable se pierde el contenido anterior. (¡Estúpidas limitantes físicas del computo!).

Por lo que la gente que no sabe el truco haría algo así:

TEMP = A
A = B
B = TEMP

De esta manera tenemos un espacio de memoria extra donde guardar el valor de A, por lo tanto podemos destruir el contenido de A sin tentarnos nuestro corazoncillo. Y recuperarlo después del buffer temporal.

Ahora lo interesante: ¿Cómo se hace sin usar ninguna variable TEMP?

La solución del matemático.

Ahora si ustedes son de esas personas que saben un montón de matemáticas, pero jamas han programado de a de veras (¡Como los hombres!) podrían sugerir esta solución. (No se hagan se que por ahí hay muchísimos).

A = A + B
B = A – B
A = A – B

Ahora sabemos que ésta es un caso particular de una solución mas general.

1. Combina los dos valores en la variable A por medio de una operación binaria bien portada (Es decir que sea invertible). En este momento en A están guardados de alguna manera los dos valores.
2. Usa la operación inversa de la operación binaria para extraer en la variable B el valor original de A a partir del valor actual de A. Recuerda que no hemos modificado B.
3. Usa la operación inversa para extraer ahora el viejo valor de B en A. Recordando que tenemos guardado en B el valor original de A.

El fallo de la solución anterior es que trabajamos con maquinas de memoria finita, es decir podría pasar que la operación bien portada que es la suma produzca un número tan grande que no quepa en la localidad de memoria que le guardamos. ¿No se acuerdan del molesto carry cuando nos enseñaron la suma en binario y  hacer circuitos sumadores? Pues es aquí donde nos vino a fastidiar la vida.

La solución del computólogo

Tan simple, tan elegante, tan parecida a la solución del matemático XD (Por ahí dicen que es la misma por que los computologos y los matemáticos son casi lo mismo ). Pues resulta que hay mas de una operación bien portada y una que tiene todo lo que necesitamos es el XOR.

x	y	xy
0	0	0
0	1	1
1	0	1
1	1	0

¡Muérete de envidia suma! ¡El XOR es una suma sin carry vean la tabla!. ¿Suficiente? El XOR (conocido también en los bajos mundos de la lógica como disyunción exclusiva) es una de las operaciones que pueden construir toda la lógica de primer orden, además es conmutativo, asociativo y es su propio inverso. Pueden ver aquí la lista de todo lo bello que es el XOR. Es mas: ¡XOR soy tu fan!

Es decir podemos usar el XOR que como no tiene carry y nunca se desborda para hacer

A = A B
B = B A
A = A B

¿Mencione que es conmutativo y que es su propio inverso? Además que en todo lenguaje decente como en C y C++ y en algunos no decentes (Java ) Tenemos un operador de XOR y tenemos una forma abreviada de hacer la asignación. ¿No me creen? Miren con sus propios ojos:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
using namespace std;
 
int main (int argc, char* argv[]) {
 
	int a = 4, b = 2;
 
	cout << "Los valores son: a = " << a << " b = " << b << endl;
 
	swap(a, b);
 
	cout << "Después del swap:" << endl;
	cout << "Los valores son: a = " << a << " b = " << b << endl;
 
	return 0;
}
 
void swap (int &a, int &b) {
	a ^= b;
	b ^= a;
	a ^= b;
}

Y para que no digan que no pelo a la banda Javera, tomen no se vallan a enojar.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class TestSwaping {
 
	public static void main(String[] args) {
		int a = 4, b = 2;
 
		System.out.println("Los valores son: a = " + a + " b = " + b);
 
		a ^= b;
		b ^= a;
		a ^= b;
 
		System.out.println("Después del swap");
		System.out.println("Los valores son: a = " + a + " b = " + b);
	}
 
}

Mas información sobre la correctez y demás cosas de este truco esta en su pagina wikipedia.