Algoritmo de intercambio XOR

Na programación por computador, o intercambio por OR exclusivo (en inglés XOR swap) é un algoritmo que emprega a disxunción exclusiva bit a bit para intercambiar os valores de dúas variábeis. A diferenza do método xeralmente empregado, evita o uso dunha variable temporal para facer o intercambio.

O algoritmo é, principalmente, un xeito de demostrar algunhas propiedades do OR exclusivo. Tense falado do seu uso como unha optimización para os programas, mais practicamente non existe ningún caso onde o intercambio por OR exclusivo proporcione algún beneficio sobre o estándar.

O intercambio convencional de variábeis require o uso dunha variábel temporal de almacenamento. Con todo, usando o algoritmo de intercambio por OR exclusivo, non se precisa ningún tipo de almacenamento temporal. O algoritmo execútase do seguinte xeito:^[1][2]

X := Y XOR X; // Faise un XOR de X e Y e gárdase o resultado en X
Y := X XOR Y; // Faise un XOR do novo X e de Y e gárdase o resultado en Y
X := Y XOR X; // Faise un XOR dos novos X e Y e gárdase o resultado en X

Como XOR é unha operación conmutativa, X XOR Y e Y XOR X poden usarse indistintamente en calquera das tres liñas. Débese ter en conta que nalgunhas arquitecturas o primeiro operando da instrución XOR especifica a localización na que o resultado da operación será almacenado, facendo que non se poidan intercambiar. En xeral o algoritmo correspóndese a tres instrucións máquina, representadas polo seguinte pseudocódigo e instrucións ensamblador na táboa:

X := X XOR Y

XR    R1,R2

xor    eax, ebx

xor x10, x10, x11

Y := Y XOR X

XR    R2,R1

xor    ebx, eax

xor x11, x11, x10

X := X XOR Y

XR    R1,R2

xor    eax, ebx

xor x10, x10, x11

No exemplo de arriba, no código do ensamblador System/370, R1 e R2 son rexistros distintos, e cada operación XR garda o resultado no rexistro nomeado no primeiro argumento. Con ensamblador x86, os valores X e Y están nos rexistros eax e ebx (respectivamente), e xor coloca o resultado da operación no primeiro rexistro. No ensamblador RISC-V, X e Y están nos rexistros x10 e x11, e xor garda o resultado da operación no primeiro operando.

Con todo, no pseudocódigo (ou implementación nunha linguaxe de alto nivel), o algoritmo falla se x e y utilizan a mesma dirección, xa que o valor almacenado naquela dirección será posto a cero pola primeira instrución XOR, e quedará a cero; non será "intercambiada consigo mesmo". Isto non é o mesmo ca ter os mesmos valores en x e y. O problema só xorde cando x e y usan a mesma dirección de almacenamento, caso no que os seus valores xa teñen que ser iguais. Isto é, se x e y usan a mesma dirección de almacenamento, entón a liña:

X := X XOR Y

porá x a cero (pois x = y e entón X XOR Y é cero) e porá y a cero (xa que almacénanse na mesma dirección), facendo que x e y perdan os seus valores orixinais.

Unha operación binaria XOR sobre cadeas de bits de lonxitude ${\displaystyle N}$ mostra as seguintes propiedades (onde ${\displaystyle \oplus }$ denota XOR):

• L1. Conmutatividade: ${\displaystyle A\oplus B=B\oplus A}$
• L2. Asociatividade:${\displaystyle (A\oplus B)\oplus C=A\oplus (B\oplus C)}$
• L3. Elemento neutro: existe unha cadea de bits de lonxitude ${\displaystyle N}$ (0) tal que para todo ${\displaystyle A}$, ${\displaystyle A\oplus 0=A}$
• L4. Cada elemento é o seu propio inverso: para cada ${\displaystyle A}$, ${\displaystyle A\oplus A=0}$.

Supoña que temos dous rexistros distintos R1 e R2 tal como na táboa dabaixo, con valores iniciais A e B respectivamente. Executamos as operacións de abaixo secuencialmente, e reducimos os resultados utilizando as propiedades listadas enriba:

Paso	Operación	Rexistro 1	Rexistro 2	Redució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

Como a operación XOR pode ser interpretada como unha suma binaria e un par de bits poden ser interpretados como un vector nun espazo vectorial bidimensional sobre o campo de dous elementos, os pasos no algoritmo pódense interpretar como multiplicacións por matrices 2×2 sobre o campo con dous elementos. Para simplificar, supoña inicialmente que x e y son un bit cada un, non vectores de bits.

Por exemplo, o paso:

X := X XOR Y

que tamén ten implícito:

Y := Y

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

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

A secuencia de operacións é entón expresado 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}}}$

(traballando con valores binarios, así ${\displaystyle 1+1=0}$), o cal expresa a matriz elemental de cambiar dúas filas (ou columnas) en termos das transveccións (en inglés shears) de engadir un elemento ao outro.

Para xeneralizar a onde X e Y non son bits, se non vectors de lonxitude n, estas matrices 2×2 son substituídas por matrices de bloque 2nx2n como${\displaystyle \left({\begin{smallmatrix}I_{n}&I_{n}\\0&I_{n}\end{smallmatrix}}\right).}$

Estas matrices están operando valores, non variábeis (con direccións de almacenamento), por iso esta interpretación abstráese de problemas con direccións de almacenamento e do problema de ter ambas variábeis na mesma dirección.

Unha función de C que aplica o algoritmo de intercambio XOR:

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

O código primeiro comproba se os enderezos das variábeis son distintos e utiliza unha cláusula de garda para saír da función se son iguais. Se non se controlara, en caso de ser iguais, o algoritmo executaría un triplo *x ^= *x, resultando en cero. O algoritmo de intercambio XOR tamén pode ser definido cunha macro:

#define XORSWAP_UNSAFE(a, b)                                                   \
  ((a) ^= (b), (b) ^= (a),                                                     \
   (a) ^= (b)) /* Non funciona cando a e b son o mesmo obxecto - asigna cero   \
                  (0) ao obxecto nese caso */
#define XORSWAP(a, b)                                                          \
  ((&(a) == &(b)) ? (a) /* Comproba que as direccións sexan distintas */       \    
                  : XORSWAP_UNSAFE(a, b))

En arquitecturas de computadoras modernas, a técnica de XOR pode ser máis lenta ca utilizar unha variábel temporal para facer o intercambio. Polo menos nas CPUs x86 recentes, tanto en AMD coma en Intel, moverse entre rexistros regularmente xera cero latencia (isto é chamado eliminación MOV). Incluso se non hai ningún rexistro estructural dispoñible, a instrución XCHG será polo menos tan rápida coma tres instrucións XOR executadas xuntas. Outra razón é que as CPUs modernas executan instrucións en paralelo empregando segmentación. Na técnica XOR, as entradas de cada operación dependen dos resultados da operación anterior, polo que teñen que ser executadas secuencialmente, perdendo calquera beneficio do paralelismo a nivel de instrución.^[3]

O intercambio XOR tamén é complicado na práctica polo aliasing. Se se intenta facer un intercambio XOR dos contidos dunha dirección consigo mesmo, o resultado é que a dirección é posta a cero e o seu valor pérdese. Por tanto, o intercambio XOR non debe ser empregado ás cegas nunha linguaxe de alto nivel se o aliasing é posíbel. Este problema non aplica se a técnica é utilizada en ensamblador para intercambiar os contidos de dous rexistros.

Ocorren problemas similares coa chamada por nome, coma no Dispositivo de Jensen, onde intercambiar i e A[i] por medio dunha variábel temporal deriva en resultados incorrectos debido a seren argumentos relacionados:

temp = i;
i = A[i]; 
A[i] = temp;

muda o valor de i na segunda liña, o que resulta no valor incorrecto i para A[i] na terceira liña.

O principio subxacente do algoritmo de intercambio por XOR pode ser aplicado a calquera operación que cumpla cos criterios L1 a L4 xa mencionados. Substituíndo XOR pola suma e a resta obtemos varias formulacións lixeiramente diferentes, mais en gran parte equivalentes. Por exemplo:^[4]

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

Ao contrario que co intercambio XOR, esta variación require que o procesador subxacente ou que a linguaxe de programación empregue un método como a aritmética modular ou a precisión arbitraria para garantir que o cómputo de X + Y non pode causar erros debido ao desbordamento de enteiros. Por tanto, é visto incluso máis raramente na práctica ca o intercambio XOR.

Con todo, a implementación de AddSwap na linguaxe de programación C sempre funciona, mesmo en caso de desbordamento de enteiros, xa que, segundo o estándar de C, a suma e a resta de enteiros sen signo seguen as regras da aritmética modular, e dicir, realízanse no grupo cíclico ${\displaystyle \mathbb {Z} /2^{s}\mathbb {Z} }$ onde ${\displaystyle s}$ é o número de bits do unsigned int. De feito, a corrección do algoritmo baséase no feito de que as fórmulas ${\displaystyle (x+y)-y=x}$ e ${\displaystyle (x+y)-((x+y)-y)=y}$ cúmprense en calquera grupo abeliano. Isto xeneraliza a proba para o algoritmo do intercambio XOR: XOR é tanto a suma como a resta no grupo abeliano ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{s}}$ (o cal é a suma directa de s copias de ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$).

Isto non se cumpre ao traballar co tipo signed int (o predeterminado para int). O desbordamento de enteiros con signo é un comportamento indefinido en C, polo que o estándar non garante a aritmética modular, o que pode levar a resultados incorrectos.

A secuencia de operacións en AddSwap pode ser expresada como multiplicación de matrices:

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