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