swap two numbers

[Abhishek Jha]

hello all,
this has been an interesting topic since long. you can swap two
numbers (say a and b) using temp(as third variable). you can also swap
without using third variable.like[ a=a+b;b=a-b;a=a-b; ]This was also
done in three statements. Can anyon suggest this swapping in anything
less then that.

 

[Pedro Graca]

this has been an interesting topic since long. you can swap two
numbers (say a and b) using temp(as third variable). you can also swap
without using third variable.like[ a=a+b;b=a-b;a=a-b; ]This was also
done in three statements. Can anyon suggest this swapping in anything
less then that.

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

 

[Method Man]

hello all,
this has been an interesting topic since long. you can swap two
numbers (say a and b) using temp(as third variable). you can also swap
without using third variable.like[ a=a+b;b=a-b;a=a-b; ]This was also
done in three statements. Can anyon suggest this swapping in anything
less then that.

[ a=a+b;b=a-b;a=a-b; ] is a bad way to swap two numbers due to possible
overflow. A better method without using a temporary variable is to use the
XOR trick [*] (which works for non-integral types as well). But, the best
way is probably just to use a standard temporary variable and let the
compiler do the optimization.

[*] a^=b; b^=a; a^=b;

 

[tigervamp]

this has been an interesting topic since long. you can swap two
numbers (say a and b) using temp(as third variable). you can also swap
without using third variable.like[ a=a+b;b=a-b;a=a-b; ]This was also
done in three statements. Can anyon suggest this swapping in anything
less then that.

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

This is even worse than the original silliness as it always invokes
undefined behavior.

Rob Gamble

 

[Keith Thompson]

hello all,
this has been an interesting topic since long. you can swap two
numbers (say a and b) using temp(as third variable). you can also swap
without using third variable.like[ a=a+b;b=a-b;a=a-b; ]This was also
done in three statements. Can anyon suggest this swapping in anything
less then that.

C FAQ <http://www.eskimo.com/~scs/C-faq/q10.3.html>, question 10.3.

 

[Kelsey Bjarnason]

this has been an interesting topic since long. you can swap two
numbers (say a and b) using temp(as third variable). you can also swap
without using third variable.like[ a=a+b;b=a-b;a=a-b; ]This was also
done in three statements. Can anyon suggest this swapping in anything
less then that.

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

int a = INT_MAX;
int b = a;

... (a = a+b) whoops.

 

[=?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=]

hello all,
this has been an interesting topic since long. you can swap two
numbers (say a and b) using temp(as third variable). you can also swap
without using third variable.like[ a=a+b;b=a-b;a=a-b; ]This was also
done in three statements. Can anyon suggest this swapping in anything
less then that.

What if a+b overflows ?
And is there any point to do "smart" tricks like this ? If one
needs to swap variables, do it the right way. If there is
anything to gain, trust your compiler to optimize it.

 

[Peter Kord]

[ a=a+b;b=a-b;a=a-b; ] is a bad way to swap two numbers due to possible

overflow. A better method without using a temporary variable is to use the
XOR trick [*] (which works for non-integral types as well). But, the best

^^^^^^^^^^^^^^^^^^^^

What do you mean by this? The trick won't work for floats, doubles or
pointers
for instance.

 

[Malcolm]

"Nils O. Selåsdal"

What if a+b overflows ?
And is there any point to do "smart" tricks like this ? If one
needs to swap variables, do it the right way. If there is
anything to gain, trust your compiler to optimize it.

You're basically right, but not about trusting the compiler. Let's say that
the XOR hack saves a cycle over use of a temporary, due to the architecture
of the instruction set. Seeing that assignment to a temporary is only for
the purposes of swapping is the sort of thing compilers tend not to be good
at, because they don't see the source with a human eye. However is saving a
cycle really worth it? If you are so time critical, wouldn't it be better to
resort to assembly?

 

[Dik T. Winter]

> "Nils O. Selåsdal"
> You're basically right, but not about trusting the compiler. Let's say that
> the XOR hack saves a cycle over use of a temporary, due to the architecture
> of the instruction set. Seeing that assignment to a temporary is only for
> the purposes of swapping is the sort of thing compilers tend not to be good
> at,

Compilers tend to be very good at just that. Using the tmp variable
will much more likely get the optimal sequence:
load a to r1
load b to r2
store r2 to a
store r1 to b
on most machines. Using the xor trick (or whatever) may very well lead
to:
load a to r1
load b to r2
set r1 to r1 ^ r2
set r2 to r2 ^ r1
set r1 to r1 ^ r2
store r1 to a
store r2 to b
on the same machines.

The point is, tell the compiler what you want, do not obfuscate it.

 

[Chris Torek]

"Nils O. Selåsdal"

You're basically right, but not about trusting the compiler. Let's say that
the XOR hack saves a cycle over use of a temporary, due to the architecture
of the instruction set. Seeing that assignment to a temporary is only for
the purposes of swapping is the sort of thing compilers tend not to be good
at, because they don't see the source with a human eye.

No; they see it with one that makes no mistakes, instead.

This is actually a very simple optimization in any compiler that
does live-range analysis of variables. The "live range" of a
variable begins from when it is first assigned and ends at the
last reference to it before it is assigned another value (or the
last reference, if never re-assigned). This means that, for
instance, in code like:

tmp = a; /* line 17 */
a = b;
b = tmp; /* line 19 */
tmp = c; /* line 20 */
c = d;
d = tmp; /* line 22 */
/* code that does not refer to "tmp" again */

the "tmp" variable has two separate live ranges: one covers lines
17 through 19, and the other lines 20 through 22.

Given this information, and assuming that a, b, c, and d are in
processor registers and the CPU has a "swap" instruction for swapping
a pair of registers, it is easy to generate code of the form:

swap rA, rB
swap rC, rD

for these six lines of code. The GNU C compiler does it, for
instance. (Of course, the person who writes the ".md" file for
the machine has to define the swap instruction.)

However is saving a cycle really worth it? If you are so time
critical, wouldn't it be better to resort to assembly?

This is a valid point -- but it turns out that many C programmers
can no longer write "fast assembly code" for modern (pipelined)
processors -- or at least, not as well as compilers with good
pipeline schedulers (gcc3's is far better than gcc2's, for instance).
To beat the compiler, you may need one of those special assembly
programmers stored in the glass cases (with the signs that read
"in case of emergency, break glass").

 

[Jarmo]

hello all,
this has been an interesting topic since long. you can swap two
numbers (say a and b) using temp(as third variable). you can also swap
without using third variable.like[ a=a+b;b=a-b;a=a-b; ]This was also
done in three statements. Can anyon suggest this swapping in anything
less then that.

Trite academic exercises aside, who needs a 'clever' way to swap two
numbers?

 

[=?iso-8859-1?q?Nils_O=2E_Sel=E5sdal?=]

You're basically right, but not about trusting the compiler. Let's say that
the XOR hack saves a cycle over use of a temporary, due to the architecture
of the instruction set. Seeing that assignment to a temporary is only for

Then I would call it a non-optimal compiler. Take a look at
optimized compiler compiler generated assembly, there isn't always that
much resemblance with the corresponding C code

the purposes of swapping is the sort of thing compilers tend not to be
good at, because they don't see the source with a human eye. However is
saving a cycle really worth it? If you are so time critical, wouldn't it
be better to resort to assembly?

Lets just not hope the C compiler does funny things then;
"The order of evaluation of subexpressions within an expression is
undefined."

 

[=?iso-8859-1?q?Nils_O=2E_Sel=E5sdal?=]

Compilers tend to be very good at just that. Using the tmp variable
will much more likely get the optimal sequence:
load a to r1
load b to r2
store r2 to a
store r1 to b

looking at compiler output using a
inline void swap(int *a,int *b);
For 4 real world examples I've tested now, the compiler
optimizes away the entire swap altogether, it just seems to
reorder things so the swap isn't even needed

 

[Dik T. Winter]

> On Sun, 17 Oct 2004 00:24:10 +0000, Dik T. Winter wrote: ....
> looking at compiler output using a
> inline void swap(int *a,int *b);
> For 4 real world examples I've tested now, the compiler
> optimizes away the entire swap altogether, it just seems to
> reorder things so the swap isn't even needed

Oh, yes, for inlined functions that is pretty probable. I have worked
with tuning an Algol 68 compiler that with the probably tuning after
a switch still did know what was where, and optimized branches to
store the same thing in the same place. But that was only 1970s
technology.

 

[Jack Klein]

hello all,
this has been an interesting topic since long. you can swap two
numbers (say a and b) using temp(as third variable). you can also swap
without using third variable.like[ a=a+b;b=a-b;a=a-b; ]This was also
done in three statements. Can anyon suggest this swapping in anything
less then that.

[ a=a+b;b=a-b;a=a-b; ] is a bad way to swap two numbers due to possible
overflow. A better method without using a temporary variable is to use the
XOR trick [*] (which works for non-integral types as well). But, the best
way is probably just to use a standard temporary variable and let the
compiler do the optimization.

[*] a^=b; b^=a; a^=b;

Except of course that it does not work for non-integer types at all,
and may generate a trap representation and thus undefined behavior on
signed integer types.

Works like a charm on all unsigned integer types, though.

 

[Malcolm]

Trite academic exercises aside, who needs a 'clever' way to swap two
numbers?

consider this

int gcf(int x, int y)
{
if(x < y)
swap(x, y);
if(x % y == 0)
return y;
else
return gcf(y, x % y);
}

And this

int gcf(int x, int y)
{
int temp;

if(x < y)
{
temp = x;
x = y;
y = temp;
}

if(x % y == 0)
return y;
else
return gcf(y, x % y);
}

Which one is clearer?

 

[pete]

consider this

int gcf(int x, int y)
{
if(x < y)
swap(x, y);
if(x % y == 0)
return y;
else
return gcf(y, x % y);
}

And this

int gcf(int x, int y)
{
int temp;

if(x < y)
{
temp = x;
x = y;
y = temp;
}

if(x % y == 0)
return y;
else
return gcf(y, x % y);
}

Which one is clearer?

My first impulse after scanning the code, was to say the second one.
The second one, is entirely defined within your post.

I was scanning the code quickly.
When I saw the function call, without even reading it,
my mind said
"put that on that back burner and let's see
what the rest of this code is all about"

If I had been reading more slowly, I would have read the name
of the function and guessed what it meant.
Now that I am really taking my time,
I even realise that swap() is a macro and not a fuction.

If I were debugging the code,
I would have to look up the definition of swap().

swap() is easy to read, but this:

temp = x;
x = y;
y = temp;

is very easy to read.

 

[CBFalconer]

.... snip ...

[*] a^=b; b^=a; a^=b;

Except of course that it does not work for non-integer types at all,
and may generate a trap representation and thus undefined behavior
on signed integer types.

Works like a charm on all unsigned integer types, though.

Except when told to swap an item with itself, when it has a
penchant for zeroing the whole mess in disgust.

 

[Mike Wahler]

--
"I support the Red Sox and any team that beats the Yankees"

"Any baby snookums can be a Yankee fan, it takes real moral
fiber to be a Red Sox fan"

Catch yesterday's game? Yikes!

-Mike
(Another NYY hater). Go Sox!