Gambi do dia: swap com apenas duas variáveis

Este artigo é uma reedição de meu blogue antigo, guardado para ser republicado durante minhas miniférias. Esteja à vontade para sugerir outros temas obscuros sobre a linguagem C ou C++ de sua preferência. Boa leitura!

Essa interessantíssima questão veio do meu amigo Kabloc: como trocar o valor entre duas variáveis do tipo int sem utilizar uma variável intermediária? O algoritmo ordinário para um swap entre tipos inteiros é:

   void normalSwap(int &first, int& second)
   {
     int third = first;
     first = second;
     second = third;
   }
   int main()
   {
     int first = 13;
     int second = 42;
     cout << "first: " << first 
       << ", second: " << second << endl;
     normalSwap(first, second);
     cout << "first: " << first 
       << ", second: " << second << endl;
   } 
   Saída:
   first: 13, second: 42
   first: 42, second: 13

Uma das soluções que eu conheço é utilizar o operador de ou exclusivo, o conhecido XOR. Esse operador binário tem a não pouco bizarra habilidade de armazenar dois padrões de bits dentro de um mesmo espaço de armazenamento. Se você tiver um dos dois padrões, conseguirá o segundo. Relembremos sua tabela verdade:

   void xorTable()
   {
     cout 
       << "-----------\n"
       << " XOR Table\n"
       << "-----------\n"
       << "0 XOR 0 = " << ( 0 ^ 0 ) << '\n'
       << "1 XOR 0 = " << ( 1 ^ 0 ) << '\n'
       << "0 XOR 1 = " << ( 0 ^ 1 ) << '\n'
       << "1 XOR 1 = " << ( 1 ^ 1 ) << '\n'
     ;
   } 
   -----------
    XOR Table
   -----------
   0 XOR 0 = 0
   1 XOR 0 = 1
   0 XOR 1 = 1
   1 XOR 1 = 0

Ou seja, imagine que temos o valor 1 e o valor 0. Armazenando os dois juntos com XOR obtemos 1, já que:

   1 (primeiro padrão) XOR 0 (segundo padrão) = 1 (padrões juntos)

Mais tarde, se quisermos obter o primeiro padrão, usamos o segundo:

   1 (padrões juntos) XOR 0 (segundo padrão) = 1 (primeiro padrão)

Para obter o segundo padrão é só utilizar o primeiro obtido:

   1 (padrões juntos) XOR 1 (primeiro padrão) = 0 (segundo padrão)

Calcule a mesma operação com as quatro combinações possíveis e verá que podemos sempre reaver os dados partindo de um dos padrões. Como o cálculo independe do número de bits, já que operadores bit a bit operam um bit de cada vez, podemos usar a mesma técnica para juntar dois inteiros, duas strings, dois "qualquer coisa armazenada numa seqüência de zeros e uns":

   template<
     typename T1, 
     typename T2, 
     typename T3
   >
   void universalXor(
     const T1& first, 
     const T2& second, 
     T3& result
   )
   {
     typedef unsigned char byte;
     const byte* pFirst = 
       reinterpret_cast<const byte*>
       (&first);
     const byte* pSecond = 
       reinterpret_cast<const byte*>
       (&second);
     byte* pResult = 
       reinterpret_cast<byte*>
       (&result);
     for( size_t i = 0; 
       i < sizeof(first) 
         && i < sizeof(second);
       ++i )
     {
       pResult[i] = pFirst[i] ^ pSecond[i];
     }
   }
   int main()
   {
     int x = 13, y = 42;
     cout << "x: " << x 
       << ", y: " << y << '\n';
     universalXor(x, y, x);
     universalXor(x, y, y);
     universalXor(x, y, x);
     cout << "x: " << x 
       << ", y: " << y << "\n\n";
     char str1[50] = "teste de xor";
     char str2[50] = "aceita strings!";
     cout << "str1: " << str1 
       << ", str2: " << str2 << '\n';
     universalXor(str1, str2, str1);
     universalXor(str1, str2, str2);
     universalXor(str1, str2, str1);
     cout << "str1: " << str1 
       << ", str2: " << str2 << '\n';
     return 0;
   } 
   Saída:
   x: 13, y: 42
   x: 42, y: 13
   str1: teste de xor, str2: aceita strings!
   str1: aceita strings!, str2: teste de xor

Essa técnica é uma das mais básicas -- se não for a mais -- de criptografia simétrica. O primeiro padrão faz o papel de texto aberto, o segundo banca a senha e o terceiro será o texto encriptado. Para "desencriptar" o texto é necessária a senha (e se você souber qual o texto original, saberá a senha).

Mas, voltando ao nosso problema original, podemos trocar duas variáveis inteiras usando a técnica do XOR. Em claro:

   #include <iostream>
   using namespace std;
   void anormalSwap(int &first, 
     int& second)
   {
     first = first ^ second;
     second = first ^ second;
     first = first ^ second;
   }
   int main()
   {
     int first = 13;
     int second = 42;
     cout << "first: " << first 
       << ", second: " << second << endl;
     anormalSwap(first, second);
     cout << "first: " << first 
       << ", second: " << second << endl;
   } 
   Saída:
   first: 13, second: 42
   first: 42, second: 13

Bom, preciso dizer que isso é uma gambi das grossas? Preciso dizer que não uso isso no meu dia a dia, até porque swap é uma função já consagrada da STL chamada std::swap? Não? Então sem Postscript dessa vez. E sem bois-cornetas =).