13

Estava estudando operações bit a bit e me deparei com o algoritmo do Xor Swap. Eu entendo o que ele faz (troca o valor de duas variáveis), mas não entendo como ele faz isto, a nível de cálculo e codificação.

Segue o algoritmo em C:

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

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

3 Respostas 3

6

Ele é utilizado para trocar dois valores sem a necessidade de uma variável temporária, utilizando operações xor.

Para entendê-lo é só olhar a tabela do xor e analisar passo-a-passo o algoritmo: inserir a descrição da imagem aqui

Para x = 0b1010 e y = 0b0011:

x = 0b1010 xor 0b0011; // que resulta em x = 0b1001
y = 0b1001 xor 0b0011; // usando o novo valor de x, e y = 0b1010
x = 0b1001 xor 0b1010; // Finalizando com os valores trocados.

Deve-se considerar que essa prática é válida para sistemas antigos e\ou com pouca RAM e para otimizar o uso dos registradores. Para os sistemas atuais, o uso de uma variável temporária é mais apropriado (ou funções próprias do sistema em questão). Como é discutido aqui.

6

Primeiro, vamos lembrar algumas propriedades do XOR (exclusive-OR):

  • A^A = 0
  • elemento neutro: A^0 = A
  • comutativa: A^B = B^A
  • associativa: (A^B)^C = A^(B^C)

Segue uma explicação retirada daqui:

A chave para se convencer de que isso funciona é acompanhar os valores originais de x e y. Seja A o valor original de x (isto é, o valor que x possui antes de executar essas três linhas de código). De mesma forma, seja B o valor original de y.

Podemos comentar cada linha de código para ver o que está acontecendo.

// x == A, y == B
x = x ^ y ;  
 // x == A ^ B, y == B
y = x ^ y ;  
 // x == A ^ B
 // y == (A ^ B) ^ B == A ^ (B ^ B)  (por associatividade)
 //   == A ^ 0  (devido à propriedade z ^ z == 0)
 //   == A      (devido à propriedade z ^ 0 == z)
x = x ^ y ;
 // x == ( A ^ B ) ^ A
 //   == ( A ^ A ) ^ B  (por associatividade/comutatividade)
 //   == 0 ^ B            (devido à propriedade z ^ z == 0)
 //   == B                (devido À propriedade z ^ 0 == z)
 // y == A

Depois que o segundo statement executou, y = A. Depois do terceiro statement, x = B.

3

O que a operação de disjunção exclusiva (XOR) faz é o seguinte:

Digamos que tenhamos uma variável X e Y. Quando eu faço um XOR entre X e Y, o que acontece é, quando os valores são diferentes, retorna-se um bit verdadeiro, quando são iguais retorna-se um bit falso.

No algoritmo XOR swap, o que se faz é:

  1. Criar um "negativo" da variável X em relação a Y;
  2. Faze-se um XOR desse negativo com Y, o que retorna o valor de X;
  3. Faze-se um XOR entre o valor original de X (agora em Y) com o "negativo" de X, o que retorna o valor original de Y.

Se for utilizado como exemplo os valores x = 12 e y = 10 (como no exemplo do link), teremos:

x = 1100 / y = 1010
x = x XOR y
x = 0110 / y = 1010
y = y XOR x
x = 0110 / y = 1100
x = x XOR y
x = 1010 / y = 1100

Basicamente, essa é uma das propriedades da disjunção exclusiva.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .