A Curious Economic Swap

• Download demo - 65.8 KB
• Download source code - 2.26 KB

Introduction

This articles has code to answer the following question: how to interchange the value between a couple of variables, of type int, without using an intermediate variable?

Beginning to think

A trivial algorithm for a swap between integer types is:

/** Changes the value between two integer variables. In other words, in the end of
the function the first variable will have the second variable value and vice-versa.
*/
void normalSwap(int &first, int& second)
{

   int third = first;
   first = second;
   second = third; // first variable value into second one
}

int main()
{
   int first = 13;
   int second = 42;

   cout << "first: " << first << ", second: " << second << endl;
   normalSwap(first, second);
   cout << "first: " << first << ", second: " << second << endl;
}

Output:

first: 13, second: 42
first: 42, second: 13

One of the solutions that must exist (at least I know one) is to use the XOR operator. This binary operator has the not-so-trivial feature of keeping two bit patterns inside only one storage space. If you have one or two patterns, you get the second. Let's remember the truth table:

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

Ouput:

XOR Table
â€"â€"â€"
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
1 XOR 1 = 0

In other words, imagine we have values 1 and 0. Keeping both using XOR, we get 1, since:

1 (first pattern) XOR 0 (second pattern) = 1 (patterns together)

Later, we can get the first pattern using the second:

1 (patterns together) XOR 0 (second pattern) = 1 (first pattern)

In order to get the second pattern, we just have to use the first one:

1 (patterns together) XOR 1 (first pattern) = 0 (second pattern)

Use the same logic in the four possible combinations, and you will see we can always get both patterns using one of them. As the logic is a bit number independent since bit operators use one bit at a time, we can extend the technique to put together two integers, two strings, and even "two things stored in a sequence of ones and zeros":

template<typename>
void universalXor(const T& first, const T& second, T& result)
{
   typedef unsigned char byte;

   const byte* pFirst = reinterpret_cast<const>( &first );
   const byte* pSecond = reinterpret_cast<const>( &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];
}

That is the most basic way of symmetric-key algorithm. The first pattern has the role of the plain text, the second pattern has the role of a password, and the third one will be the obfuscated text. In order to see the plain text, we need the password.

Using the Code

The code is straightforward. The code just needs to call the function like in an ordinary swap.

int main()
{
   // swaping 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";

   // swaping strings
   char str1[50] = "xor test", str2[50] = "we accept 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;
}

Output:

x: 13, y: 42
x: 42, y: 13str1: xor test, str2: we accept strings!
str1: we accept strings!, str2: xor test

Points of Interest

I think it is worth saying that this is just a funny code technique, not a professional production code. In other words, it's a code to learn about some concepts and to use the concepts to make something more useful.