algoritmo de intercambio XOR

En programación informática , el intercambio exclusivo (a veces abreviado como intercambio XOR ) es un algoritmo que utiliza la operación lógica "o exclusivo" a nivel de bits para intercambiar los valores de dos variables sin utilizar la variable temporal que normalmente se requiere.

El algoritmo es principalmente una novedad y una forma de demostrar las propiedades de la operación OR exclusiva . A veces se habla de una optimización de programas , pero prácticamente no existen casos en los que el intercambio mediante OR exclusiva ofrezca ventajas sobre la técnica estándar y obvia.

El intercambio convencional requiere el uso de una variable de almacenamiento temporal. Sin embargo, con el algoritmo de intercambio XOR, no se necesita almacenamiento temporal. El algoritmo es el siguiente: ^{[ 1 ] [ 2 ]}

X := Y XOR X ; // Realiza la operación XOR entre los valores y almacena el resultado en X Y := X XOR Y ; // Realiza la operación XOR entre los valores y almacena el resultado en Y X := Y XOR X ; // Realiza la operación XOR entre los valores y almacena el resultado en X

Dado que XOR es una operación conmutativa , tanto X XOR Y como Y XOR X pueden usarse indistintamente en cualquiera de las tres líneas anteriores. Cabe destacar que, en algunas arquitecturas, el primer operando de la instrucción XOR especifica la ubicación de destino donde se almacena el resultado de la operación, lo que impide esta intercambiabilidad. El algoritmo generalmente corresponde a tres instrucciones de código máquina , representadas por pseudocódigo e instrucciones de ensamblaje correspondientes en las tres filas de la siguiente tabla:

En el ejemplo de código ensamblador System/370 anterior, R1 y R2 son registros distintos , y cada XRoperación deja su resultado en el registro especificado en el primer argumento. En ensamblador x86, los valores X e Y se encuentran en los registros eax y ebx (respectivamente), y xorel resultado de la operación se coloca en el primer registro (Nota: x86 admite la instrucción XCHG, por lo que el uso de la triple XOR no tiene sentido en esta arquitectura). En ensamblador RISC-V, los valores X e Y se encuentran en los registros x10 y x11, y xorel resultado de la operación se coloca en el primer operando.

Sin embargo, en la versión o implementación en pseudocódigo o lenguaje de alto nivel, el algoritmo falla si x e y usan la misma ubicación de almacenamiento, ya que el valor almacenado en esa ubicación se pondrá a cero con la primera instrucción XOR y luego permanecerá cero; no se "intercambiará consigo mismo". Esto no es lo mismo que si x e y tienen los mismos valores. El problema surge solo cuando x e y usan la misma ubicación de almacenamiento, en cuyo caso sus valores ya deben ser iguales. Es decir, si x e y usan la misma ubicación de almacenamiento, entonces la línea:

X := X XOR Y

establece x a cero (porque x = y, por lo tanto X XOR Y es cero) y establece y a cero (ya que utiliza la misma ubicación de almacenamiento), lo que provoca que x e y pierdan sus valores originales.

La operación binaria XOR sobre cadenas de bits de longitud${\displaystyle N}$exhibe las siguientes propiedades (donde${\displaystyle \oplus }$denota XOR): ^{[ a ]}

• L1. Conmutatividad :${\displaystyle A\oplus B=B\oplus A}$
• L2. Asociatividad :${\displaystyle (A\oplus B)\oplus C=A\oplus (B\oplus C)}$
• L3. Existe identidad : existe una cadena de bits, 0, (de longitud N ) tal que${\displaystyle A\oplus 0=A}$para cualquier${\displaystyle A}$
• L4. Cada elemento es su propio inverso : para cada${\displaystyle A}$,${\displaystyle A\oplus A=0}$.

Supongamos que tenemos dos registros distintos , A R1y R2B, como se muestra en la tabla a continuación, con valores iniciales A y B respectivamente. Realizamos las operaciones que se describen a continuación en secuencia y reducimos los resultados utilizando las propiedades mencionadas anteriormente.

X := X XOR Y

Y := Y

Una función en C que implementa el algoritmo de intercambio XOR:

void xor_swap ( int * x , int * y ) { if ( x == y ) return ; * x ^= * y ; * y ^= * x ; * x ^= * y ; }

El código primero comprueba si las direcciones son distintas y utiliza una cláusula de protección para salir de la función anticipadamente si son iguales. Sin esa comprobación, si fueran iguales, el algoritmo se reduciría a una tripleta, *x ^= *xlo que resultaría en cero.

En las arquitecturas de CPU modernas , la técnica XOR puede ser más lenta que usar una variable temporal para realizar el intercambio. Al menos en las CPU x86 recientes, tanto de AMD como de Intel, el movimiento entre registros regularmente genera latencia cero. (Esto se denomina eliminación de MOV). Incluso si no hay ningún registro arquitectónico disponible para usar, la XCHGinstrucción será al menos tan rápida como las tres operaciones XOR juntas. Otra razón es que las CPU modernas se esfuerzan por ejecutar instrucciones en paralelo mediante tuberías de instrucciones . En la técnica XOR, las entradas de cada operación dependen de los resultados de la operación anterior, por lo que deben ejecutarse en un orden estrictamente secuencial, lo que anula cualquier beneficio del paralelismo a nivel de instrucción . ^{[ 3 ]}

El principio subyacente del algoritmo de intercambio XOR se puede aplicar a cualquier operación que cumpla los criterios L1 a L4 anteriores. Reemplazar XOR por suma y resta da lugar a varias formulaciones ligeramente diferentes, pero en gran medida equivalentes. Por ejemplo: ^{[ 4 ]}

void add_swap ( unsigned int * x , unsigned int * y ) { * x = * x + * y ; * y = * x - * y ; * x = * x - * y ; }

A diferencia del intercambio XOR, esta variación requiere que el procesador o lenguaje de programación subyacente utilice un método como aritmética modular o números grandes para garantizar que el cálculo X + Yno pueda causar un error por desbordamiento de enteros . Por lo tanto, se observa con aún menos frecuencia en la práctica que el intercambio XOR.

Sin embargo, la implementación de AddSwaplo anterior en el lenguaje de programación C siempre funciona incluso en caso de desbordamiento de enteros, ya que, según el estándar C, la suma y la resta de enteros sin signo siguen las reglas de la aritmética modular , es decir, se realizan en el grupo cíclico.${\displaystyle \mathbb {Z} /2^{s}\mathbb {Z} }$dónde${\displaystyle s}$es el número de bits de unsigned int. De hecho, la corrección del algoritmo se deduce del hecho de que las fórmulas${\displaystyle (x+y)-y=x}$y${\displaystyle (x+y)-((x+y)-y)=y}$se cumple en cualquier grupo abeliano . Esto generaliza la demostración del algoritmo de intercambio XOR: XOR es tanto la suma como la resta en el grupo abeliano.${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{s}}$(que es la suma directa de s copias de${\displaystyle \mathbb {Z} /2\mathbb {Z} }$).

Esto no se cumple al tratar con el signed inttipo (el predeterminado para int). El desbordamiento de enteros con signo es un comportamiento indefinido en C y, por lo tanto, la aritmética modular no está garantizada por el estándar, lo que puede llevar a resultados incorrectos.

La secuencia de operaciones AddSwapse puede expresar mediante multiplicación de matrices como:

${\displaystyle {\begin{pmatrix}1&-1\\0&1\end{pmatrix}}{\begin{pmatrix}1&0\\1&-1\end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}}$

En arquitecturas que carecen de una instrucción de intercambio dedicada, el algoritmo de intercambio XOR es necesario para una asignación óptima de registros , ya que evita el registro temporal adicional . Esto es particularmente importante para los compiladores que utilizan la asignación estática simple de registros; estos compiladores a veces generan programas que necesitan intercambiar dos registros cuando no hay ninguno libre. El algoritmo de intercambio XOR evita la necesidad de reservar un registro adicional o de volcar registros a la memoria principal. ^{[ 5 ]} La variante de suma/resta también puede utilizarse con el mismo propósito. ^{[ 6 ]}

Este método de asignación de registros es particularmente relevante para los compiladores de sombreadores de GPU . En las arquitecturas de GPU modernas, el desbordamiento de variables resulta costoso debido al ancho de banda de memoria limitado y la alta latencia de memoria, mientras que limitar el uso de registros puede mejorar el rendimiento gracias a la partición dinámica del archivo de registros . Por lo tanto, algunos compiladores de GPU requieren el algoritmo de intercambio XOR. ^{[ 7 ]}

• Diferencia simétrica
• Lista enlazada XOR
• Cifrado de Feistel (el algoritmo de intercambio XOR es una forma degenerada del cifrado de Feistel).