El intercambio XOR ( ing. Algoritmo de intercambio Xor ) es un algoritmo que utiliza la operación XOR bit a bit (excluyendo "o") para intercambiar valores entre variables que contienen datos del mismo tipo, sin utilizar una variable adicional (temporal). La solución del problema viene dada por la propiedad de autorreversibilidad XOR: A XOR A = 0 для всех A.
Algoritmo en pseudocódigo :
X := X XOR Y Y := Y XOR X X := X XOR YEsto generalmente corresponde a tres instrucciones en código de máquina , como en el código ensamblador IBM System/370 :
XOR R1, R2 XOR R2, R1 XOR R1, R2donde R1y R2 son registros y la operación XOR almacena el resultado en el primer argumento.
El algoritmo se usa con especial frecuencia en la práctica de la programación en ensamblador debido a su eficiencia: otros algoritmos de intercambio requieren el uso de un registro intermedio (un recurso de almacenamiento adicional) o (para tipos numéricos) operaciones aritméticas adicionales (el uso excesivo de recursos informáticos). recursos), lo cual es especialmente importante cuando se programan microcontroladores y dispositivos simples similares que tienen requisitos estrictos para el consumo de memoria y los ciclos del procesador. Algunos compiladores de optimización pueden generar código que utiliza este algoritmo.
Sin embargo, en las CPU modernas de propósito general , la técnica XOR puede ser más lenta que usar una variable temporal para el intercambio debido a la paralelización de la ejecución de instrucciones: en la técnica XOR, los operandos de todas las instrucciones dependen de los resultados de las instrucciones anteriores, por lo que debe ejecutarse en estricto orden secuencial. A menudo, los detalles del algoritmo utilizado se ocultan dentro de una macro o una función en línea , y se selecciona uno u otro algoritmo de intercambio según las características de la plataforma de ejecución.
Al implementar un algoritmo de intercambio de este tipo, hay una serie de errores de captura, en particular, si la función de intercambio toma punteros o referencias y se llama con los mismos argumentos, los datos no se intercambiarán, pero se restablecerán. [una]
Varias arquitecturas implementan el intercambio XOR a nivel de hardware, la primera implementación efectiva es la máquina Datacraft ( 1970 ), que proporcionó el intercambio de cualquier registro en un ciclo de reloj. El PDP-6 tenía esta capacidad ya en 1964 ; su instrucción EXCHpodría intercambiar el contenido de cualquier registro con el contenido de cualquier ubicación de memoria u otro registro. Los procesadores x86 también tienen la instrucción XCHG.