Swap two integers without using temporary variable

[indrawati.yahya]

OK, before you all stab me with your OT pitchfork, I just want to
mention that this question is indeed related to c.l.c++. My question
is, does the well-known method to swap two integers produce undefined
behaviour in c++? The method is:

a ^= b ^= a ^= b;

It's a clever trick, but I have a feeling something may go wrong if I
use it in C++, although quick tests with a few compilers produce
correct output. So is the code guaranteed to work correctly on all
compilers? Thanks.

[Kai-Uwe Bux]

in************* @gmail.com wrote:

OK, before you all stab me with your OT pitchfork, I just want to
mention that this question is indeed related to c.l.c++. My question
is, does the well-known method to swap two integers produce undefined
behaviour in c++? The method is:

a ^= b ^= a ^= b;

If you write it on a single line, it would appear to be UB since you modify
the variable a twice between sequence points (and even if by some extended
exegesis of the standard it would turn out to be well-defined, it would
still be poor form; but the in the absence of obvious separating sequence
points, the burden to prove well-defined behavior would be on whoever codes
that way. Presumably, it would take a whole paragraph in comments to
justify that line).

However

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

has well-defined behavior.

It's a clever trick,

No, it isn't. It's just a form of code obfuscation. If you want to swap a
and be, just say so:

swap( a, b );

but I have a feeling something may go wrong if I
use it in C++, although quick tests with a few compilers produce
correct output. So is the code guaranteed to work correctly on all
compilers?

See above.
Best

Kai-Uwe Bux

[terminator]

On Nov 26, 1:13 pm, Kai-Uwe Bux <jkherci...@gmx .netwrote:

indrawati.ya... @gmail.com wrote:

OK, before you all stab me with your OT pitchfork, I just want to
mention that this question is indeed related to c.l.c++. My question
is, does the well-known method to swap two integers produce undefined
behaviour in c++? The method is:

a ^= b ^= a ^= b;

If you write it on a single line, it would appear to be UB since you modify
the variable a twice between sequence points (and even if by some extended
exegesis of the standard it would turn out to be well-defined, it would
still be poor form; but the in the absence of obvious separating sequence
points, the burden to prove well-defined behavior would be on whoever codes
that way. Presumably, it would take a whole paragraph in comments to
justify that line).

However

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

has well-defined behavior.

I wanted to say so.

It's a clever trick,

No, it isn't. It's just a form of code obfuscation. If you want to swap a
and be, just say so:

swap( a, b );

and what is the implementation of swap?
One may like to implement the int swap as the above three lines.

regards,
FM.

[Kai-Uwe Bux]

terminator wrote:

On Nov 26, 1:13 pm, Kai-Uwe Bux <jkherci...@gmx .netwrote:

>indrawati.ya.. [e-mail] wrote:

OK, before you all stab me with your OT pitchfork, I just want to
mention that this question is indeed related to c.l.c++. My question
is, does the well-known method to swap two integers produce undefined
behaviour in c++? The method is:

a ^= b ^= a ^= b;

If you write it on a single line, it would appear to be UB since you
modify the variable a twice between sequence points (and even if by some
extended exegesis of the standard it would turn out to be well-defined,
it would still be poor form; but the in the absence of obvious separating
sequence points, the burden to prove well-defined behavior would be on
whoever codes that way. Presumably, it would take a whole paragraph in
comments to justify that line).

However

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

has well-defined behavior.

I wanted to say so.

It's a clever trick,

No, it isn't. It's just a form of code obfuscation. If you want to swap a
and be, just say so:

swap( a, b );

and what is the implementation of swap?

That is up to the implementor of the library.

One may like to implement the int swap as the above three lines.

So what? Even if std::swap should happen to be implemented in such a way
that it boils down to the above three lines for built-in scalar types, that
still would not imply that

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

conveys intend as well and as succinctly as

std::swap( a, b );

There is no point in littering code with hacks. Note: the same applies to

{
int dummy = a;
a = b;
b = dummy;
}

although the case is somewhat weaker. You also would not want to write that
over and over again in your code.
Best

Kai-Uwe Bux

[Marco Manfredini]

in************* @gmail.com wrote:

OK, before you all stab me with your OT pitchfork, I just want to
mention that this question is indeed related to c.l.c++. My question
is, does the well-known method to swap two integers produce undefined
behaviour in c++? The method is:

a ^= b ^= a ^= b;

It's a clever trick, but I have a feeling something may go wrong if I
use it in C++, although quick tests with a few compilers produce
correct output. So is the code guaranteed to work correctly on all

A really *stone old* trick, that doesn't work if a and b occupy the same
storage location.

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

int x=1;
swap(x,x);

will produce 0 in x and can hardly be considered a valid implementation
of swap - which btw. should terminate the other discussion as well.

[Kai-Uwe Bux]

Marco Manfredini wrote:

in************* @gmail.com wrote:

>OK, before you all stab me with your OT pitchfork, I just want to
mention that this question is indeed related to c.l.c++. My question
is, does the well-known method to swap two integers produce undefined
behaviour in c++? The method is:

a ^= b ^= a ^= b;

It's a clever trick, but I have a feeling something may go wrong if I
use it in C++, although quick tests with a few compilers produce
correct output. So is the code guaranteed to work correctly on all

A really *stone old* trick, that doesn't work if a and b occupy the same
storage location.

Ah that was it. I remembered vaguely a discussion of several tricks like
this on this group. Unfortunately, I was not able to recall the exact
shortcoming that was pointed out back then (I considered the case a == b
not &a == &b --- and a== b worked).

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

int x=1;
swap(x,x);

will produce 0 in x and can hardly be considered a valid implementation
of swap - which btw. should terminate the other discussion as well.

Yup.
Thanks a lot

Kai-Uwe Bux

[Ron Natalie]

Kai-Uwe Bux wrote:

>
So what? Even if std::swap should happen to be implemented in such a way
that it boils down to the above three lines for built-in scalar types, that
still would not imply that

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

conveys intend as well and as succinctly as

std::swap( a, b );

There is no point in littering code with hacks. Note: the same applies to

std::swap gets rid of having to worry about it. Presumably your
implementation knows the best way. Once you get past some simple
scalar values, the classes can define their own specialization for
swap.

The people who thing the XOR behavior is a neat idea totally lose the
concept that it's probably the least efficient way to do so. Even
the presumbalby space inefficent:
t = a; a = b; t = b;

might not actually allocate any memory for the temporary value, it
may in fact just be an transient register that may have been allocated
anyway.

LD R1, a
LD R2, b
ST a, R2
ST b, R1

where the XOR debacle
LD R1, a
LD R2, b
XOR R1,R1,R2
XOR R2,R2,R1
XOR R1,R1,R2
ST a, R1
ST b, R2

[James Kanze]

On Nov 26, 10:56 am, indrawati.ya... @gmail.com wrote:

OK, before you all stab me with your OT pitchfork, I just want to
mention that this question is indeed related to c.l.c++. My question
is, does the well-known method to swap two integers produce undefined
behaviour in c++? The method is:

a ^= b ^= a ^= b;

It's a clever trick,

It's a stupid trick, which doesn't work reliably in any language.

As written above, it's undefined behavior in C++. But even if
you introduce sequence points, it doesn't work.

but I have a feeling something may go wrong if I
use it in C++, although quick tests with a few compilers produce
correct output.

Only in a few special cases. The basic algorithm doesn't work
reliably, so any implementation using it is bound to fail in
some cases.

--
James Kanze (GABI Software) email:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[terminator]

On Nov 26, 4:02 pm, Ron Natalie <r...@spamcop.n etwrote:

Kai-Uwe Bux wrote:

So what? Even if std::swap should happen to be implemented in such a way
that it boils down to the above three lines for built-in scalar types, that
still would not imply that

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

conveys intend as well and as succinctly as

std::swap( a, b );

There is no point in littering code with hacks. Note: the same applies to

std::swap gets rid of having to worry about it. Presumably your
implementation knows the best way. Once you get past some simple
scalar values, the classes can define their own specialization for
swap.

The people who thing the XOR behavior is a neat idea totally lose the
concept that it's probably the least efficient way to do so. Even
the presumbalby space inefficent:
t = a; a = b; t = b;

might not actually allocate any memory for the temporary value, it
may in fact just be an transient register that may have been allocated
anyway.

LD R1, a
LD R2, b
ST a, R2
ST b, R1

where the XOR debacle
LD R1, a
LD R2, b
XOR R1,R1,R2
XOR R2,R2,R1
XOR R1,R1,R2
ST a, R1
ST b, R2

even old x86 machines support some 'exg' opcode that swaps two
registers in just one instruction ,so a good compiler can handle
triple assignment much better than you mentioned in case both ints
have register storage.The xor trick has less chance of such
optimization , but it is a joyfull solution to a programming delima(I
like it more than add/subtract solution).

regards,
FM

[James Kanze]

On Nov 27, 4:21 pm, terminator <farid.mehr...@ gmail.comwrote:

On Nov 26, 4:02 pm, Ron Natalie <r...@spamcop.n etwrote:

The people who thing the XOR behavior is a neat idea totally lose the
concept that it's probably the least efficient way to do so. Even
the presumbalby space inefficent:
t = a; a = b; t = b;

might not actually allocate any memory for the temporary value, it
may in fact just be an transient register that may have been allocated
anyway.

LD R1, a
LD R2, b
ST a, R2
ST b, R1

where the XOR debacle
LD R1, a
LD R2, b
XOR R1,R1,R2
XOR R2,R2,R1
XOR R1,R1,R2
ST a, R1
ST b, R2

even old x86 machines support some 'exg' opcode that swaps two
registers in just one instruction ,so a good compiler can
handle triple assignment much better than you mentioned in
case both ints have register storage.The xor trick has less
chance of such optimization, but it is a joyfull solution to
a programming delima(I like it more than add/subtract
solution).

I seem to recall some 8086 compilers actually recognizing the
classical swap idiom (with the temporary) and generating the
exch instruction to implement it. Modern x86 compilers don't,
however, probably because on more recent x86 processors, xchg
has an implied lock prefix, which acts as a memory fence (which
in turn means that the instruction is considerably slower than
it would be otherwise).

I just ran some quick benchmarks on an Intel based Linux machine
here (using g++ 4.1.0, -O3), using the following "swappers":

struct SwapperClassic
{
void operator()( int& a, int& b )
{
int tmp = a ;
a = b ;
b = tmp ;
}
} ;

struct SwapperXor
{
void operator()( int& a, int& b )
{
a ^= b ;
b ^= a ;
a ^= b ;
}
} ;

struct SwapperAsm
{
void operator()( int& a, int& b )
{
asm ( "movl %[a], %%eax\n xchgl %%eax,%[b] \n movl %%eax,%
[a]"
: [a] "+m" (a), [b] "+m" (b) : : "%eax" ) ;
}
} ;

On this particular machine (not sure of its actual spec's, which
processor or the clock frequency), I got:

ns per machine memory
iter. instr. accesses

SwapperClassic: 1.7 5 5
SwapperXor: 2.5 9 7
SwapperAsm: 84.4 4 4

Tests run on 500 million iterations. In this case, the actual
function was invoked within a virtual member function, and
swapped two member variables. And the last two columns do not
include the standard function prefix or postfix.

A quick glance at the generated assembler showed that none of
the three versions used any local variables.

And as you can see, the cost of the memory fence due to the
implicit lock prefix on the xchgl instruction is very, very
high. The generated code uses one less instruction, and has one
less memory access, but requires roughly 50 times more time to
run.

--
James Kanze (GABI Software) email:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]