Algoritmo de intercambio XOR

En programación de computadoras , el intercambio exclusivo o (a veces abreviado como intercambio XOR ) es un algoritmo que utiliza la operación exclusiva o bit a bit para intercambiar los valores de dos variables sin usar la variable temporal que normalmente se requiere.

El algoritmo es principalmente una novedad y una forma de demostrar las propiedades de la operación exclusiva . A veces se analiza como una optimización del programa , pero casi no hay casos en los que el intercambio mediante una técnica exclusiva o proporcione beneficios sobre la técnica estándar y obvia.

el algoritmo

El intercambio convencional requiere el uso de una variable de almacenamiento temporal. Sin embargo, al utilizar 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 almacena el resultado en X Y := X XOR Y ; // XOR los valores y almacena el resultado en Y X := Y XOR X ; // XOR los valores y almacenamos el resultado en X

Dado que XOR es una operación conmutativa , X XOR Y o Y XOR X se pueden usar 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 normalmente corresponde a tres instrucciones de código de máquina , representadas por el pseudocódigo correspondiente y las instrucciones de ensamblaje 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. Usando el ensamblaje x86, los valores X e Y están en los registros eax y ebx (respectivamente) y xorcoloca 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 xey usan la misma ubicación de almacenamiento, ya que el valor almacenado en esa ubicación será puesto a cero por la primera instrucción XOR y luego permanecerá cero ; no será "intercambiado consigo mismo". Esto no es lo mismo que si xey tuvieran los mismos valores. El problema sólo surge cuando xey usan la misma ubicación de almacenamiento, en cuyo caso sus valores ya deben ser iguales . Es decir, si xey usan la misma ubicación de almacenamiento, entonces la línea:

X := X XOR Y

establece x en cero (porque x = y , por lo que X XOR Y es cero) y establece y en cero (ya que usa la misma ubicación de almacenamiento), lo que hace que xey pierdan sus valores originales.

Prueba de corrección

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

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

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

Interpretación del álgebra lineal

Como XOR puede interpretarse como una suma binaria y un par de bits puede interpretarse como un vector en un espacio vectorial bidimensional sobre el campo con dos elementos , los pasos del algoritmo pueden interpretarse 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

que también tiene el implícito:

Sí := Sí

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

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

La secuencia de operaciones se expresa entonces como:

{\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, entonces ), que expresa la matriz elemental de cambiar dos filas (o columnas) en términos de las transvecciones (cortes) de agregar un elemento al otro. $1+1=0$

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

Estas matrices operan con valores, no con variables (con ubicaciones de almacenamiento), por lo que esta interpretación se abstrae de las cuestiones de la ubicación de almacenamiento y del problema de que ambas variables comparten la misma ubicación de almacenamiento.

Ejemplo de código

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 usa una cláusula de protección para salir temprano de la función si son iguales. Sin esa verificación, si fueran iguales, el algoritmo se reduciría a un triple y *x ^= *xdarí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 los mismo objeto: asigna cero \  (0) al objeto en ese caso */ #define XORSWAP(a, b) \  ((&(a) == &(b)) ? (a) /* Comprobar direcciones distintas * /  \   : XORSWAP_UNSAFE(a,b))

Razones para evitarlo en la práctica

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, moverse entre registros regularmente genera 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 juntos. Otra razón es que las CPU modernas se esfuerzan por ejecutar instrucciones en paralelo a través de canales 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 orden estrictamente secuencial, anulando cualquier beneficio del paralelismo a nivel de instrucción . ^[3]

alias

El intercambio XOR también se complica en la práctica por el aliasing . Si se intenta intercambiar XOR el contenido de alguna ubicación consigo mismo, 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 alias. Este problema no se aplica si la técnica se utiliza en ensamblaje para intercambiar el contenido de dos registros.

Se producen problemas similares con call by name , como en Jensen's Device , donde el intercambio iy A[i]mediante una variable temporal produce resultados incorrectos debido a que los argumentos están relacionados: el intercambio mediante 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.

Variaciones

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

void AddSwap ( int sin signo * x , int sin signo * y ) { if ( x ! = 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 la aritmética modular o bignums para garantizar que el cálculo X + Yno pueda causar un error debido a un desbordamiento de enteros . Por lo tanto, en la práctica se ve aún más raramente que el intercambio XOR.

Sin embargo, la implementación de lo AddSwapanterior 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 está el número de bits de . De hecho, la corrección del algoritmo se deriva del hecho de que las fórmulas y se mantienen en cualquier grupo abeliano . Esto generaliza la prueba del 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 ). $\mathbb {Z} /2^{s}\mathbb {Z}$ $s$ unsigned int $(x+y)-y=x$ $(x+y)-((x+y)-y)=y$ $(\mathbb {Z} /2\mathbb {Z} )^{s}$ $\mathbb {Z} /2\mathbb {Z}$

Esto no se aplica cuando se trata del signed inttipo (el valor predeterminado para int). El desbordamiento de enteros con signo es un comportamiento indefinido en C y, por lo tanto, el estándar no garantiza la aritmética modular, lo que puede generar resultados incorrectos.

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

{\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}}

Solicitud de registro de asignación

En 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 una asignación óptima de registros . Esto es particularmente importante para los compiladores que utilizan un formulario 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 transferir registros a la memoria principal. ^[5] La variante de suma/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, derramar variables es costoso debido al ancho de banda de memoria limitado y la alta latencia de la memoria, mientras que limitar el uso de registros puede mejorar el rendimiento debido a la partición dinámica del archivo de registro . Por lo tanto, algunos compiladores de GPU requieren el algoritmo de intercambio XOR. ^[7]

Ver también

diferencia simétrica
lista enlazada XOR
Cifrado Feistel (el algoritmo de intercambio XOR es una forma degenerada de un cifrado Feistel)

Notas

↑ Las primeras tres propiedades, junto con la existencia de una inversa para cada elemento, son la definición de grupo abeliano . La última propiedad es la afirmación de que todo elemento es una involución , es decir, de orden 2, lo cual no es cierto para todos los grupos abelianos.

Referencias

^ "La magia de XOR". Cs.umd.edu. Archivado desde el original el 1 de abril de 2014 . Consultado el 2 de abril de 2014 .
^ "Intercambio de valores con XOR". gráficos.stanford.edu . Consultado el 2 de mayo de 2014 .
^ Amarasinghe, Saman; Leiserson, Charles (2010). "6.172 Ingeniería del rendimiento de sistemas de software, Clase 2". MIT OpenCourseWare . Instituto de Tecnología de Massachusetts. Archivado desde el original el 25 de enero de 2015 . Consultado el 27 de enero de 2015 .
^ Warren, Henry S. (2003). El deleite del hacker . Boston: Addison-Wesley. pag. 39.ISBN 0201914654.
^ Pereira, Fernando Magno Quintão; Palsberg, Jens (2009). "Eliminación de la SSA después de la asignación del registro" (PDF) . Construcción del compilador . Apuntes de conferencias sobre informática. 5501 : 158-173. doi :10.1007/978-3-642-00722-4_12. ISBN 978-3-642-00721-7. Consultado el 17 de abril de 2022 .
^ Hackear, Sebastián; Grund, Daniel; Goos, Gerhard (2006). "Registrar asignación para programas en formulario SSA". Construcción del compilador . Apuntes de conferencias sobre informática. 3923 : 247–262. doi : 10.1007/11688839_20 . ISBN 978-3-540-33050-9.
^ Abbott, Connor; Schürmann, Daniel. "Asignación de registros basada en SSA para arquitecturas de GPU" (PDF) . Consultado el 17 de abril de 2022 .