Swap 2

Swap é aquela fatídica rotina que volta e meia estamos usando…


void swap ( int x, int y)
{   int t;
    t = x;
    x = y;
    y = t;
}

Outro dia afirmei que não era possível efetuar um “swap” usando menos do que 3 variáveis. Mas fiquei com esta dúvida na cabeça: será?

Pois é… Bom, descobri que quando as variáveis são inteiras (int, long, char), isto é possível!

void swap ( int x, int y)
{
  x ^= y;
  y ^= x;
  x ^= y;
}

Dizem que isto é um velho truque de assembly… Talvez o Fred possa dissertar sobre isto.

Anúncios

11 comentários sobre “Swap 2

  1. Não seria:

    void swap(int *x, int *y)
    {
      *x ^= *y;
      *y ^= *x;
      *x ^= *y;
    }

    ?

    Existem alguns problemas em usar operações lógicas (XOR) para fazer swap… Em alguns casos, durante a otimização, o compilador pode eliminar completamente uma das operações, causando problemas… No livro Zen and the Art of Graphics Programming”, Michael Abrash mostra que para escrever na memória de vídeo temos que lê-la primeiro, para carregar os “latches”. Isso pode ser feito assim:

    *p |= 0;

    Mas a operação OR com todos os bits zerados é otimizada pelo compilador e retirada completamente do código.

    Eu ficaria com o método padrão, usando a variável temporária…

  2. Outro motivo… se bem que eu não testei… é que o método do XOR é mais lento que o método da variável temporária….

    O primieiro gera 3 operações lógicas e 3 movimentações. O segundo gera 4 movimentações apenas, sem operações lógicas…

    swap1:
      mov eax, DWORD PTR [rsi]
      xor eax, DWORD PTR [rdi]
      mov DWORD PTR [rdi], eax
      xor eax, DWORD PTR [rsi]
      mov DWORD PTR [rsi], eax
      xor DWORD PTR [rdi], eax
      ret
    swap2:
      mov eax, DWORD PTR [rdi]
      mov edx, DWORD PTR [rsi]
      mov DWORD PTR [rdi], edx
      mov DWORD PTR [rsi], eax
      ret
    1. Novamente a intenção aqui é apresentar, off-topic, o uso do xor.
      Também não testei, mas o “truque” vem do próprio assembly.
      Se quiser, pode-se usar um trecho in-line, o que tornaria o código não portável.

  3. Novamente a intenção aqui é apresentar, off-topic, o uso do xor.
    Também não testei, mas o “truque” vem do próprio assembly.
    Se quiser, pode-se usar um trecho in-line, o que tornaria o código não portável.
    Outra coisa: não… o exemplo original vem para o lado blassé, i.e., não usa ponteiros!

  4. Dá para usar a instrução assembly “XCHG” caso esteja sendo executado em uma máquina x86.

    int asm_swap1 (int a, int b);
    int asm_swap2 (void);

    #pragma aux asm_swap1 = \
    ” xchg ebx,edx ” \
    parm [ebx] [edx] value [ebx];
    #pragma aux asm_swap2 = “” \
    value [edx];

    #define swap(a,b) { \
    (a) = asm_swap1 ((a), (b)); \
    (b) = asm_swap2 (); \
    }

  5. Se os dados a serem trocados estiverem nos registros, então não é preciso usar uma 3a variável.
    mov eax,1234 ;num1
    mov ebx,5678 ;num2
    xor ebx,eax
    xor eax,ebx
    xor ebx,eax

    O livro “Hackers Delight” menciona este método dando como referência a IBM.
    abraços

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s