Is there a Swap faster than using XOR!!!

[ANaiveProgrammer]

hi all

swapping two variables using xor can be as follows
b = a ^ b
a = b ^ a
b = a ^ b
i've been given an assigment to do a swap faster than above and
without using three variables ( on a linux box over i80x86)? I was
wondering howz that possible? Any help will be highly
appreciated......
regards
waqas

 

[Chris Torek]

swapping two variables using xor ...

See the comp.lang.c FAQ, questions 3.3b and 10.3.

 

[Martin Ambuhl]

hi all

swapping two variables using xor can be as follows
b = a ^ b
a = b ^ a
b = a ^ b
i've been given an assigment to do a swap faster than above and
without using three variables ( on a linux box over i80x86)? I was
wondering howz that possible? Any help will be highly
appreciated......

The XOR trick is old and tired. It is also stupid and dangerous.
Anyone giving you an assignment to do a swap with a temporary variable
is an ass. So is anyone who imagines that micro-optimization at this
level is desirable or even possible.

 

[Method Man]

The XOR trick is old and tired. It is also stupid and dangerous.
Anyone giving you an assignment to do a swap with a temporary variable
is an ass.

You mean "without a temporary variable"?

Because, the simplest and fastest way to do a swap is using the traditional
temporary third variable. Almost every compiler now will optimize it for
you.

 

[Paul Hsieh]

swapping two variables using xor can be as follows
b = a ^ b
a = b ^ a
b = a ^ b
i've been given an assigment to do a swap faster than above and
without using three variables ( on a linux box over i80x86)? I was
wondering howz that possible? Any help will be highly
appreciated......

The responses you've received don't make a lot of sense to me. First
of all, this is apparently off topic in this newsgroup (Linux/i80x86
are off topic). Second of all of all, you have to describe the type
of the variables you are talking about -- given that you are using
"^", I'm going to assume they are integer scalars of some kind.

An alternate solution (which sort of works for floating point as well)
includes: b += a; a = b - a; b -= a; . However as to whether or not
this is faster is also apparently off topic in c.l.c.

<OFF TOPIC ANSWER>
b += a; a = b - a; b -= a; is slower than the sequence of 3 xors for
integers. The reason is that on the x86 "a = b - a;" has to be broken
down into two instructions (for floating point this is not true, but
may vary from compiler to compiler). You might try something like b
+= a; a -= b; b += a; a = -a; and hope that the last two instructions
run in parallel, but that gets you to at best a tie with the 3 xor
solution.

If the two variables are in x86 registers, then there is a single
assembly language instruction "xchg reg, reg" that performs precisely
what you want (consult your compiler documentation for how to insert
such instructions in your code). If this is faster for modern x86s,
it is for sole reason that the sequence of 3 xor operations are
dependent upon each other. Using a temp variable: c = a; a = b; b =
c; is actually the fastest solution in general on most modern x86s
(the first two instructions can run in parallel on a K6/PPro or
better) -- the reason being that "xchg reg, reg" really performs the
exact same thing (using a rename register for a temp) but has to
invoke the microcode sequencer to do so (which may preclude other
instructions from being decoded and executed in parallel.) The xchg
solution is also horrendously bad (up to *HUNDREDS* of times slower)
if at least one of the variables is in memory because of the implicit
"lock" semantics of xchg on the x86. So xchg is really only a good
choice when both variables are mapped to registers and your inner loop
has some severe register pressure.
</OFF TOPIC ANSWER>

 

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

The responses you've received don't make a lot of sense to me. First
of all, this is apparently off topic in this newsgroup (Linux/i80x86
are off topic). Second of all of all, you have to describe the type
of the variables you are talking about -- given that you are using
"^", I'm going to assume they are integer scalars of some kind.

An alternate solution (which sort of works for floating point as well)
includes: b += a; a = b - a; b -= a; . However as to whether or not
this is faster is also apparently off topic in c.l.c.

<OFF TOPIC ANSWER>
b += a; a = b - a; b -= a; is slower than the sequence of 3 xors for
integers. The reason is that on the x86 "a = b - a;" has to be broken
down into two instructions (for floating point this is not true, but
may vary from compiler to compiler). You might try something like b
+= a; a -= b; b += a; a = -a; and hope that the last two instructions
run in parallel, but that gets you to at best a tie with the 3 xor
solution.

It might overflow.

Your assumption that two instructions may be slower than one instruction
is also false.

 

[Paul Hsieh]

It might overflow.

This makes no difference (in the integer case).

Your assumption that two instructions may be slower than one instruction
is also false.

Read again. I made no such assumption.

 

[Thomas Stegen]

This makes no difference (in the integer case).

Am implementation is allowed to use instructions which cause exceptions
interrupts in the case of signed integers overlowing. MIPS has such
instructions for example (add and sub for example), I don't know about
x86. Though C compilers for MIPS generally does not use them (instead
addu and subu are often used).

In short, if you rely on overflow of signed integers you are living on
the mercy of the particular compiler being used.

 

[Keith Thompson]

An alternate solution (which sort of works for floating point as well)
includes: b += a; a = b - a; b -= a; . However as to whether or not
this is faster is also apparently off topic in c.l.c.

If by "sort of works" you mean "doesn't work", I agree. Yes, it's
mathematically sound if a and b are capable of representing actual
real numbers, but C floating-point variables are not. Roundoff errors
will cause errors in the results. In some cases, you may get the same
values you started with; in others, you'll lose a lot of precision,
especially if the initial values of a and b differ greatly in
magnitude. If a and b are the same variable, you'll set it to zero (a
problem shared with the xor kludge). And of course any of the
operations can overflow if the operands are floating-point or signed
integers.

The way to swap two variables in C is to use a temporary variable:
old_a = a;
a = b;
b = old_a;
If you're programming in machine language, you may be able to use a
swap instruction; a smart C compiler may be able to convert the above
to use that instruction if it makes sense to do so. This is simple,
it's likely to be as efficient as any other solution, and it doesn't
suffer from the pitfalls of other "clever" techniques.

Asking how to swap to variables without using a temporary is like
asking how to drive a nail without using a hammer. The correct answer
is not "use xor" or "use your forehead", it's "why do you want to do
that?". If there's a valid answer to that, we can consider alternate
solutions, but I have yet to see a case where it doesn't make more
sense just to use a temporary.

 

[Christian Bau]

hi all

swapping two variables using xor can be as follows
b = a ^ b
a = b ^ a
b = a ^ b

Anyone who does that shouldn't be allowed to get a job as a programmer.

i've been given an assigment to do a swap faster than above and
without using three variables ( on a linux box over i80x86)? I was
wondering howz that possible? Any help will be highly
appreciated......

int tmp = a;
a = b;
b = a;

If whoever gave you that assignment doesn't agree, just ask him or her
to post here. Looking forward to it.

 

[Richard Tobin]

int tmp = a;
a = b;
b = a;

Yup, the compiler should certainly be able to optimise away the
temporary variable in that one!

-- Richard

 

[Raymond Martineau]

Anyone who does that shouldn't be allowed to get a job as a programmer.

Only if there is no comments attached to the code.

This is an assignment, meaning that some person wants to see something done
with some special requirements - in this case, swapping without a temporary
variable. Whether the assignment is legitimate under standard C is another
story, because the swap code provided does not work with floating point
numbers or data-types larger than an int/long.

int tmp = a;
a = b;
b = a;

That last line should be:
b=tmp;

Otherwise, it will be a complete no-op, regardless of data type.

If whoever gave you that assignment doesn't agree, just ask him or her
to post here. Looking forward to it.

A better idea would to ask for the solution rather than getting him to post
in various newsgroups. If there are cases where the solution will not work
(e.g. it relies on a specific data type), then submit a request to the
teacher's department asking the assignment to be annulled.

 

[Jack Klein]

This makes no difference (in the integer case).

Yes it does, for the signed integer types. Overflow or underflow in
signed integer types is undefined behavior. That pretty much ends all
discussion here. Whatever a particular compiler might happen to do in
an instance of undefined behavior is off-topic here, because you have
left the boundary of the language.

 

[Christopher Benson-Manica]

Only if there is no comments attached to the code.

Not so; it's always a bad idea, and always dangerous unless the type
in question is unsigned char.

 

[James Dow Allen]

(e-mail address removed) (Paul Hsieh) wrote in message

<OFF TOPIC ANSWER>
b += a; a = b - a; b -= a; is slower than the sequence of 3 xors for
integers. ...

Since much of this discussion is off-topic anyway, I'll
indulge in some ancient folklore.

The IBM 370/145, with a 2-byte ALU, could do a 4-byte addition in
*one* micro-cycle (the cycle was extended to run the ALU twice)
but required *four* micro-cycles to do a 4-byte XOR (both halves
of the ALU did the same byte with results compared for reliability!)

Well ... just in case you wanted to know...

James

 

[Paul Hsieh]

Am implementation is allowed to use instructions which cause exceptions
interrupts in the case of signed integers overlowing. MIPS has such
instructions for example (add and sub for example), I don't know about
x86.

The OP asked for Linux on x86. Apparently the x86 *DOES* have an
interrupt on overflow mechanism as well, however, you aren't going to
be able to turn it on in user mode under Linux.

In short, if you rely on overflow of signed integers you are living on
the mercy of the particular compiler being used.

This comment was under a <OFF TOPIC...> clause.

 

[Paul Hsieh]

If by "sort of works" you mean "doesn't work", I agree.

*Sigh* ...

[...] Yes, it's
mathematically sound if a and b are capable of representing actual
real numbers, but C floating-point variables are not. Roundoff errors
will cause errors in the results. In some cases, you may get the same
values you started with; in others, you'll lose a lot of precision,
especially if the initial values of a and b differ greatly in
magnitude. If a and b are the same variable, you'll set it to zero (a
problem shared with the xor kludge). And of course any of the
operations can overflow if the operands are floating-point or signed
integers.

The way to swap two variables in C is to use a temporary variable:
old_a = a;
a = b;
b = old_a;

Of course, I didn't have wait too long before you tripped yourself up.
This *ALSO* has a numerical problem. For example, older x86
compilers would often put the x87 into 80 bit mode -- but being an x86
this means that running out of registers (or stack entries) was a
common problem. So the above operation would require an additional
storage which might be forced to go through memory -> but that memory
would be declared as 64 bits, so this action actually drops some
accuracy.

Look, *ALL* floating point usage is inherently numerically unstable
(unless the parameters are short shifted powers of two) -- which is
why I just said "sort of works". If you are using floating point at
all, either you work out how every single operation is numerically
characterized (and you may need to understand the underlying assembly
to really know), or you just assume that in general that every
calculation will always be off by some amount and maybe you test to
see by how much.

Asking how to swap to variables without using a temporary is like
asking how to drive a nail without using a hammer. The correct answer
is not "use xor" or "use your forehead", it's "why do you want to do
that?". If there's a valid answer to that, we can consider alternate
solutions, but I have yet to see a case where it doesn't make more
sense just to use a temporary.

Spoken like someone unjustifiably sure of themselves. Try
implementing an incremental fibonacci inner loop using an add, a swap
and a 3 variables. Then tell me which swap implementation is the most
appropriate for such an inner loop.

Every "clever swap implementation", that I know of has a scenario
where it is best to use them. For example, the 3 xors can be used on
graphics buffers, if your graphics device has limited memory, is too
slow either to swap on a pixel by pixel basis or to otherwise transfer
through system memory but nevertheless has an accelerated pixel-op
engine which includes xor. The sum, subtract method works well if the
surrounding operations can cancel out with those operations. And
finally the often useful "DONT DO THAT" operation -- i.e., rename the
registers in your algorithm, rather switching them at run time. These
are 3 cases where I would never recommend using the swap through a
temp solution.

Your problem is that you've got a hammer and a nail, but you didn't
bother to check if you are trying to penetrate glass or paper.

 

[Richard Bos]

Of course, I didn't have wait too long before you tripped yourself up.
This *ALSO* has a numerical problem. For example, older x86
compilers would often put the x87 into 80 bit mode

Details of implementation are immaterial. C is not a portable assembler,
no matter what imbecile Ada-heads[1] may want you to think. If the
compiler isn't capable of generating correct machine code for correct C,
ditch it.

Richard

[1] Not necessarily a pleonasm

 

[Keith Thompson]

Of course, I didn't have wait too long before you tripped yourself up.
This *ALSO* has a numerical problem. For example, older x86
compilers would often put the x87 into 80 bit mode

Details of implementation are immaterial. C is not a portable assembler,
no matter what imbecile Ada-heads[1] may want you to think. If the
compiler isn't capable of generating correct machine code for correct C,
ditch it.

Richard

[1] Not necessarily a pleonasm

Speaking as a former (and unrepentant) Ada-head, not everyone who uses
and likes Ada is as ignorant about C as you imply. Your point is
valid; it doesn't need to be associated with a language flame war.

(C can be, and often is, used as an intermediate language for
compilers for higher-level languages; that doesn't make it a "portable
assembler".)

 

[Tim Rentsch]

The way to swap two variables in C is to use a temporary variable:
old_a = a;
a = b;
b = old_a;

Of course, I didn't have wait too long before you tripped yourself up.
This *ALSO* has a numerical problem. For example, older x86
compilers would often put the x87 into 80 bit mode

Details of implementation are immaterial. C is not a portable assembler,
no matter what imbecile Ada-heads[1] may want you to think. If the
compiler isn't capable of generating correct machine code for correct C,
ditch it.

Richard

[1] Not necessarily a pleonasm

Speaking as a former (and unrepentant) Ada-head, not everyone who uses
and likes Ada is as ignorant about C as you imply.

Richard's article specifically indicates that his description shouldn't
be taken as applying to all people who use Ada. Admittedly, he does
this in a rather indirect way - how many people would know right off
the bat what a "pleonasm" is?