Algoritmo de intercambio XOR

alt=With three XOR operations the binary values 1010 and 0011 are exchanged between variables.|miniatura|Uso do algoritmo de intercambio XOR para intercambiar nibbles (4 bits) entre variábeis sen o uso de almacenamento temporal
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 algoritmo 
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:
```pascal
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: 

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, *x*a 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:
```pascal
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.

## Proba de corrección 
Unha operación binaria *XOR* sobre cadeas de bits de lonxitude N mostra as seguintes propiedades (onde \oplus denota *XOR*):

* **L1**. Conmutatividade: A \oplus B = B \oplus A 
* **L2**. Asociatividade:(A \oplus B) \oplus C = A \oplus (B \oplus C) 
* **L3**. Elemento neutro: existe unha cadea de bits de lonxitude N (0) tal que para todo A, A \oplus 0 = A 
* **L4**. Cada elemento é o seu propio inverso: para cada A, 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:

### Interpretación na álxebra lineal 
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:
```pascal
X := X XOR Y
```
que tamén ten implícito:
```pascal
Y := Y
```
corresponde á matriz \left(\begin{smallmatrix}1 & 1\\0 & 1\end{smallmatrix}\right) como

: \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:

: 
\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í 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\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.

## Exemplo de código 
Unha función de C que aplica o algoritmo de intercambio XOR:
```c
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:
```c
#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))
```

## Razóns para evitalo na práctica 
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.

### Aliasing 
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:  
```c
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.

## Variacións 
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:
```c
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 \mathbb Z/2^s\mathbb Z onde 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 (x + y) - y = x e (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 (\mathbb Z/2\mathbb Z)^{s} (o cal é a suma directa de *s* copias de \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:

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

## Notas