Swapping with no temporary variable

Posted by levoltz on August 19, 2006 in How-To | 7 Comments

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: coding, swapping, c++, hacks

Google Web Search Features

Subscribe to Comments RSS Feed in this post

7 Responses

vinayak
August 21, 2006 at 8:56 am

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

bothack
August 21, 2006 at 3:54 pm

Brilliant… I feel like a dufoos now.

vinayak
August 22, 2006 at 5:39 am

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

rskumaran
September 20, 2006 at 5:28 pm

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)))

Omer Farooq
October 18, 2006 at 1:34 am

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

varun8
April 5, 2007 at 8:09 am

dear Omer Farooq …

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

sangamesh
November 6, 2008 at 11:25 am

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.