# Algoritmo XOR Swap

XOR Swap é um algoritmo que usa a função lógica Ou Exclusivo para trocar os valores de duas variáveis do mesmo tipo, sem usar armazenamento temporário. Ele utiliza a propriedade de que (A XOR B) XOR B = A. Como ele utiliza a função booleana XOR, o algoritmo só irá funcionar com números escritos na base binária. Como computadores só usam números binários, é um bom método a ser usado em programação.

## O algoritmo

Algoritmos de troca convencionais necessitam de uma variável de armazenamento temporário. Já com o algoritmo XOR Swap, nenhum armazenamento temporário é necessário. O algoritmo é o seguinte:
* x := x XOR y
* y := x XOR y
* x := x XOR y
O algoritmo corresponde geralmente a três instruções em Linguagem de máquina. Por exemplo, em código assembly para o System/370, seria:
    XOR R1, R2
    XOR R2, R1
    XOR R1, R2
onde R1 e R2 são registradores e a operação XOR coloca o resultado no primeiro argumento. Para programadores assembly esse algoritmo é particularmente interessante por sua eficiência e performance. Ele elimina o uso de registrador intermediário, que é um recurso limitado em programação em linguagem de máquina. Ele também elimina dois ciclos de acesso à memória, que são caros se comparados com uma operação no registrador.

## Explicação

Por exemplo, vamos supor que tenhamos dois valores, X = 12 e Y = 10. Em binário teremos
    X = 1 1 0 0
    Y = 1 0 1 0
Agora, realizaremos um OU Exclusivo entre X e Y para obter 0 1 1 0 e armazenaremos em X. Agora nós temos
    X = 0 1 1 0
    Y = 1 0 1 0
Realizamos o OU Exclusivo entre X e Y novamente para obter 1 1 0 0 - armazenaremos em Y, e agora teremos
    X = 0 1 1 0
    Y = 1 1 0 0
Realizamos o OU Exclusivo entre X e Y novamente para obter 1 0 1 0 - armazenaremos em X, e teremos
    X = 1 0 1 0
    Y = 1 1 0 0
Os valores foram trocados, e o algoritmo trabalhou apenas sobre estas instâncias.
Em geral, porém, se chamarmos o valor inicial de X = x e o valor inicial de Y = y, então realizando as passos acima, usando ⊕ para clarear o OU Exclusivo, e lembrando que 1 ⊕ a = 0 e b ⊕ 0 = b, rende:
* X = x ⊕ y, Y = y
* Y = x ⊕ y, Y = x ⊕ y ⊕ y = x
* X = x ⊕ y ⊕ x = y, Y = x

## Exemplos de Código
### Pascal

Essa função não trabalhará quando X e Y estiverem na mesma posição de memória. Por exemplo, XorSwap( var1, var1 ) falhará: isso irá atribuir o valor zero para var1 depois da primeira declaração, e as declarações seguintes irão preservar o valor zero.

### C
## Razões para se usar na prática

Na maioria das situações práticas, o algoritmo de troca simples, com o uso de uma variável temporária, é mais eficiente que o algoritmo XOR swap. Situações práticas nas quais o uso do XOR swap é adequado incluem:
* Em um processador cujo conjunto de instruções permite que o XOR swap seja codificado em um número menor de bytes;
* Quando há poucos registradores disponíveis$^{[sugiratraduçãomelhor]}$;
* Em microcontroladores com pouca memória RAM disponível.
Como essas situações são raras, normalmente o uso de XOR swap não oferece um nível de otimização tão grande quanto o algoritmo de troca convencional.

## Razões para evitar seu uso na prática

A maioria dos modernos compiladores pode otimizar a variável temporária usada no algoritmo de troca convencional, sendo que, com esse algoritmo, é usada a mesma quantidade de memória e o mesmo número de registradores que o XOR swap, e é no mínimo tão rápido quanto, e, frequentemente, mais rápido que o mesmo. Além disso, o código do XOR swap é muito menos legível, e completamente obscuro para um programador desfamiliarizado com essa técnica.
Nas arquiteturas de CPU mais modernas, a técnica de XOR é consideravelmente mais lenta do que o uso de variável auxiliar para a troca de valores. Uma das razões disso é que as CPUs modernas procuram executar as instruções em paralelo através de pipelines. Na técnica de XOR, a entrada de cada operação depende do resultado da operação anterior. Logo, as instruções devem ser executadas em uma ordem estritamente sequencial. Se a eficiência for algo de muita importância, é recomendável testar e comparar as velocidades de execução de ambas as técnicas na arquitetura de destino.

### Nome alternativo

O uso de XOR swap é também complicado quando ocorre a nomeação alternativa (aliasing) de endereço. Como foi visto nos exemplos de código acima, quando são usados ponteiros, e ambos os ponteiros apontam para o mesmo endereço de memória, a primeira instrução do algoritmo faz com que a localização seja zerada, e o valor é perdido.