Saturday, July 7, 2007

Write a C program to swap two variables without using a temporary variable.

This questions is asked almost always in every interview.

The best way to swap two variables is to use a temporary variable.


int a,b,t;

t = a;
a = b;
b = t;




There is no way better than this as you will find out soon. There are a few slick expressions that do swap variables without using temporary storage. But they come with their own set of problems.


Method1 (The XOR trick)


a ^= b ^= a ^= b;


Although the code above works fine for most of the cases, it tries to modify variable 'a' two times between sequence points, so the behavior is undefined. What this means is it wont work in all the cases. This will also not work for floating-point values. Also, think of a scenario where you have written your code like this



swap(int *a, int *b)
{
*a ^= *b ^= *a ^= *b;
}


Now, if suppose, by mistake, your code passes the pointer to the same variable to this function. Guess what happens? Since Xor'ing an element with itself sets the variable to zero, this routine will end up setting the variable to zero (ideally it should have swapped the variable with itself). This scenario is quite possible in sorting algorithms which sometimes try to swap a variable with itself (maybe due to some small, but not so fatal coding error). One solution to this problem is to check if the numbers to be swapped are already equal to each other.


swap(int *a, int *b)
{
if(*a!=*b)
{
*a ^= *b ^= *a ^= *b;
}
}




Method2

This method is also quite popular


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


But, note that here also, if a and b are big and their addition is bigger than the size of an int, even this might end up giving you wrong results.



Method3

One can also swap two variables using a macro. However, it would be required to pass the type of the variable to the macro. Also, there is an interesting problem using macros. Suppose you have a swap macro which looks something like this


#define swap(type,a,b) type temp;temp=a;a=b;b=temp;



Now, think what happens if you pass in something like this


swap(int,temp,a) //You have a variable called "temp" (which is quite possible).



This is how it gets replaced by the macro


int temp;
temp=temp;
temp=b;
b=temp;


Which means it sets the value of "b" to both the variables!. It never swapped them! Scary, isn't it?


So the moral of the story is, dont try to be smart when writing code to swap variables. Use a temporary variable. Its not only fool proof, but also easier to understand and maintain.

17 comments:

kai said...

"swap(int *a, int *b)
{
if(*a!=*b)
{
*a ^= *b ^= *a ^= *b;
}
}"

my guess is that "*a ^= *b ^= *a ^= *b;" will still work for "*a==*b", but the test should be if(a!=b) so we are not zero out in place.
maybe i'm too much rely on modern compiler, i'll need to dig to find what translated in machine code for a^= b ...

Artan said...

Actually, I don't think the check is necessary and *a^=*b^=*a^=*b works in all cases.
Suppose a = 2 and b = 2 and rewriting the expression like this:
a = a ^ b = 2 ^ 2 = 0
b = b ^ a = 2 ^ 0 = 2
a = a ^ b = 0 ^ 2 = 2

Is there something I'm not understanding in your concern Vijay?

Anonymous said...

This is how it gets replaced by the macro


int temp;
temp=temp;
temp=b;
b=temp;
?????????????????????? and a where is?

Anonymous said...

I am suggesting one more solution to this problem. It is also quite good. Before giving first of all I would like to pay thanks to this community. I am new means this is my first day but way is really make me churn me.

a=5,b=2
a=((a+b)-(a=b))

Salil said...

The above given post has need a correction it should be :
a=((a+b)-(b=a))
now it will work fantastically no doubt.....

Krishnakanth P said...

KK

try the following, it will work fine in all the cases

#define swap(a,b) (((a)!=(b))?a^=b^=a^=b:a)

Prabodha said...

int x=8,y=10;
x=x+y;
y=x-y;
x=x-y;
printf("%d%d" x,y);

whanson said...

what about a function that passes the values and the address?

swap( int x, int y, int *px, int *py )
{
*px = y;
*py = x;
}

doesn't use any temporary variable.

Anonymous said...

swap( int x, int y, int *px, int *py )

doesn't use any temporary variable.


.. Because you already have two (probably stack allocated) temporary variables given to you in the formal parameters.

Hasitha said...

Extra ordinary website, its really usefulllll

Jhammatian said...

int a = 2, b = 5;

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

Anonymous said...

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

Unknown said...

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

Anonymous said...

Odd, but in 20 years of programming with C I've never ever needed to do this. Instead of this question why don't you post some things that actually show you know how to ship software.

Anonymous said...

You fucking curry-n*ggrs, you think because you memorize a few interview questions, that you have the same experience as someone that's been doing this for years. And then you show up at some job thinking that you know everything, when you really don't know shit..

Anonymous said...

Attractive component of content. I simply stumbled upon your
blog and in accession capital to say that I acquire actually loved
account your blog posts. Anyway I will be subscribing for your
augment and even I achievement you get admission to consistently quickly.


my website :: how much should i weigh for my age and height

Anonymous said...

I'm not sure exactly why but this site is loading extremely slow for me. Is anyone else having this issue or is it a problem on my end? I'll check back later on and see if the
problem still exists.

my site - waist to height ratio calculator