Swapping integers

Advertisemen

The typical way to swap two integers would be with the use of a temporary variable:

int a=5,b=8,temp;

temp=a;

a=b;

b=temp;

Although an interview question can ask you how to do that without introducing a temporary variable, the answer is:

a=a+b;
b=a-b;

a=a-b;

Which can be simplified into one line:

a = (a-(b=(a=a+b)-b));

I want to check now, which method takes the least time, I expect it to be the temporary variable method as there is no calculation. I tested each method with 1,000,000,000 (one billion!) swaps:

#include <iostream>

#include <ctime>

using namespace std;

int main()

{

       clock_t startTime,endTime;

      

       startTime = clock();

      

       //temp var method

       for (int i=0;i<1000000000;i++)

       {

              int a=i,b=i+1,temp;

              temp=a;

              a=b;

              b=temp;

       }

       endTime = clock();

       cout << endTime - startTime << endl;

       startTime = clock();

       //calculation method

       for (int i=0;i<1000000000;i++)

       {

              int a=i,b=i+1;

              a = (a-(b=(a=a+b)-b));

       }

       endTime = clock();

       cout << endTime - startTime << endl;

       return 0;

}

The temporary variable methods takes 3132ms while the calculation method takes 3303ms. 

However, using the XOR swap algorithm integers can be swapped using bitwise operations:

int a = 123,b = 456;

a=a^b;

b=a^b;

a=a^b;

Testing this with a billion integer swaps:

#include <iostream>

#include <ctime>

using namespace std;

int main()

{

       clock_t startTime, endTime;

       startTime = clock();

       //bitwise method

       for (int i=0;i<1000000000;i++)

       {

              int a = i,b = i+1;

              a=a^b;

              b=a^b;

              a=a^b;

       }

       endTime = clock();

       cout<< endTime - startTime <<endl;

       return 0;

}

It takes 3278ms - slower than a temporary variable, but faster than the calculations. And the XOR swap can also be compacted to one line: 

a=a^(b=(a=(a^b))^b);

Advertisemen