Algoritmo de intercambio XOR

En programación informática , el intercambio exclusivo o swap (a veces abreviado como XOR swap ) es un algoritmo que utiliza la operación exclusiva o bit a bit 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 o exclusiva . A veces se lo analiza como una optimización de programas , pero casi no hay casos en los que el intercambio mediante o exclusiva proporcione 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 ; // XOR los valores y almacenar el resultado en X Y := X XOR Y ; // XOR los valores y almacenar el resultado en Y X := Y XOR X ; // XOR los valores y almacenar el resultado en X     
     
     

Dado que XOR es una operación conmutativa , tanto X XOR Y como Y XOR X se pueden utilizar indistintamente en cualquiera de las tres líneas anteriores. Tenga en cuenta que en algunas arquitecturas el primer operando de la instrucción XOR especifica la ubicación de destino en la que se almacena el resultado de la operación, lo que evita esta intercambiabilidad. El algoritmo corresponde típicamente a tres instrucciones de código de máquina , representadas por las instrucciones de pseudocódigo y ensamblador 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 nombrado en el primer argumento. Si se utiliza el ensamblador x86, los valores X e Y están en los registros eax y ebx (respectivamente) y xorse coloca el resultado de la operación en el primer registro.

Sin embargo, en la versión o implementación del 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á en cero; no se "intercambiará consigo mismo". Esto no es lo mismo que si x e y tienen los mismos valores. El problema solo surge 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 en cero (porque x = y, entonces X XOR Y es cero) y establece y en cero (ya que utiliza la misma ubicación de almacenamiento), lo que hace que x e y pierdan sus valores originales.

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

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

Supongamos que tenemos dos registros distintos R1y, R2como en la tabla siguiente, con valores iniciales A y B respectivamente. Realizamos las operaciones siguientes en secuencia y reducimos nuestros resultados utilizando las propiedades enumeradas anteriormente.

Como XOR se puede interpretar como una suma binaria y un par de bits se puede interpretar como un vector en un espacio vectorial bidimensional sobre el campo con dos elementos , los pasos del algoritmo se pueden interpretar como una multiplicación por matrices de 2×2 sobre el campo con dos elementos. Para simplificar, supongamos inicialmente que x e y son bits individuales, no vectores de bits.

Por ejemplo, el paso:

X := X XOR Y    

Lo cual también tiene implícito:

Y := Y  

corresponde a la matriz como ${\displaystyle \left({\begin{smallmatrix}1&1\\0&1\end{smallmatrix}}\right)}$

${\displaystyle {\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}={\begin{pmatrix}x+y\\y\end{pmatrix}}.}$

La secuencia de operaciones se expresa entonces 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}}}$

(trabajando con valores binarios, por lo tanto ), que expresa la matriz elemental de conmutación de dos filas (o columnas) en términos de las transvecciones (cortantes) de agregar un elemento al otro. ${\estilo de visualización 1+1=0}$

Para generalizar a donde X e Y no son bits individuales, sino vectores de bits de longitud n , estas matrices 2×2 se reemplazan por matrices de bloques 2n ×2n tales como${\displaystyle \left({\begin{smallmatrix}I_{n}&I_{n}\\0&I_{n}\end{smallmatrix}}\right).}$

Estas matrices operan sobre valores, no sobre variables (con ubicaciones de almacenamiento), por lo tanto, esta interpretación evita los problemas de ubicación de almacenamiento y el problema de que ambas variables compartan la misma ubicación de almacenamiento.

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

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

      
    
    
    

El código primero verifica si las direcciones son distintas y utiliza una cláusula de protección para salir de la función antes de tiempo si son iguales. Sin esa verificación, si fueran iguales, el algoritmo se convertiría en un triple, *x ^= *xlo que daría como resultado cero.

El algoritmo de intercambio XOR también se puede definir con una macro:

#define XORSWAP_UNSAFE(a, b) \ 
  ((a) ^= (b), (b) ^= (a), \ 
   (a) ^= (b)) /* No funciona cuando a y b son el mismo objeto - asigna cero \ 
                  (0) al objeto en ese caso */ 
#define XORSWAP(a, b) \ 
  ((&(a) == &(b)) ? (a) /* Verificar direcciones distintas */                     \ 
                  : XORSWAP_UNSAFE(a, b))

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 incurre en latencia cero. (Esto se llama 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 los tres XOR tomados en conjunto. Otra razón es que las CPU modernas se esfuerzan por ejecutar instrucciones en paralelo a través de canalizaciones de instrucciones . En la técnica XOR, las entradas a cada operación dependen de los resultados de la operación anterior, por lo que deben ejecutarse en un orden estrictamente secuencial, anulando cualquier beneficio del paralelismo a nivel de instrucción . ^[3]

El intercambio XOR también se complica en la práctica debido al aliasing . Si se intenta realizar un intercambio XOR del contenido de alguna ubicación consigo misma, el resultado es que la ubicación se pone a cero y se pierde su valor. Por lo tanto, el intercambio XOR no debe usarse a ciegas en un lenguaje de alto nivel si es posible el aliasing. Este problema no se aplica si la técnica se usa en ensamblaje para intercambiar el contenido de dos registros.

Se producen problemas similares con la llamada por nombre , como en el Dispositivo de Jensen , donde intercambiar iy A[i]a través de una variable temporal produce resultados incorrectos debido a que los argumentos están relacionados: intercambiar a través de temp = i; i = A[i]; A[i] = tempcambia el valor de ien la segunda declaración, lo que luego da como resultado el ivalor incorrecto de A[i]en la tercera declaración.

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 diversas formulaciones ligeramente diferentes, pero en gran medida equivalentes. Por ejemplo: ^[4]

void AddSwap ( entero sin signo * x , entero sin signo * y ) { * x = * x + * y ; * y = * x - * y ; * x = * x - * y ; }        

        
        
        

A diferencia del intercambio XOR, esta variación requiere que el procesador subyacente o el lenguaje de programación utilice un método como la aritmética modular o bignums para garantizar que el cálculo de X + Yno pueda causar un error debido a un desbordamiento de enteros . Por lo tanto, se observa con 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 resta de enteros sin signo siguen las reglas de la aritmética modular , es decir, se realizan en el grupo cíclico donde es el número de bits de . De hecho, la corrección del algoritmo se desprende del hecho de que las fórmulas y se cumplen en cualquier grupo abeliano . Esto generaliza la prueba para el algoritmo de intercambio XOR: XOR es tanto la suma como la resta en el grupo abeliano (que es la suma directa de s copias de ). ${\displaystyle \mathbb {Z} /2^{s}\mathbb {Z} }$${\estilo de visualización s}$unsigned int${\displaystyle (x+y)-y=x}$${\displaystyle (x+y)-((x+y)-y)=y}$${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{s}}$${\displaystyle \mathbb {Z} /2\mathbb {Z} }$

Esto no se cumple cuando se trabaja con el signed inttipo (el valor 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 generar resultados incorrectos.

La secuencia de operaciones en AddSwapse puede expresar mediante la 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 las arquitecturas que carecen de una instrucción de intercambio dedicada, debido a que evita el registro temporal adicional, se requiere el algoritmo de intercambio XOR para la asignación óptima de registros . Esto es particularmente importante para los compiladores que utilizan la forma de asignación única estática para la asignación de registros; estos compiladores ocasionalmente producen programas que necesitan intercambiar dos registros cuando no hay registros libres. El algoritmo de intercambio XOR evita la necesidad de reservar un registro adicional o de volcar registros en la memoria principal. ^[5] La variante de adición/resta también se puede utilizar para 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, la dispersión de variables es costosa 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 debido 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 de un cifrado de Feistel)