Swapping with no temporary variable

19Aug06

Many times on programming there is a need of swapping 2 variables, i.e. exchange their value.
An example is (in Pseudocode) :

a=10
b=20
print a,b // 10,20
temp=a
a=b
b=temp
print a,b // 20,10

What if we want to swap a,b without a temp var? (this is also nice as simple programming challenge. We will XOR those variable three times. I will explain this with a small C program (Using C++ visual studio console application):

#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
	int i,j;
	i=10;	// 01010 (10)
	j=20;	// 10100 (20)
	printf("Before: i=%d, j=%dn",i,j);
	i = i ^ j;	// i= 01010 ^ 10100  =11110 (30)
	j = i ^ j;	// j= 11110 ^ 10100  =01010 (10)
	i = i ^ j;  	// i= 11110 ^ 01010  =10100 (20)
	printf("After:  i=%d, j=%dn",i,j);

return 0;
}

The output will be:
Before: i=10, j=20
After: i=20, j=10

Explanation:
I use three assignments:

1st Assignment i = i ^ j;
Binary Decimal Variable
01010 10 -> i
10100 20 -> j
——
11110 30 -> i

2nd Assignment j = i ^ j;

11110 10 -> i
10100 30 -> j
——
01010 10 -> j

3rd Assignment i = i ^ j;

11110 10 -> i
01010 10 -> j
——
10100 20 -> i


NOTE:
There is no overflow problems as long as both variables are below MAXINT.

Technorati Tags: , , ,



7 Responses to “Swapping with no temporary variable”

  1. 1 vinayak

    There is a simpler way of swapping variables. I have described it below:

    let a=5
    b=6
    a=a+b (5+6=11)
    b=a-b(11-6=5)
    a=a-b(11-5=6)
    now a=6 and b=5

  2. Brilliant… I feel like a dufoos now.🙂

  3. 3 vinayak

    I also felt like a dufoos when i did not know the method i described and i was using a temp variable. Keep doing the good work🙂

  4. Then this also work . But there is a bug in above and this method for bigger nos in “C”.

    let a=5
    b=6
    a=a*b (5*6=30)
    b=a/b(30/6=5)
    a=a/b(30/5=6)
    now a=6 and b=5

    But the simple and faster way is

    #define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

  5. 5 Omer Farooq

    This Swap method is most effective of all

    int a=5,b=4;
    a=a XOR b;
    b=a XOR b;
    a=a XOR b;

    The variable will be swaped. U can check the program
    CONTACT:- pureevil105@hotmail.com

  6. 6 varun8

    dear Omer Farooq …

    Xor is the technique used by the author… wat has been written by both r the same…

  7. 7 sangamesh

    1) In an array list all the numbers 75% close to 10
    2) Given a 10 * 10 matrix merge 2 columns which have minimum column sum and repeat the same procedure to reduce a 10*10 matrix to 10*2 matrix
    3)Given sorted list of array A & B produce array C in Sorted manner containing A & B.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: