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 é:

/** Troca o valor entre duas variáveis inteiras. Ou seja, ao final da função
a variável first irá conter o valor da variável second e vice-versa.
*/
void normalSwap(int &first, int& second)
{
    int third = first;
    first = second;
    second = third; // contém o valor de first
}

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 << "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';
} 

/* 
Saída:
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()
{
    // trocando ints
    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";

    // trocando strings em c
    char str1[50] = "teste de xor", 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;

/** Troca o valor entre duas variáveis inteiras. Ou seja, ao final da função
a variável first irá conter o valor da variável second e vice-versa.
*/
void anormalSwap(int &first, int& second)
{
    first = first ^ second; // first contém first e second juntos
    second = first ^ second; // firstXORsecond XOR second = first
    first = first ^ second; // second = first. logo, firstXORsecond XOR 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? Não? Então sem Postscript dessa vez. E sem bois-cornetas =).