Algoritmo Xor Swap

Origem: Wikipédia, a enciclopédia livre.

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.

Índice 1 O algoritmo 2 Explicação 3 Exemplos de Código 3.1 Pascal 3.2 C 4 Fluxograma

[editar] O algoritmo

Algoritmos de troca convencionais necessitam de uma variável de armazenamento temporário. Este tipo de algoritmo pode fazer o programador cair em uma armadilha: imagine que um inteiro possa guardar números de 0 até 100. Se x for igual a 70 e y for igual a 100, será passado o limite de armazenamento da variável.

Usando o algoritmo XOR Swap, esse tipo de problema não ocorre e nenhum armazenamento temporário é necessário. O algoritmo é o seguinte:

1. x := x XOR y
2. y := x XOR y
3. 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.

[editar] 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 um ⊕ a = 0 e b ⊕ 0 = b, rende:

1. X = x ⊕ y, Y = y
2. Y = x ⊕ y, Y = x ⊕ y ⊕ y = x
3. X = x ⊕ y ⊕ x = y, Y = x

[editar] Exemplos de Código

[editar] 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.

[editar] C

void xorSwap(int *x, int *y)
{
  if (x != y)
  {
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
  }
}

[editar] Fluxograma