Ferramentas de Usuário

Ferramentas de Site


algoritmo:algoritmo_swap_sem_variavel_auxiliar

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. Utiliza-se a propriedade de que (A XOR B) XOR B = A. Como se utiliza a função booleana XOR, o algoritmo só irá funcionar com números escritos na base binária. Como os 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. Este tipo de algoritmo pode fazer o programador cair numa 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 pela sua eficiência e performance. O algoritmo elimina o uso de registrador intermediário, que é um recurso limitado de programação em linguagem de máquina. Também elimina dois ciclos de acesso à memória, que são caros se comparados com uma operação no registrador.

Explicação do algoritmo

Por exemplo, vamos supor que há dois valores, X = 12 e Y = 10. Em binário são:

  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 armazena-se em X. Agora fica

  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 – armazena-se em Y, e agora fica

  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 – armazena-se em X, e agora fica

  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

Implementação

C

void xorSwap(int *x, int *y)
{
  if (*x != *y)
  {
   *x ^= *y;
   *y ^= *x;
   *x ^= *y;
  }
}
algoritmo/algoritmo_swap_sem_variavel_auxiliar.txt · Última modificação em: 2018/05/14 21:37 (edição externa)