swap() function without tmp

[OSHIMA]

Hi,
I found the swap() function without a temporary variable.

void swap(int *x, int *y){
*x ^= *y;
*y ^= *x;
*x ^= *y;
}

So, I wrote the next code that exchange the double.

void dswap(double *x, double *y){
*(int *)x ^= *(int *)y;
*((int *)x + 1) ^= *((int *)y + 1);
*(int *)y ^= *(int *)x;
*((int *)y + 1) ^= *((int *)x + 1);
*(int *)x ^= *(int *)y;
*((int *)x + 1) ^= *((int *)y + 1);
}

But it is dirty. Does it rewrite more simply?

 

[Daniel]

On 13 May 2004 19:57:29 -0700

void swap(int *x, int *y){
*x ^= *y;
*y ^= *x;
*x ^= *y;
}

Beware that this function will not work if *x == *y. I'd say you
should not swap in this case and notify the impossibility somehow. Or
just use a function or a macro that uses a third variable.

Speaking for myself only.

 

[Ben Pfaff]

Hi,
I found the swap() function without a temporary variable.

void swap(int *x, int *y){
*x ^= *y;
*y ^= *x;
*x ^= *y;
}

So, I wrote the next code that exchange the double.

void dswap(double *x, double *y){
*(int *)x ^= *(int *)y;
*((int *)x + 1) ^= *((int *)y + 1);
*(int *)y ^= *(int *)x;
*((int *)y + 1) ^= *((int *)x + 1);
*(int *)x ^= *(int *)y;
*((int *)x + 1) ^= *((int *)y + 1);
}

But it is dirty. Does it rewrite more simply?

This is nonportable, slow, and counterproductive. Use a
temporary, and read the FAQ:

20.15c: How can I swap two values without using a temporary?

A: The standard hoary old assembly language programmer's trick is:

a ^= b;
b ^= a;
a ^= b;

But this sort of code has little place in modern, HLL
programming. Temporary variables are essentially free,
and the idiomatic code using three assignments, namely

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

is not only clearer to the human reader, it is more likely to be
recognized by the compiler and turned into the most-efficient
code (e.g. using a swap instruction, if available). The latter
code is obviously also amenable to use with pointers and
floating-point values, unlike the XOR trick. See also questions
3.3b and 10.3.

 

[Eric]

Hi,
I found the swap() function without a temporary variable.

I would still recommend using a temporary variable.

 

[glen herrmannsfeldt]

void swap(int *x, int *y){
*x ^= *y;
*y ^= *x;
*x ^= *y;
}

So, I wrote the next code that exchange the double.

void dswap(double *x, double *y){
*(int *)x ^= *(int *)y;
*((int *)x + 1) ^= *((int *)y + 1);
*(int *)y ^= *(int *)x;
*((int *)y + 1) ^= *((int *)x + 1);
*(int *)x ^= *(int *)y;
*((int *)x + 1) ^= *((int *)y + 1);
}

Hmm, if there was a memxor() function that would exclusive
or one region of memory with another, then this could be
done somewhat portably. memand() and memor() to complete
the set. Maybe it should be added to C2009.

-- glen

 

[Joona I Palaste]

On 13 May 2004 19:57:29 -0700

Beware that this function will not work if *x == *y. I'd say you
should not swap in this case and notify the impossibility somehow. Or
just use a function or a macro that uses a third variable.

Speaking for myself only.

It won't work if x == y, you mean. If x == y, the first line will
set *x to 0, and the remaining lines will be XORing 0 by 0, yielding 0.
If x != y but *x == *y it can still work.
Imagine *x == 10 and *y == 10.
First line: *x = 10 ^ 10, i.e. *x = 0
Second line: *y = 10 ^ 0, i.e. *y = 10
Third line: *x = 0 ^ 10, i.e. *x = 10
Output: *x == 10 and *y == 10, as requested.

 

[Keith Thompson]

Hi,
I found the swap() function without a temporary variable.

void swap(int *x, int *y){
*x ^= *y;
*y ^= *x;
*x ^= *y;
}

This fails if x and y point to the same int object.

It can also fail if type int has trap representations. I'm not sure
whether it's reliable if the representation is either one's-complement
or sign-magnitude (each of which has two distinct representations for
0) -- and even if it is, it's probably not worth the effort to prove
it.

If your goal is to swap two variables, just use a temporary. If
you're doing this as an intellectual exercise, have fun, but watch out
for the pitfalls.

 

[Case]

So, I wrote the next code that exchange the double.

void dswap(double *x, double *y){
*(int *)x ^= *(int *)y;
*((int *)x + 1) ^= *((int *)y + 1);
*(int *)y ^= *(int *)x;
*((int *)y + 1) ^= *((int *)x + 1);
*(int *)x ^= *(int *)y;
*((int *)x + 1) ^= *((int *)y + 1);
}

How do you know for sure that sizeof double is 2 * sizeof int?

Kees

 

[Nick Keighley]

I found the swap() function without a temporary variable.

void swap(int *x, int *y){
*x ^= *y;
*y ^= *x;
*x ^= *y;
}

basically this is a silly trick. It is also well known. It only works on
scalars. It probably isn't faster than the sane version. And what does this
do?

swap (&a, &a);

So, I wrote the next code that exchange the double.

void dswap(double *x, double *y){
*(int *)x ^= *(int *)y;
*((int *)x + 1) ^= *((int *)y + 1);
*(int *)y ^= *(int *)x;
*((int *)y + 1) ^= *((int *)x + 1);
*(int *)x ^= *(int *)y;
*((int *)x + 1) ^= *((int *)y + 1);
}

But it is dirty. Does it rewrite more simply?

void dswap(double *x, double *y)
{
double t;

t = &a;
&a = &b;
&b = t;
}

 

[Dan Pop]

the set. Maybe it should be added to C2009.

^^^^^
Apparently, there is going to be no such thing. C99 is far too good to
be replaced after a mere decade ;-)

Dan

 

[Dan Pop]

Hi,
I found the swap() function without a temporary variable.

void swap(int *x, int *y){
*x ^= *y;
*y ^= *x;
*x ^= *y;
}

So, I wrote the next code that exchange the double.

void dswap(double *x, double *y){
*(int *)x ^= *(int *)y;
*((int *)x + 1) ^= *((int *)y + 1);
*(int *)y ^= *(int *)x;
*((int *)y + 1) ^= *((int *)x + 1);
*(int *)x ^= *(int *)y;
*((int *)x + 1) ^= *((int *)y + 1);
}

But it is dirty. Does it rewrite more simply?

Before wasting time with such things, ask yourself: what is the point of
not doing the swap the natural way, using a temporary?

The *portable* way of doing what you want to do is to swap the two doubles
on a byte by byte basis. The result is going to be ludicrously slow,
compared to the normal procedure.

The nonportable way of solving your problem is aliasing your doubles with
unsigned long long's and swapping the latter. It relies on a few
assumptions not guaranteed by the standard and on the existence of the
type long long (or some other 64-bit type) on your implementation.

Dan

 

[pete]

basically this is a silly trick. It is also well known.
It only works on scalars.

"scalars" is too general.
Bitwise operations are only defined for integer types.

 

[Dan Pop]

This fails if x and y point to the same int object.

This can be trivially tested.

It can also fail if type int has trap representations. I'm not sure
whether it's reliable if the representation is either one's-complement
or sign-magnitude (each of which has two distinct representations for
0) -- and even if it is, it's probably not worth the effort to prove
it.

Trivially avoided by using pointers to unsigned int instead. Unless we
start introducing padding bits and other nonsense into the picture...

If your goal is to swap two variables, just use a temporary.

Couldn't agree more.

If you're doing this as an intellectual exercise, have fun, but watch out
for the pitfalls.

The more you study it as an intellectual exercise, the more its futility
becomes obvious.

However, memswap() would have made sense in the standard C library, as
there is no portable and efficient method of implementing it in C.

Dan

 

[Beni]

void dswap(double *x, double *y)
{
double t;

t = &a;
&a = &b;
&b = t;
}

I didn't know you could store the address of a variable in a
non-pointer(here double) variable. Or was that a typo?

 

[Daniel]

It won't work if x == y, you mean. If x == y, the first line will
set *x to 0, and the remaining lines will be XORing 0 by 0, yielding
0. If x != y but *x == *y it can still work.

I actually thought both would fail, thanks por pointing that out.

 

[Alex]

(e-mail address removed) (Nick Keighley) wrote in message

I didn't know you could store the address of a variable in a
non-pointer(here double) variable. Or was that a typo?

Should be * instead of & throughout, and either a and b should be x and y
(or y and x) throughout, or x and y should be a and b (or b and a). Other
than that, it was perfect .

Alex

 

[glen herrmannsfeldt]

Apparently, there is going to be no such thing. C99 is far too good to
be replaced after a mere decade ;-)

Or there might not be enough C99 compilers available by 2009?

I was always so disappointed the Fortran didn't keep up
the trend from 66 to 77 with 88 and 99.

-- glen

 

[Keith Thompson]

"scalars" is too general.
Bitwise operations are only defined for integer types.

And personally, I value my sanity too much to try to use bitwise
operators on anything other than unsigned integer types. That's not
to say that you *can't* use bitwise operators on signed integer types,
but it rarely makes sense to do so.

 

[OSHIMA]

Hi,
Thanks a lot of reply messages.

How do you know for sure that sizeof double is 2 * sizeof int?
Kees

It is my mistake. A 'int' means a 'long'.

Hmm, if there was a memxor() function that would exclusive
or one region of memory with another, then this could be
done somewhat portably. memand() and memor() to complete
the set. Maybe it should be added to C2009.
-- glen

A memxor() not implemeted my environment(library) yet.
But it's easy to implement for me. Thanks a valuable
information.

I would still recommend using a temporary variable.
Eric

*portable* way of doing what you want to do is to swap the two doubles
on a byte by byte basis. The result is going to be ludicrously slow,
Dan

Yes, I know my program is slow and tricky.
But, imagine the microchip programming like a PIC.
(which has 64/128 byte's mem only --It is off topic here?)
A double tmp variable needs 8 bytes stack and microchip
has not engough memory. So, I need a double swap() without
tmp rather than a speed.
Don't say 'Use Assembly Language'.

The nonportable way of solving your problem is aliasing
your doubles with unsigned long long's and swapping the latter.

void dswap(double *x, double *y){
*(long long *)x ^= *(long long *)y;
*(long long *)y ^= *(long long *)x;
*(long long *)x ^= *(long long *)y;
}

In my programming environment, it worked correctly and object
code has not use the surplus mem.
Thanks a lot. >> for all

 

[pete]

And personally, I value my sanity too much to try to use bitwise
operators on anything other than unsigned integer types. That's not
to say that you *can't* use bitwise operators on signed integer types,
but it rarely makes sense to do so.

I have only one code example where it is OK
to use a bitwise operator on an int.

The code example is
unsigned mask = ((unsigned char)-1 >> 1) + 1;
for masking the most significant bit of a byte.

The left operand of the shift operator is promoted to either
int or unsigned. In the case when it is promoted to int,
the sign bit is not involved in the operations.