Algoritmo de intercambio XOR

Utilizando el algoritmo de intercambio XOR para intercambiar burbujas entre variables sin el uso de almacenamiento temporal

En la programación informática, el exclusivo o intercambio (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 utilizando 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 o. A veces se trata como una optimización del programa, pero casi no hay casos en los que el intercambio a través de exclusivo o proporcione un beneficio sobre la técnica obvia y estándar.

El algoritmo

El intercambio convencional requiere el uso de una variable de almacenamiento temporal. Sin embargo, al usar el algoritmo de intercambio XOR, no se necesita almacenamiento temporal. El algoritmo es como sigue:

X := X XOR Y; // XOR los valores y almacenar el resultado en XY := Y XOR X; // XOR los valores y almacenar el resultado en YX := X XOR Y; // XOR los valores y almacenar 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 generalmente 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 XR deja su resultado en el registro mencionado en el primer argumento. Usando el ensamblaje x86, los valores X e Y están en los registros eax y ebx (respectivamente) y xor coloca el resultado de la operación en el primer registro.

Sin embargo, en la versión o implementación de 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 ese la ubicación se pondrá a cero con la primera instrucción XOR y luego permanecerá en cero; no será "intercambiado consigo mismo". Esto no es lo mismo que si x e y tuvieran 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 a cero (ya que usa la misma ubicación de almacenamiento), lo que hace que x e y pierdan sus valores originales.

Prueba de corrección

La operación binaria XOR sobre cadenas de bits de longitud N{displaystyle N} exhibe las siguientes propiedades (donde ⊕ ⊕ {displaystyle oplus } denota XOR:

• L1. Comunitario: A⊕ ⊕ B=B⊕ ⊕ A{displaystyle Aoplus B=Boplus A}
• L2. Asociación: ()A⊕ ⊕ B)⊕ ⊕ C=A⊕ ⊕ ()B⊕ ⊕ C){displaystyle (Aoplus B)oplus C=Aoplus (Boplus C)}
• L3. La identidad existe: hay un poco de cuerda, 0, (de longitud N. A⊕ ⊕ 0=A{displaystyle Aoplus 0=A} para cualquier A{displaystyle A}
• L4. Cada elemento es su propio inverso: para cada uno A{displaystyle A}, A⊕ ⊕ A=0{displaystyle Aoplus A=0}.

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

Paso	Operación	Registro 1	Registro 2	Reducción
0	Valor inicial	A{displaystyle A}	B{displaystyle B}	—
1	R1:= R1 XOR R2	A⊕ ⊕ B{displaystyle Aoplus B}	B{displaystyle B}	—
2	R2:= R1 XOR R2	A⊕ ⊕ B{displaystyle Aoplus B}	()A⊕ ⊕ B)⊕ ⊕ B=A⊕ ⊕ ()B⊕ ⊕ B){displaystyle (Aoplus B)oplus B=Aoplus (Boplus B)} =A⊕ ⊕ 0{displaystyle =Aoplus 0} =A{displaystyle =A}	L2 L4 L3
3	R1:= R1 XOR R2	()A⊕ ⊕ B)⊕ ⊕ A=()B⊕ ⊕ A)⊕ ⊕ A{displaystyle (Aoplus B)oplus A=(Boplus A)oplus A} =B⊕ ⊕ ()A⊕ ⊕ A){displaystyle =Boplus (Aoplus A)} =B⊕ ⊕ 0{displaystyle =Boplus 0} =B{displaystyle =B}	A{displaystyle A}	L1 L2 L4 L3

Interpretación del álgebra lineal

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 2×2 matrices sobre el campo de dos elementos. Para simplificar, suponga inicialmente que x e y son bits individuales, no vectores de bits.

Por ejemplo, el paso:

X := X XOR Y

que también tiene implícito:

Y := Y

corresponde a la matriz ()1101){displaystyle left({begin{smallmatrix}1 limit1 limit1end{smallmatrix}}right)} como

()1101)()xSí.)=()x+Sí.Sí.).{displaystyle {begin{pmatrix}1 = limit1end{pmatrix}{begin{pmatrix}x\yend{pmatrix}={begin{pmatrix}x+yend{pmatrix}}}}}}}

La secuencia de operaciones se expresa entonces como:

()1101)()1011)()1101)=()0110){begin{pmatrix}1 {} {} {begin{pmatrix}{begin{pmatrix}1 {11end{pmatrix}}{begin{pmatrix}1 {}={trix}} {trix}}} {trix} {}}}}}}}}}} {}}} {}}}}}}} {} {} {m}= {m} {m}= {m}t}t}t}t}t}t}t}t}t}t}t}t}t}t}}t} {m}t}t} {m}t} {b}t}cH}t}t}t}c}c}t}t}t}t}t}t}t}t}cH}cH}cHh}cH}}cH}}

(trabajando con valores binarios, por lo tanto 1+1=0{displaystyle 1+1=0}), que expresa la matriz elemental de cambiar dos filas (o columnas) en términos de las transvections (hesas) de añadir un elemento al otro.

Para generalizar a donde X y Y no son pedazos individuales, sino que en lugar de bit vectores de longitud n, estas matrices 2×2 son reemplazadas por 2n× 2n matrices de bloque como ()InIn0In).{displaystyle left({begin{smallmatrix}I_{n} {n} limitI_{n}end{smallmatrix}}right).}

Estas matrices operan sobre valores, no sobre variables (con ubicaciones de almacenamiento), por lo tanto, esta interpretación se abstrae de los problemas de ubicación de almacenamiento y el problema de compartir ambas variables. el mismo lugar de almacenamiento.

Ejemplo de código

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

vacío XorSwap()int *x, int *Sí.) {} si ()x ! Sí.) {} *x ^= *Sí.; *Sí. ^= *x; *x ^= *Sí.; }}

El código primero comprueba si las direcciones son distintas. De lo contrario, si fueran iguales, el algoritmo se plegaría a un triple *x ^= *x dando 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) /* Check for distinct addresses */ : XORSWAP_UNSAFE(a, b))

Razones para la evitación 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 intercambios. Al menos en las CPU x86 recientes, tanto de AMD como de Intel, el movimiento entre registros genera regularmente una latencia cero. (Esto se denomina eliminación de MOV). Incluso si no hay ningún registro de arquitectura disponible para usar, la instrucción XCHG será al menos tan rápida como los tres XOR juntos. 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 de 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.

Alias

El intercambio de XOR también se complica en la práctica debido a los alias. Si se intenta intercambiar por XOR el 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 de XOR no se debe usar a ciegas en un lenguaje de alto nivel si es posible la creación de alias. Este problema no se aplica si la técnica se usa en ensamblaje para intercambiar el contenido de dos registros.

Ocurren problemas similares con la llamada por nombre, como en el dispositivo de Jensen, donde el intercambio de i y A[i] a través de una variable temporal produce resultados incorrectos debido a los argumentos relacionados: intercambio a través de temp = i; yo = A[yo]; A[i] = temp cambia el valor de i en la segunda declaración, lo que da como resultado un valor i incorrecto para 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 los criterios L1 a L4 anteriores. Reemplazar XOR por suma y resta da varias formulaciones ligeramente diferentes, pero en gran medida equivalentes. Por ejemplo:

vacío AddSwap() no firmado int* x, no firmado int* Sí. ){} si ()x ! Sí.) {} *x = *x + *Sí.; *Sí. = *x - *Sí.; *x = *x - *Sí.; }}

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 + Y no pueda causar un error debido a un número entero Desbordamiento. Por lo tanto, se ve aún más raramente en la práctica que el intercambio XOR.

Sin embargo, la aplicación de AddSwap arriba en el lenguaje de programación C siempre funciona incluso en caso de flujo entero, ya que, según el estándar C, adición y resta de enteros no firmados siguen las reglas de aritmética modular, es decir, se hacen en el grupo cíclico Z/2sZ{displaystyle mathbb {Z} {fnMitbb} {Z} Donde s{displaystyle s} es el número de bits de unsigned int. De hecho, la corrección del algoritmo se debe al hecho de que las fórmulas ()x+Sí.)− − Sí.=x{displaystyle (x+y)-y=x} y ()x+Sí.)− − ()()x+Sí.)− − Sí.)=Sí.{displaystyle (x+y)-(x+y)-y)=y} Esperen en cualquier grupo abeliano. Esto generaliza la prueba del algoritmo de intercambio XOR: XOR es tanto la adición y resta del grupo abeliano ()Z/2Z)s{fnMicrosoft Sans Serif} (que es la suma directa de s copias de Z/2Z{displaystyle mathbb {Z} {Z}).

Esto no se mantiene al tratar con el tipo int type (el valor predeterminado para int ). El desbordamiento entero firmado es un comportamiento indefinido en C y, por lo tanto, la aritmética modular no está garantizada por el estándar, lo que puede conducir a resultados incorrectos.

La secuencia de operaciones en addswap se puede expresar mediante multiplicación de matriz como:

()1− − 101)()101− − 1)()1101)=()0110){begin{pmatrix}1 {} {} {begin{pmatrix}{begin{pmatrix}1 {1} {}} {begin{pmatrix} {} {} {}= {begin{trix}} {trix} {}}}}}}}}}} {}}}}}}}} {begin} {}}}}} {m}= {m}= {m}= {m}= {m}t}=m}t}t}t}t}t}t}t}t}t}t}t}t}t}t}t}t}t} {m}t}cH}cH}cHh}cHh}cH}cH}cH}cH}cH}cH0}cH0}}c}cH

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 de registro óptima. Esto es particularmente importante para los compiladores que utilizan un formulario de asignación único estático 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 derramar registros en la memoria principal. La variante de suma/resta también se puede utilizar para el mismo propósito.

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 derrame de variables es costoso debido al ancho de banda de memoria limitado y la latencia de memoria alta, 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.