Algoritmo de intercambio XOR - XOR swap algorithm

Uso del algoritmo de intercambio XOR para intercambiar nibbles entre variables sin el uso de almacenamiento temporal

En programación de computadoras , el exclusivo o intercambio (a veces abreviado como intercambio XOR ) es un algoritmo que usa 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 propiedades de la operación exclusiva o . A veces se discute como una optimización del programa , pero casi no hay casos en los que el intercambio por vía exclusiva o proporcione un beneficio sobre la técnica estándar y obvia.

El algoritmo

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

X := X XOR Y; /* XOR the values and store the result in X */
Y := Y XOR X; /* XOR the values and store the result in Y */
X := X XOR Y; /* XOR the values and store the result in X */

Dado que XOR es una operación conmutativa , X XOR Y o Y XOR X pueden usarse indistintamente en cualquiera de las tres líneas anteriores; sin embargo, cuando el intercambio de tres XOR se codifica en lenguaje ensamblador, esta intercambiabilidad no está disponible dentro de cada línea, porque 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. El algoritmo normalmente corresponde a tres instrucciones de código máquina, representadas por el pseudocódigo correspondiente y las instrucciones de ensamblaje en las tres filas de la siguiente tabla:

Pseudocódigo	Ensamblaje IBM System / 370	montaje x86
`X := X XOR Y`	`XR R1,R2`	`xor eax, ebx`
`Y := Y XOR X`	`XR R2,R1`	`xor ebx, eax`
`X := X XOR Y`	`XR R1,R2`	`xor eax, ebx`

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 mencionado en el primer argumento. Usando el ensamblaje x86, los valores X e Y están en los registros eax y ebx (respectivamente), y xorcolocan el resultado de la operación en el primer registro.

Sin embargo, en la versión en pseudocódigo o de alto nivel o aplicación, el algoritmo falla si x e y utilizar la misma ubicación de almacenamiento, ya que el valor almacenado en ese lugar se pondrá a cero a cabo por la primera instrucción XOR, y después seguir siendo cero; no será "intercambiado consigo mismo". Esto es no lo mismo que si X e Y tienen los mismos valores. El problema viene solamente cuando x y y utilizan la misma ubicación de almacenamiento, en cuyo caso sus valores ya deben ser iguales. Es decir, si x e y utilizan la misma ubicación de almacenamiento, entonces la línea:

X := X XOR Y

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

Prueba de corrección

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

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 : hay una cadena de bits, 0, (de longitud N ) tal que para cualquier ${\ Displaystyle A \ oplus 0 = A}$ ${\ Displaystyle A}$
L4. Cada elemento es su propia inversa : para cada uno , . ${\ Displaystyle A}$ ${\ Displaystyle A \ oplus A = 0}$

Supongamos que tenemos dos registros distintos R1y R2como en la tabla siguiente, 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	${\ Displaystyle A}$	${\ Displaystyle B}$	-
1	`R1 := R1 XOR R2`	${\ Displaystyle A \ oplus B}$	${\ Displaystyle B}$	-
2	`R2 := R1 XOR R2`	${\ Displaystyle A \ oplus B}$	${\ Displaystyle (A \ oplus B) \ oplus B = A \ oplus (B \ oplus B)}$ ${\ displaystyle = A \ oplus 0}$ ${\ Displaystyle = A}$	L2 L4 L3
3	`R1 := R1 XOR R2`	${\ Displaystyle (A \ oplus B) \ oplus A = (B \ oplus A) \ oplus A}$ ${\ Displaystyle = B \ oplus (A \ oplus A)}$ ${\ displaystyle = B \ oplus 0}$ ${\ displaystyle = B}$	${\ Displaystyle \ A}$	L1 L2 L4 L3

Interpretación de á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 matrices 2 × 2 sobre el campo con dos elementos. Por simplicidad, se supone inicialmente que x y y son cada uno de los bits individuales, no se mordió vectores.

Por ejemplo, el paso:

X := X XOR Y

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

Para generalizar donde X e Y no son bits únicos, sino vectores de bits de longitud n , estas matrices de 2 × 2 se reemplazan por matrices de bloques de 2 n × 2 n 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 se abstrae de los problemas de ubicación de almacenamiento y el 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)
  {
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
  }
}

El código primero verifica si las direcciones son distintas. De lo contrario, si fueran iguales, el algoritmo se doblarí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)) /* Doesn't work when a and b are the same object - assigns zero \
                  (0) to the object in that case */
#define XORSWAP(a, b)                                                         \
  ((&(a) == &(b)) ? (a) /* Check for distinct addresses */                    \
                  : 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 incurre en latencia cero. (Esto se denomina eliminación de MOV). Incluso si no hay ningún registro arquitectónico disponible para su uso, 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 orden estrictamente secuencial, anulando cualquier beneficio del paralelismo a nivel de instrucción .

Aliasing

El intercambio de XOR también se complica en la práctica mediante el uso de alias . Si se intenta intercambiar mediante 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 de XOR no debe usarse a ciegas en un lenguaje de alto nivel si es posible el uso de alias.

Se producen problemas similares con la llamada por nombre , como en el dispositivo de Jensen , 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 da como resultado el valor de 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 con los criterios L1 a L4 anteriores. Reemplazar XOR por suma y resta da una formulación ligeramente diferente, pero en gran medida equivalente:

void AddSwap( unsigned int* x, unsigned int* y )
{
  if (x != y)
  {
    *x = *x + *y;
    *y = *x - *y;
    *x = *x - *y;
  }
}

A diferencia del intercambio de XOR, esta variación requiere que el procesador subyacente o el lenguaje de programación utilice un método como 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 ve aún más raramente en la práctica 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 hacen en el grupo cíclico donde está el número de bits de . De hecho, la exactitud del algoritmo se deriva del hecho de que las fórmulas y se mantienen en cualquier grupo abeliano . En realidad, esto es una generalización de 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 ). ${\ Displaystyle \ mathbb {Z} / 2 ^ {s} \ mathbb {Z}}$ ${\ Displaystyle 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 trata del 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 (un compilador conforme con el estándar podría optimizar dicho código, lo que conduce a 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}}}

Ver también

Diferencia simétrica
Lista vinculada XOR
Cifrado Feistel (el algoritmo de intercambio XOR es una forma degenerada de un cifrado Feistel)

Languages

In other projects