350px|thumb|Um algoritmo XOR Swap para trocar nibbles entre variáveis sem o uso de uma terceira variável para armazenar os valores temporariamente. 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 right|thumb|Fluxograma de um XOR Swap. 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 procedure XorSwap( var X, Y: Integer ); begin X := X xor Y; Y := X xor Y; X := X xor Y; end;

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 void xorSwap( int *x, int *y ) { if ( x != y ) { *x ^= *y; *y ^= *x; *x ^= *y;

/* Versão compacta: *x ^= *y ^= *x ^= *y; */

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[sugira tradução melhor]; 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.

Ver também Swap code en Java, C, Python

Categoria:Algoritmos Categoria:Aritmética binária