swap two integers without using a tmp variable?

[Steve]

How do you rewrite the swap function without using a tmp variable in
the swap function????

int main()
{
int x = 3;
int y = 5;

// Passing by reference

cout << "Passed by reference, before" << endl;
cout << "x = " << x << " y = " << y << endl;

swap(x,y);

cout << "Passed by reference, after" << endl;
cout << "x = " << x << " y = " << y << endl;

return 0;
}

void swap(int &x, int &y)
{
int tmp;

tmp = x;
x = y;
y = tmp;
}

 

[Victor Bazarov]

How do you rewrite the swap function without using a tmp variable in
the swap function????

There used to be a popular trick involving XORing the integers in
three steps, which allowed you to avoid having to define a temporary
storage, but it is much less clear than with a temporary.

int a = 42, b = 73;
b = a ^ b;
a = b ^ a;
b = a ^ b;
// here 'a' is 73, 'b' is 42.

However, it's better to rely on std::swap for that.

V

 

[Walter Tross]

Steve 2004-06-22 :

How do you rewrite the swap function without using a tmp variable in
the swap function????

By doing something which could be called cross-xoring, with operator ^=
I leave it as an exercise, since it is fun
(Don't worry about the tmp: remember that auto variables can live in
registers)

Walter Tross

 

[Maxim Yegorushkin]

There used to be a popular trick involving XORing the integers in
three steps, which allowed you to avoid having to define a temporary
storage, but it is much less clear than with a temporary.

int a = 42, b = 73;
b = a ^ b;
a = b ^ a;
b = a ^ b;
// here 'a' is 73, 'b' is 42.

Or one can use regular addition and substruction:

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

 

[After Dark]

Even easier way:

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

ex:

initially: a = 3, b = 7
1 step: a = 10, b = 7
2 step: a = 10, b = 3
3 step: a = 7, b = 3

KISS

 

[Owen Jacobson]

How do you rewrite the swap function without using a tmp variable in
the swap function????

void swap(int &x, int &y)
{
int tmp;

tmp = x;
x = y;
y = tmp;
}

For *this specific case* (well, any integer case, actually -- or even
boolean) there is a shortcut based on the bitwise-XOR (^) operator. In
general you're better off using a temporary, in all but the most
pathological cases, where you're better off operating on pointers.

Working it out is best left as an exercise, because this sounds like
homework.

 

[Karl Heinz Buchegger]

How do you rewrite the swap function without using a tmp variable in
the swap function????

You don't

There is no advantage in doing so.
The popular xor-trick failes if you
try to swap a variable with itself.

The other popular arithmetic tricks
fail, if over- or underflow occours.

So the best thing is: Use a temporary.

 

[Bill Reyn]

This code does the trick, (no temp variable in function swap). But
is it a cheat?

# include <iostream>
using namespace std;
int x = 3; // this are now visible in swap
int y = 5; // this are now visible in swap
int main()
{
// Passing by reference

cout << "Passed by reference, before" << endl;
cout << "x = " << x << " y = " << y << endl;

swap(x,y);

cout << "Passed by reference, after" << endl;
cout << "x = " << x << " y = " << y << endl;

return 0;
}

void swap(int &a, int &b)
{
x = a;
y = b;

}

 

[JKop]

Bill Reyn posted:

This code does the trick, (no temp variable in function swap). But
is it a cheat?

No it doesn't. It's non-functional (The english term, not the C++ term!).

# include <iostream>
using namespace std;
int x = 3; // this are now visible in swap
int y = 5; // this are now visible in swap
int main()
{
// Passing by reference

cout << "Passed by reference, before" << endl;
cout << "x = " << x << " y = " << y << endl;

swap(x,y);

cout << "Passed by reference, after" << endl;
cout << "x = " << x << " y = " << y << endl;

return 0;
}

void swap(int &a, int &b)
{
x = a;

At this point:

x == 3

y = b;

At this point:

y == 5

}

Your code does nothing.

Even if some-one were to call swap(y,x) , it still wouldn't work.


-JKop

 

[Risto Lankinen]

How do you rewrite the swap function without using a tmp variable in
the swap function????

void swap(int &x, int &y)
{
int tmp;

tmp = x;
x = y;
y = tmp;
}

Here is the Risto's Variable Free Recursive Integer Swap(TM):

void swap( int &r,int &s )
{
if( r < s )
{
--s;
swap( r,s );
++r;
}
else if( r > s )
{
--r;
swap( r,s );
++s;
}
}

Here's another old one that a few people found amusing enough
to pass around as a joke:

void swap( Thing &leftHand,Thing &rightHand )
{
try
{
throw leftHand;
}
catch( Thing falling )
{
leftHand = rightHand;
rightHand = falling;
}
}


Enjoy!

- Risto -

 

[Steve]

The xor solution was really elegant. I would not have thought about it
and never knew it could be done this way.
X XOR Y XOR Y = X (assign in y variable, cancel out both Y)
X XOR Y XOR X = Y (assign in x variable, cancel out both X)
Thanks for the help.

 

[Richard Herring]

The xor solution was really elegant. I would not have thought about it
and never knew it could be done this way.
X XOR Y XOR Y = X (assign in y variable, cancel out both Y)
X XOR Y XOR X = Y (assign in x variable, cancel out both X)

And it DOESN'T WORK (no apologies for shouting) if X and Y are both
references to the same object. Don't do it!

 

[Victor Bazarov]

Or one can use regular addition and substruction:

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

Try it with 'a' and 'b' close to INT_MAX.

V

 

[Peter Koch Larsen]

There used to be a popular trick involving XORing the integers in
three steps, which allowed you to avoid having to define a temporary
storage, but it is much less clear than with a temporary.

int a = 42, b = 73;
b = a ^ b;
a = b ^ a;
b = a ^ b;
// here 'a' is 73, 'b' is 42.

However, it's better to rely on std::swap for that.

Very clever! I just tested it:
int i(42);

victors_swap(i,9);

;-)

 

[Peter Koch Larsen]

How do you rewrite the swap function without using a tmp variable in
the swap function????

int main()
{
int x = 3;
int y = 5;

// Passing by reference

cout << "Passed by reference, before" << endl;
cout << "x = " << x << " y = " << y << endl;

swap(x,y);

cout << "Passed by reference, after" << endl;
cout << "x = " << x << " y = " << y << endl;

return 0;
}

void swap(int &x, int &y)
{
int tmp;

tmp = x;
x = y;
y = tmp;
}

For integers, pointers and many other built-in types, theswap function
should just use a temporary. For more complex objects (e.g. std::string), it
can often be an advantage to do a memberwise swap. Actually, this is the way
it must be implemented if swap should have a nothrow guarantee (and it
should!).

/Peter

 

[JKop]

Risto Lankinen posted:

void swap( Thing &leftHand,Thing &rightHand )
{
try
{
throw leftHand;
}
catch( Thing falling )
{
leftHand = rightHand;
rightHand = falling;
}
}

That one really made me laugh!!

-JKop

 

[Mike Smith]

And it DOESN'T WORK (no apologies for shouting) if X and Y are both
references to the same object. Don't do it!

That's simple enough to fix:

void xor_swap(int &a, int &b)
{
if (a != b)
{
b = a ^ b;
a = b ^ a;
b = a ^ b;
}
}

There's still no good reason to do it, of course.

 

[puppet_sock]

And it DOESN'T WORK (no apologies for shouting) if X and Y are both
references to the same object. Don't do it!

Well... You *could* add a self-assignment guard.

Sometimes coders find themselves working on extremely limited hardware.
Like a smoke detector or something. And every variable is taking up
the very limited RAM that was only allowed by having an arm-wrestling
match with the comptroller and the accountant.
Socks

 

[Howard]

And it DOESN'T WORK (no apologies for shouting) if X and Y are both

Well... You *could* add a self-assignment guard.

Sometimes coders find themselves working on extremely limited hardware.
Like a smoke detector or something. And every variable is taking up
the very limited RAM that was only allowed by having an arm-wrestling
match with the comptroller and the accountant.
Socks

Hmmm, seeems to me that adding the code to guard against swapping the same
variable would take more RAM than a temporary variable itself would take.

My guess is this was a homework question. (I had that question as an
extra-credit question in one of my programming classes.) I doubt there's
ever really a good reason to not use a temporary integer variable for
swapping. (And of course, using the std::swap function is even better, if
you're not toooo pressed for space.)

-Howard

 

[Julie]

I doubt there's
ever really a good reason to not use a temporary integer variable for
swapping.

Small footprint embedded systems would be a good place/reason.