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

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