25 de fevereiro de 2009

Trocando Valores entre Duas Variáveis sem uma Auxiliar

Como trocar os valores de duas variáveis sem usar uma terceira? Suponha duas variáveis:

pipe = 1984 e less = 2009

O objetivo é esse:

pipe = 2009 e less = 1984



A solução mais comum é com o uso de uma terceira variável, que serve como auxiliar, como mostrado na listagem 1. O problema deste método é que ele necessita de uma terceira variável, que é descartada logo depois. Este método possui as vantagens de ser o mais simples e universal, uma vez que pode ser aplicado a qualquer tipo de variável (numérico, string, objeto criado pelo usuário, vetor etc.), além de contar com o constante aumento na capacidade de memória dos sistemas computacionais, o que incentiva o seu uso. Contudo, muitas pessoas, inclusive eu, procuram uma forma alternativa para fazer este trabalho.

>>> pipe = 1984
>>> less = 2009
>>> aux = pipe  # Iniciando a troca...
>>> pipe = less
>>> less = aux
>>> pipe
2009
>>> less
1984
>>> 
Listagem 1. Forma comum de realizar a troca.

Desde que eu comecei a programar, encontro esse problema e já tinha me convencido que não era possível resolvê-lo sem a terceira variável, mas hoje eu descobri como. Em vez de usar operadores aritméticos, basta usar um operador lógico: o XOR bit a bit. As operações bit a bit, também conhecidas como bitwise, operam com os valores a nível de bits, comparando ou operando cada bit que compõe o valor da variável. A listagem 2 mostra como isto pode ser feito com Python.

>>> pipe = 1984
>>> less = 2009
>>> pipe = pipe ^ less  # Iniciando a troca...
>>> less = pipe ^ less
>>> pipe = pipe ^ less
>>> pipe
2009
>>> less
1984
>>> 
Listagem 2. Usando XOR para resolver o problema.

Para quem não entendeu, a operação XOR (a.k.a., Disjunção Exclusiva  e OU Exclusivo) tem a característica de retornar True, caso os dois componentes da operação sejam diferentes e False em caso contrário. Para entender melhor isso, veja a tabela 1.


Tabela 1. XOR

Sabendo como o XOR trabalha, podemos analisar o que acontece. Para isso, coloque os números em questão em notação binária e realize a operação de XOR com cada um dos bits que o compõem (veja a figura 1). Na primeira operação, 1984 ^ 2009, o resultado é 25. Isto indica que, ao fazer 1984 ^ 25, resultará em 2009 e ao fazer 2009 ^ 25, resultará em 1984. Assim, guarda-se o resultado da primeira operação na primeira variável e opera-se este resultado com a segunda, atribuindo a esta, o valor obtido, o que deixa a segunda variável com o valor da primeira. Então faz-se operação semelhante para a primeira variável, para que ela fique com o resultado da segunda variável.


Figura 1. Raio X da operação com o XOR.

A vantagem de se utilizar o XOR é a economia de memória associada ao custo de processamento de operações bit a bit, que costuma ser pequeno, além de ser uma forma elegante de resolução do problema. Contudo, pesa contra este método, o fato de que ele não pode ser utilizado com todos os tipos de dados existentes. Em Python, por exemplo, não pode-se utilizá-lo com strings e objetos criados pelo usuário, a não ser que este implemente o método __xor__(self, other) para os tipos de objetos não suportados. Mas mesmo com esta possibilidade, pode ser mais interessante que o programador utilize o primeiro método nestes casos. Em todo caso, vale a pena testar a utilização do XOR para realização desta operação na sua linguagem de programação preferida, com os mais diferentes tipos de dados, para testar sua utilização e se descobrir algo novo, comente!




Fonte: iMasters Fóruns

Leia Também
  • Sobrecarga de Operadores em Python – Para manipular melhor os seus objetos.
  • Modulus 11 – Um algoritmo muito usado para validação de documentos nacionais.
  • Algoritmo de Luhn – Entenda o funcionamento e algumas aplicações deste famoso algoritmo para criação e checagem de dígitos de verificação.

13 comentários:

  1. É importante ressaltar que esse algoritmo não funciona para fazer swap(a, b) se a e b são o _mesmo_ objeto, já que no primeiro xor, a variável vai receber o valor 0 (x ^ x = 0), e os próximos 2 XOR serão 0 ^ 0.

    Uma solução é implementar a função assim:
    void Swap(int *a, int *b) {
    if (*a ^ *b) {
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
    }
    }

    Isso garante que ambos são diferentes (poderia-se testar apenas com a != b, ou *a != *b, mas daquela forma o resultado do xor pode ser aproveitado em alguma eventual otimização).

    []s

    ResponderExcluir
  2. Salve, Coster!
    Acho que não entendi o que você quis dizer com o _mesmo_ objeto.
    Perceba, no caso do exemplo citado, das variáveis pipe e less, as duas não são o mesmo objeto. São do mesmo tipo, mas não são o _mesmo_.
    Será que você quis dizer _mesmo_ tipo?
    Abraço!

    ResponderExcluir
  3. Eu to falando do caso do C/C++, em que um ponteiro aponta para a mesma variável (tipo no meu exemplo, Swap(&a, &a, se não tivesse o teste de igualdade ali).

    De qualquer forma, em Python é bem mais simples fazer swap assim:
    a, b = b, a

    []s

    ResponderExcluir
  4. @Coster
    Agora entendi! Realmente Python tem uma facilidade absurda e este exemplo que você citou, a, b = b, a, ainda funciona com tipos diferentes. Um grande facilitador para o programador.
    Abraço!

    ResponderExcluir
  5. Não seria melhor utilizar só a lógica? =S...
    $a = 5;
    $b = 4;

    $a = $a+$b;
    //a = 9
    $b = $a-$b;
    //9 - 4;
    //b = 5;
    $a = $a - $b;
    //a = 4

    ResponderExcluir
  6. @Felipe Seu exemplo ainda só funciona com números. A solução trazida pelo @Coster, valida, até onde eu saiba, só na linguagem Python, é a mais fácil e flexível de todas:

    >>> a, b = b, a

    Inté! ;-)

    ResponderExcluir
  7. var
    a,b:real

    leia (a)
    leia (b)
    b<-b+a
    a<-b-a
    b<-b-a
    escreval (a,b)

    ResponderExcluir
  8. Sem dúvidas é a forma mais nerd de se trocar duas variáveis, é ótimo pra mostrar pros amigos hehe

    Mas as vantagens desse método parece que terminam ai. Fazendo um teste rápido usando C esse método gastou mais que o dobro do tempo requerido pelo método convencional para realizar um número bem grande de trocas.

    De qualquer forma, boa dica, parabéns! :)

    ResponderExcluir
  9. É, esse método, na minha opinião, serve só como demonstração ou mesmo pra estudo da lógica. Eu não implementaria em um ambiente de produção.

    Abraço!

    ResponderExcluir
  10. O beneficio dessa técnica é instanciar uma variável a menos. Você sempre tem medir os custos de 1) Processamento, 2) Armazenamento/Alocação e 3) Comunicação pra avaliar uma técnica. E essa, privilegia o custo de alocação (de memoria). Você não pode otimizar os 3 ao mesmo tempo. Quando vc avalia tempo (de compilação ou de processamento) você está avaliando apenas um dos custos.

    ResponderExcluir
  11. No qbasic ha uma instrucao chamada swap a,b gostaria de saber se ha uma instrucao eqquivalente no vbasic.

    ResponderExcluir
  12. muito bom, me ajudou muito!!!!

    ResponderExcluir
  13. saca esta:
    var
    a,b = int

    leia (a)
    leia (b)
    escreva "a:" (b)
    escreva "b:" (a)

    ResponderExcluir