• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Cypher

[C] Algoritmo swap sem variável auxiliar

9 mensagens neste tópico

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. 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

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

Código

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

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

Edit: ja alterei o código! estava incorrecto o Triton já me tinha avisado só que não tive tempo...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Interessante, mas é preciso ter em atenção que só funciona para números inteiros. Para floating-point ou strings, usa-se o método convencional (com a variável que armazena temporariamente o valor de uma das variáveis a trocar).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Segundo li na Wikipedia inglesa, qualquer compilador moderno, com as devidas optimizações ligadas, consegue detectar um código de swap com variável temporária e optimizar para código mais rápido ainda que este.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Apesar de conhecer esta forma, utilizo sempre o swap com variavel temporária por ser mais intuitivo.

Supostamente esta técnica é um pouco mais rápida do que o swap com variável temporária.

Segundo li na Wikipedia inglesa, qualquer compilador moderno, com as devidas optimizações ligadas, consegue detectar um código de swap com variável temporária e optimizar para código mais rápido ainda que este.

Muito interessante, já me aconteceu de ter 2 porções de código em que usando a supostamente mais rápida, na realidade o programa fica mais lento. Talvez seja uma explicação :thumbsup:

Só uma coisa, o código não está errado ? Não deveria ser:

void xorSwap(int *x, int *y)
{
  if (*x != *y)
  {
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
  }
   
  /* Versão compacta: *x ^= *y ^= *x ^= *y; */
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Só uma coisa, o código não está errado ?

Está, já tinha avisado o Cypher em relação a isso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Apesar de conhecer esta forma, utilizo sempre o swap com variavel temporária por ser mais intuitivo.

Supostamente esta técnica é um pouco mais rápida do que o swap com variável temporária.

Bem para saber isso, só sabendo o tempo que demora a execução de cada tarefa, xor ou cópia de registos. A grande vantagem deste método é mesmo não precisar de variàvel auxiliar, e numa situação em que tenhas os registos todos ocupados este  método é claramente mais rápido uma vez que com o método de variável temporária irias ter que aceder à memória.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tanto quando sei, qualquer operação ao nivel dos bits ( And , Or , Xor , Shifts ) é extremamente rápida por existem no processador circuitos que fazem isto directamente.

Eu penso que o tempo de alocar uma nova variável e a cópia de registos deveria ser mais lento.

Já não digo que "é mais lento" devido aquilo que o Triton referiu :thumbsup:

PS: Só para explicar a razão de não usar esta forma: este código não é intuitivo... se fosse rever uma porção de código feita há uns meses, provavelmente não me ia lembrar que aquilo era um swap (a menos que o utilizasse muitas vezes)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A família de processadores x86 tem uma instrução chamada XCHG que faz a troca de valores entre registos directamente.

Modern optimizing compilers work by translating the code they are given into an internal flow-based representation which they transform in many ways before producing their machine-code output. These compilers are more likely to recognize and optimize a conventional (temporary-based) swap than to recognize the high-level language statements that correspond to a XOR swap. Many times, what is written as a swap in high-level code is translated by the compiler into a simple internal note that two variables have swapped memory addresses, rather than any amount of machine code. Other times, when the target architecture supports it, the compiler can use a single XCHG (exchange) instruction which performs the swap in a single operation.

http://en.wikipedia.org/wiki/XOR_swap_algorithm#The_XCHG_instruction

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora