Swapping Variables

Many algorithms, including the world-famous Euclidean, require to swap the values of two variables. So you probably know the following principle.

int x = 8;
int y = 123;
int tmp = x;
x = y;
y = tmp;

However, do you know how to swap the values of two variables without using a temporary variable? If you do, feel free to skip the rest of this article. If you don’t, you’re either not one of my students, or you haven’t been paying attention due to other, more thrilling activities (shame on you!).

Well, there are basically two ways how to swap variables without using temporary memory.

1. PSM (Primary School Math) 😉

x = x + y;
y = x - y;
x = x - y;

or

x = x * y;
y = x / y;
x = x / y;

Homework: Find out why this works!

2. XOR (Exclusive-OR)

An old professor of mine used to say: “There is nothing that you can’t do with XOR”, and he proved to be right.

One characteristic of the XOR function is its ability to undo/redo itself. If you do an XOR operation twice you will get back to the initial situation. If you’re not familiar with this, you may want to read The X-Factor (OR The Power of XOR), 2. OTP (One-Time Pad) Encryption first.

So what we’re gonna do in the first line is to “stir” y into x. Variable x now “contains” both x and y. To retrieve the initial value of x, which is to be written to y, we just have to do the same operation again (see second line). y now contains the initial value of x, whereas x still “contains” both values. In the third line, we retrieve the initial value of y from x by performing the same operation yet again (remember that in this line y contains the initial value of x).

x = x ^ y;
y = x ^ y;
x = x ^ y;

Homework: Try to understand the explanation above. 😉

A warning …

… to all those who are planning to use these cool and nerdy swap methods in practical life!

Please, please. Only use the very first method, involving a temporary variable, in your every day programming projects. There are multiple reasons why you shouldn’t use the “cool” methods:

  • Today’s processors have fast accessible caches (beside other technologies) that make it very unlikely for these methods to have higher runtime efficiency.
  • Saving 4-8 byte of runtime memory isn’t worth any disadvantages.
  • You can give someone a heck of a hard time debugging your program, especially if x and y do not contain the actual values but pointers instead. (Think twice: This someone could be you!)

You cannot believe that what you have learned is totally useless? Well, every discipline of science will come up with useless facts once in a while. And it is exactly this what some people (aka nerds) may find so sexy about science. 🙂

Enjoy!

— Andre M. Maier

Advertisements

About bitjunkie

Teacher, Lecturer, and BITJUNKIE ...
This entry was posted in Bit-Twiddling, Information Theory, Uncategorized and tagged , , , , . Bookmark the permalink.