Swap!
Sara Marouf
C or C++.
Thanks.
marcjb
No, you can't. You need to keep track of the variable that is over-
written first, and you would need another variable for that.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
Dann Corbit
news:37CD7852...@hotmail.com...
> Can you swap 2 variable without using 3rd one.. Can u show me a code in
> C or C++.
The cheezy xor trick.
a ^= b;
b ^= a;
a ^= b;
Here's the nasal demon variant:
a ^= b ^= a ^= b;
Subtraction can also be used.
It's simply not worth it.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
Martin Ambuhl
Sara Marouf wrote:
>
> Can you swap 2 variable without using 3rd one.. Can u show me a code in
> C or C++.
This is a silly parlor trick of beginning programmers. It is not
guaranteed to work over all types and can be derailed with appropriate
arguments even for types where it does work. It is unlikely to save you
any space or time. If you still want to do this stupid thing, do what
you should have done already and check the FAQ.
--
Martin Ambuhl mam...@earthlink.net
__________________________________________________________
Fight spam now!
Get your free anti-spam service: http://www.brightmail.com
Dann Corbit
news:7qk28j$542$1...@nnrp1.deja.com...
> In article <37CD7852...@hotmail.com>,
> Sara Marouf <compu...@hotmail.com> wrote:
> > Can you swap 2 variable without using 3rd one.. Can u show me a code
> in
> > C or C++.
> >
> >
>
> No, you can't. You need to keep track of the variable that is over-
> written first, and you would need another variable for that.
Darn. I just said it. Twice.
Kelsey Bjarnason
> C or C++.
#include <stdio.h>
int main()
{
int x = 3, y = 4;
printf( "Here's two numbers. Enter them in reverse order: %d
%d\n",x,y );
scanf( "%d %d", &x, &y );
printf("Numbers are now: %d %d\n", x, y );
return 0;
}
Why this should not be done is left as an excercise for the reader.
gilley
On Wed, 1 Sep 1999, Sara Marouf wrote:
> Can you swap 2 variable without using 3rd one.. Can u show me a code in
> C or C++.
> Thanks.
>
>
>
#define swap_bitwize(a,b) ( a^=b; b^=a; a^=b; )
think about it before you use it.
Erik Max Francis
> You mean it will if they're both integral types; bitwise operators
> don't
> work with anything else. (It baffles me why anyone thinks this is so
> useful, but that's another story.)
Indeed; it's amusing, and it's something that has probably been used a
few times in the Obfuscated C Code Contests, but it doesn't have much in
the way of practical use.
--
Erik Max Francis | icq 16063900 | whois mf303 | email m...@alcyone.com
Alcyone Systems | irc maxxon (efnet) | web http://www.alcyone.com/max/
San Jose, CA | languages en, eo | icbm 37 20 07 N 121 53 38 W
USA | Wed 1999 Sep 1 (68%/948) | &tSftDotIotE
__
/ \ You win the victory when you yield to friends.
\__/ Sophocles
Morris Dovey
> (reluctant snip of excellent explanation)
Kaz...
Nicely said! Your explanation is one of the best (on any subject) that I've seen on
comp.lang.c -- or any other newsgroup...
Morris Dovey
West Des Moines, Iowa USA
mrd...@iedu.org
Barry Schwarz
a^=b;b^=a;a^=b;
will swap their contents without using a third.
In article <37CD7852...@hotmail.com>, Sara Marouf
Eric Amick
> If a and b are the same type of variable -
> a^=b;b^=a;a^=b;
> will swap their contents without using a third.
You mean it will if they're both integral types; bitwise operators don't
work with anything else. (It baffles me why anyone thinks this is so
useful, but that's another story.)
--
Eric Amick
Columbia, MD
eam...@clark.net
Kaz Kylheku
>Barry Schwarz <schw...@aol.com.net> wrote:
>> If a and b are the same type of variable -
>
>> a^=b;b^=a;a^=b;
>
>> will swap their contents without using a third.
>
>You mean it will if they're both integral types; bitwise operators don't
>work with anything else. (It baffles me why anyone thinks this is so
>useful, but that's another story.)
This is next to useless in my view. Here are four good reasons:
1. On many modern RISC-type machines, you cannot do it at all. The compiler
will have to emit code that uses temporary storage by way of allocating
a register. The reasons is that on a load-store architecture, you
typically don't have register-memory operations other than loads and
stores with a few simple addressing modes, let alone memory-memory
operations. For the Awful XOR Trick (AXT) to live up to its promise
of no temporary variable, the machine has to support memory-to-memory
exclusive or operations, so that the compiler can emit code like:
movexor [b], [a] (1)
movexor [a], [b]
movexor [b], [a]
Without memory-to-memory XOR operations, an intermediate register has to be
used. That counts as extra storage; the algorithm is no longer the same.
2. Even if the machine supports mem-to-mem XOR operations, you are looking
at doing six memory accesses for just a one word swap! Three instructions
that access two memory locations each. The problem of swapping two words
can be solved using only two loads and two stores per word swapped:
move [a], R0 (2)
move [b], R1
move R0, [b]
move R1, [a]
The use of AXT could only be justified on machines that have no
registers, on which the swap would have to be coded as:
move [a], [temp] (3)
move [b], [a]
move [temp], [b]
3. AXT fails miserably if a and b refer to the same object, so a test and
branch is needed to avoid that case. If a and b are the same object,
the object becomes zero after the very first XOR. Tests and branches
introduce potential pipeline stalls; why introduce them if you don't
have to?
Now let's consider that machine with no registers which supports movexor.
By introducing the test for overlap, you probably waste enough bytes
with the additional test and branch that you have effectively negated
any advantage of not having to use the temporary word of storage.
Since there are no registers, the test will need to make additional memory
references. You might as well code it as (3) and not have to write a test.
4. Arbitrarily large objects can be swapped word by word using the normal three
variable rotation, using only one extra word of storage (or, more
likely, register). So saving a word buys you next to nothing if the
objects are large.
Martin Ambuhl
gilley wrote:
>
> On Wed, 1 Sep 1999, Sara Marouf wrote:
>
> > Can you swap 2 variable without using 3rd one.. Can u show me a code in
> > C or C++.
> > Thanks.
> >
> >
> >
>
> #define swap_bitwize(a,b) ( a^=b; b^=a; a^=b; )
>
> think about it before you use it.
The "think before you use" advise is sound. However, since this hack
does not work in a wide variety of cases and almost certainly gains
nothing, the maxim "think before you post code" might be appropriate.
Martin Ambuhl
Barry Schwarz wrote:
>
> If a and b are the same type of variable -
>
> a^=b;b^=a;a^=b;
>
> will swap their contents without using a third.
Are you sure?
1) What happens for a == b?
2) Since ^ is defined only over integers, what happens when a and b are
a) a floating point type
b) a pointer type
c) a struct or union type?
This continues to be a dangerous and pointless hack, best saved for beer
and pizza parties.
>
> In article <37CD7852...@hotmail.com>, Sara Marouf
> <compu...@hotmail.com> writes:
>
> >Can you swap 2 variable without using 3rd one.. Can u show me a code in
> >C or C++.
--
Eli Bendersky
what is a variable's value before overwriting it.
In assembly programming you would probably
use a register to preserve it, which would be
probably faster than memory, but in C you
must use some temporary variable, or at
least some address in the memory.
You can also type assebly code in C programs,
read the help on how to do it..
Martin Ambuhl wrote in message <37CD8672...@earthlink.net>...
>
>
>Sara Marouf wrote:
>>
>> Can you swap 2 variable without using 3rd one.. Can u show me a code in
>> C or C++.
>
>This is a silly parlor trick of beginning programmers. It is not
>guaranteed to work over all types and can be derailed with appropriate
>arguments even for types where it does work. It is unlikely to save you
>any space or time. If you still want to do this stupid thing, do what
>you should have done already and check the FAQ.
>
Richard J. Dawes
> ... (It baffles me why anyone thinks this is so
> useful, but that's another story.)
Yes, that *is* another (off-topic!) story. But, quickly, my under-
standing is that it's useful when coding directly in assembly, if you
have a register-register XOR instruction available. Consider some
algorithm requiring a loop in which a swap is necessary. If a spare
register is available and three MOVEs would be faster than three XORs
(often, if not usually, the case), then, yes, using a "temp" register
would be best. But quite often there are no such spares, and saving
even just one to the stack is relatively exorbitant. So, you use the
good ol' XOR-swap trick.
There are many "tricks" which don't seem much good in one paradigm,
but are quite handy in others. Sometimes it's cyclical, depending
on the available technology. I think they're all worth learning and
"filing away", for potential use somewhere far down the road.
--
==========================================
Richard J. Dawes rda...@san.rr.com
==========================================
Scott McMahan
> Can you swap 2 variable without using 3rd one
Write one to disk.
Scott
Richard Heathfield
<l7tz3.1628$dn.1...@newshog.newsread.com>...
Nice try. But my microwave oven, oddly enough, doesn't have a disk drive.
Ben Pfaff
Scott McMahan <sc...@aravis.softbase.com> wrote in article
<l7tz3.1628$dn.1...@newshog.newsread.com>...
> Sara Marouf (compu...@hotmail.com) wrote:
> > Can you swap 2 variable without using 3rd one
>
> Write one to disk.
Nice try. But my microwave oven, oddly enough, doesn't have a disk drive.
You need to upgrade to Microwave99 then.
--
"I ran it on my DeathStation 9000 and demons flew out of my nose." --Kaz
John Winters
Ben Pfaff <pfaf...@msu.edu> wrote:
>"Richard Heathfield" <comp...@eton.powernet.co.uk> writes:
>
> Scott McMahan <sc...@aravis.softbase.com> wrote in article
> <l7tz3.1628$dn.1...@newshog.newsread.com>...
> > Sara Marouf (compu...@hotmail.com) wrote:
> > > Can you swap 2 variable without using 3rd one
> >
> > Write one to disk.
>
> Nice try. But my microwave oven, oddly enough, doesn't have a disk drive.
>
>You need to upgrade to Microwave99 then.
Which will take 3/4 hour to warm one cup of coffee.
John
--
John Winters. Wallingford, Oxon, England.
The Linux Emporium - a source for Linux CDs in the UK
See http://www.linuxemporium.co.uk/
raw...@my-deja.com
"Richard Heathfield" <comp...@eton.powernet.co.uk> wrote:
> Scott McMahan <sc...@aravis.softbase.com> wrote in article
> <l7tz3.1628$dn.1...@newshog.newsread.com>...
> > Sara Marouf (compu...@hotmail.com) wrote:
> > > Can you swap 2 variable without using 3rd one
> >
> > Write one to disk.
> >
> >
>
> Nice try. But my microwave oven, oddly enough, doesn't have a disk drive.
So use your microwave modem to FTP the data to and from your
refrigerator. (On a practical note, you can also extend your
microwave's storage capacity through the use of appropriate
Tupperware containers.)
--
MJSR
Gregg
Sara Marouf <compu...@hotmail.com> wrote in article
<37CD7852...@hotmail.com>...
> Can you swap 2 variable without using 3rd one.. Can u show me a code in
> C or C++.
> Thanks.
a=a+b;
b=a-b;
a=a-b;
Only for types with addition and subtraction
Gregg Lewandowski
gr...@npac.syr.edu
Ben Pfaff
In article <87aer5x...@pfaffben.user.msu.edu>,
Ben Pfaff <pfaf...@msu.edu> wrote:
>"Richard Heathfield" <comp...@eton.powernet.co.uk> writes:
>
> Scott McMahan <sc...@aravis.softbase.com> wrote in article
> <l7tz3.1628$dn.1...@newshog.newsread.com>...
> > Sara Marouf (compu...@hotmail.com) wrote:
> > > Can you swap 2 variable without using 3rd one
> >
> > Write one to disk.
>
> Nice try. But my microwave oven, oddly enough, doesn't have a disk drive.
>
>You need to upgrade to Microwave99 then.
Which will take 3/4 hour to warm one cup of coffee.
But that's corrected in Service Pack 1!
--
Dann Corbit on comp.lang.c:
"Once you have leached enough [from c.l.c], you may find that others are
then able to attach their razor-sharp hooks into your meaty extremities
and you can provide them with a gruesome meal yourself."
Ben Pfaff
Sara Marouf <compu...@hotmail.com> wrote in article
<37CD7852...@hotmail.com>...
> Can you swap 2 variable without using 3rd one.. Can u show me a code in
> C or C++.
> Thanks.
a=a+b;
b=a-b;
a=a-b;
Only for types with addition and subtraction
What if a + b overflows? That's undefined behavior.
--
"Large amounts of money tend to quench any scruples I might be having."
-- Stephan Wilms
in...@fdhoekstra.nl
>
> Sara Marouf <compu...@hotmail.com> wrote...
> > Can you swap 2 variable without using 3rd one.. Can u show me
> > a code in C or C++.
>
> b=a-b;
> a=a-b;
>
> Only for types with addition and subtraction
And 99% guaranteed to give you an overflow sooner or later.
Richard
Scott McMahan
> Nice try. But my microwave oven, oddly enough, doesn't have a disk drive.
You need to upgrade.
Scott
Joe Maun
Martin Ambuhl wrote:
>
> Barry Schwarz wrote:
> >
> > If a and b are the same type of variable -
> >
> > a^=b;b^=a;a^=b;
> >
> > will swap their contents without using a third.
>
> Are you sure?
> 1) What happens for a == b?
Their contents are swapped. (given they have integer type.)
--
Joe
Dann Corbit
Joe Maun <repl...@yahoo.com> wrote in message
news:37CED12D...@yahoo.com...
swap(a,a);
oops.
Lawrence Kirby
mam...@earthlink.net "Martin Ambuhl" writes:
>
>
>Barry Schwarz wrote:
>>
>> If a and b are the same type of variable -
>>
>> a^=b;b^=a;a^=b;
>>
>> will swap their contents without using a third.
>
>Are you sure?
>1) What happens for a == b?
It works fine. Howver if a and b represent more general expressions
and &a == &b then there will be a problem.
>2) Since ^ is defined only over integers, what happens when a and b are
> a) a floating point type
> b) a pointer type
> c) a struct or union type?
Strictly there can be a problem even with signed integers, although not
on 2's complement based systems.
--
-----------------------------------------
Lawrence Kirby | fr...@genesis.demon.co.uk
Wilts, England | 7073...@compuserve.com
-----------------------------------------
Lawrence Kirby
>
>
>Sara Marouf <compu...@hotmail.com> wrote in article
><37CD7852...@hotmail.com>...
>> Can you swap 2 variable without using 3rd one.. Can u show me a code in
>> C or C++.
>> Thanks.
>
>a=a+b;
>b=a-b;
>a=a-b;
>
>Only for types with addition and subtraction
Signed integer arithmetic can overflow resulting in undefined behaviour.
Floating point arithmetic can also overflow but perhaps more importantly
the results can be inexact. For example if you try to swap 1.0 and 1E30
with this method you may be disappointed by the result.
Ian Greenwood
John Winters <jo...@polo.demon.co.uk> wrote in message
news:7qm2ah$k1p$1...@polo.demon.co.uk...
> In article <87aer5x...@pfaffben.user.msu.edu>,
> Ben Pfaff <pfaf...@msu.edu> wrote:
> >"Richard Heathfield" <comp...@eton.powernet.co.uk> writes:
> >
> > Scott McMahan <sc...@aravis.softbase.com> wrote in article
> > <l7tz3.1628$dn.1...@newshog.newsread.com>...
> > > Sara Marouf (compu...@hotmail.com) wrote:
> > > > Can you swap 2 variable without using 3rd one
> > >
> > > Write one to disk.
> >
drive.
> >
>
> Which will take 3/4 hour to warm one cup of coffee.
You may be able to speed this up by changing the jumper settings on your
microwave and overclocking the chip
Cheers
IanG
Dann Corbit
news:vZGz3.208$u03.7471@client...
> Unsigned type is not good enough for safety.
> Run this to learn why the cute xor trick is not so darned cute [FCOL]:
>
> #include <stdio.h>
> #include <stdlib.h>
>
> int main (void)
> {
> unsigned i;
> unsigned j;
> unsigned arr[10];
/* Change to this: */
for (i = 0; i < 10; i++)
arr[i] = (unsigned) rand ();
puts("\nBefore [cough] permutation");
for (i = 0; i < 10; i++)
printf ("%d\n", arr[i]);
> for (i = 0; i < 10; i++)
> for (j = 0; j < 10; j++)
> {
> arr[i] ^= arr[j];
> arr[j] ^= arr[i];
> arr[i] ^= arr[j];
> }
> puts("\nAfter [cough] permutation");
> for (i = 0; i < 10; i++)
> printf ("%d\n", arr[i]);
> return 0;
> }
Oops.
Dann Corbit
Run this to learn why the cute xor trick is not so darned cute [FCOL]:
#include <stdio.h>
#include <stdlib.h>
int main (void)
{
unsigned i;
unsigned j;
unsigned arr[10];
puts("\nBefore [cough] permutation");
for (i = 0; i < 10; i++)
printf ("%d\n", arr[i]);
for (i = 0; i < 10; i++)
arr[i] = (unsigned) rand ();
for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
{
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
puts("\nAfter [cough] permutation");
for (i = 0; i < 10; i++)
printf ("%d\n", arr[i]);
return 0;
}
Dann Corbit
** Having one of those stupid [let's make a bug] days...
** Would you believe:
*/
#include <stdio.h>
#include <stdlib.h>
int
main (void)
{
unsigned i;
unsigned j;
unsigned arr[10];
puts("\nBefore [cough] permutation");
for (i = 0; i < 10; i++)
{
arr[i] = (unsigned) rand ();
printf ("%u\n", arr[i]);
}
for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
{
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
puts("\nAfter [cough] permutation");
for (i = 0; i < 10; i++)
printf ("%u\n", arr[i]);
Yogesh Kayal
if A & B are intergers then A & B can be swapped as
A = A + B
B = A - B
A = A - B
Similarly you can make use of multiplication & division for swapping.
marcjb wrote in message <7qk28j$542$1...@nnrp1.deja.com>...
>In article <37CD7852...@hotmail.com>,
> Sara Marouf <compu...@hotmail.com> wrote:
>> Can you swap 2 variable without using 3rd one.. Can u show me a code
>in
>> C or C++.
>> Thanks.
>>
>>
>
>No, you can't. You need to keep track of the variable that is over-
>written first, and you would need another variable for that.
Jack Klein
<sp...@cyberdude.com> wrote in comp.lang.c:
> I think you can't do that really. You must know
> what is a variable's value before overwriting it.
> In assembly programming you would probably
> use a register to preserve it, which would be
> probably faster than memory, but in C you
> must use some temporary variable, or at
> least some address in the memory.
>
> You can also type assebly code in C programs,
> read the help on how to do it..
Who says "You can also type assebly (sic) code in C programs"?
Certainly not the ANSI/ISO International Standard for the C
programming language. And there are quite a few compilers that would
disagree with you as well.
Jack Klein
--
Home: http://home.att.net/~jackklein
Jack Klein
wrote in comp.lang.c:
>
>
> On Wed, 1 Sep 1999, Sara Marouf wrote:
>
> > Can you swap 2 variable without using 3rd one.. Can u show me a code in
> > C or C++.
> > Thanks.
> >
> >
> >
>
>
> #define swap_bitwize(a,b) ( a^=b; b^=a; a^=b; )
>
> think about it before you use it.
Funny...
#define swap_bitwize(a,b) ( a^=b; b^=a; a^=b; )
int main(void)
{
double d1, d2;
swap_bitwize(d1, d2);
return 0;
}
For some reason my compiler doesn't like it...
Jack Klein
wrote in comp.lang.c:
> Barry Schwarz <schw...@aol.com.net> wrote:
> > If a and b are the same type of variable -
>
> > a^=b;b^=a;a^=b;
>
> > will swap their contents without using a third.
>
> You mean it will if they're both integral types; bitwise operators don't
> work with anything else. (It baffles me why anyone thinks this is so
> useful, but that's another story.)
Actually it is only _guaranteed_ to work if they are unsigned integer
types. It is not _guaranteed_ to work if they are signed integer
types, and there are a few architectures out there where it won't.
Kaz Kylheku
You might be thinking of the implementation-defined value that results from xor
if one or or both operands are negative; that consideration doesn't actually
matter since these intermediate values aren't used. The semantics of the XOR
leads to the exchange of corresponding bits. Since the bits are exchanged, the
values are.
Jack Klein
Kylheku) wrote in comp.lang.c:
I do not see any guarantee in the standard that an XOR on two signed
integers will not produce a trap representation, which signed integers
may have. The fact that C89 did not discuss trap values does not mean
that it did not permit them, as the committee maintains that the
definition of them in C9X is not a change, merely the correction of an
oversight.
If there is such a guarantee that I missed, please supply a reference.
Jack Klein
in comp.lang.c:
To be more specific: even on a 2's complement implementation with
CHAR_BIT 8, SCHAR_MIN is not required to be less than -127, meaning
that 0x80 that we would "expect" to represent -128 is not a valid
value.
On such a platform an XOR of 1 and -127 (0x01 and 0x81) would produce
0x80. The moment this value is assigned back to one of the signed
chars the behavior is undefined.
raw...@my-deja.com
"Gregg" <gr...@npac.syr.edu> wrote:
>
> Sara Marouf <compu...@hotmail.com> wrote in article
> <37CD7852...@hotmail.com>...
> > C or C++.
>
> b=a-b;
> a=a-b;
>
> Only for types with addition and subtraction
Of course, most types in C don't have addition and subtraction
in the sense of satisfying the algebraic laws that would make this
work; overflow or roundoff generally invalidate the associative
law. The unsigned integer types work, but there you can also use
the exclusive or trick.
With addition, an unsigned integer type can be viewed as the
integers modulo some power of two; but exclusive or could be
viewed as element-by-element addition of a vector of bits
(integers modulo 2). Yet somehow the people who are
fascinated with the exclusive or trick are not pleased with
the addition trick, even though they both work reliably only
on the unsigned integer types; perhaps it's the more exotic
nature of the bitwise operator.
--
MJSR
Kaz Kylheku
>On Fri, 03 Sep 1999 05:50:30 GMT, jack...@att.net (Jack Klein) wrote
>in comp.lang.c:
>
>> On Fri, 03 Sep 1999 03:58:36 GMT, k...@ashi.footprints.net (Kaz
>> Kylheku) wrote in comp.lang.c:
>> > if one or or both operands are negative; that consideration doesn't actually
>> > matter since these intermediate values aren't used. The semantics of the XOR
>> > leads to the exchange of corresponding bits. Since the bits are exchanged, the
>> > values are.
>>
>> I do not see any guarantee in the standard that an XOR on two signed
>> integers will not produce a trap representation, which signed integers
>> may have. The fact that C89 did not discuss trap values does not mean
>> that it did not permit them, as the committee maintains that the
>> definition of them in C9X is not a change, merely the correction of an
>> oversight.
>>
>> If there is such a guarantee that I missed, please supply a reference.
>
>To be more specific: even on a 2's complement implementation with
>CHAR_BIT 8, SCHAR_MIN is not required to be less than -127, meaning
>that 0x80 that we would "expect" to represent -128 is not a valid
>value.
>
>On such a platform an XOR of 1 and -127 (0x01 and 0x81) would produce
>0x80. The moment this value is assigned back to one of the signed
>chars the behavior is undefined.
From past readings of comp.std.c, I've been led to understand that there are
only three supported representations for signed integers: two's complement,
one's complement and sign-magnitude. (Is this codified in C9X? Time
to check.)
A supposedly two's complement implementation which rejects -128 would be
non-conforming since it's not really two's complement, but rather
a sort of bastardized two's complement with one of the values
declared invalid.
In all three representations, all combinations of 1's and 0's give rise to
values. It follows that trap representations must rely on invisible bits that
do not contribute to the value.
These bits can't be manipulated using bit operations, except if one aliases the
object using an array of unsigned char. To create a trap representation, the
program has to do something underhanded, like cause an overflow, or use
aliasing tricks to access forbidden fields in the object, etc.
Joe Maun
Dann Corbit wrote:
>
> Joe Maun <repl...@yahoo.com> wrote in message
> news:37CED12D...@yahoo.com...
> >
> >
> > Martin Ambuhl wrote:
> > >
> > > Barry Schwarz wrote:
> > > >
> > > > If a and b are the same type of variable -
> > > >
> > > > a^=b;b^=a;a^=b;
> > > >
> > > > will swap their contents without using a third.
> > >
> > > Are you sure?
> > > 1) What happens for a == b?
> >
> > Their contents are swapped. (given they have integer type.)
> Unless, of course, a "is" b. (e.g. they are exactly the same object):
Impossible.[1] You must be thinking about C++. (Or perhaps you are
seeing stars?)
>swap(a,a);
>
> oops.
Given the above rolled into a function:
swap(a,b); will not do much either.
[1] It might be possible if you see the above as a macro before
expansion.
--
Joe
Dann Corbit
> Dann Corbit wrote:
> >
> > Joe Maun <repl...@yahoo.com> wrote in message
> > news:37CED12D...@yahoo.com...
> > >
> > >
> > > Martin Ambuhl wrote:
> > > >
> > > > Barry Schwarz wrote:
> > > > >
> > > > > If a and b are the same type of variable -
> > > > >
> > > > > a^=b;b^=a;a^=b;
> > > > >
> > > > > will swap their contents without using a third.
> > > >
> > > > Are you sure?
> > > > 1) What happens for a == b?
> > >
> > > Their contents are swapped. (given they have integer type.)
> > Unless, of course, a "is" b. (e.g. they are exactly the same object):
>
>
> Impossible.[1] You must be thinking about C++. (Or perhaps you are
> seeing stars?)
day."
> >swap(a,a);
> >
> > oops.
>
> Given the above rolled into a function:
> swap(a,b); will not do much either.
>
> [1] It might be possible if you see the above as a macro before
> expansion.
/*
** Unsafe macros:
*/
#include <stdio.h>
#include <stdlib.h>
#define swapa(a, b) a ^= b, b ^= a, a ^= b;
#define swapb(a, b, t) t = a; a = b; b = t;
int
main (void)
{
unsigned i;
unsigned j;
unsigned t;
unsigned arr[10];
puts ("\nBefore [cough] permutation");
for (i = 0; i < 10; i++)
{
arr[i] = (unsigned) rand ();
printf ("%u\n", arr[i]);
}
for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
{
swapb (arr[i], arr[j], t);
}
puts ("\nAfter [gurgle] tmp permutation");
for (i = 0; i < 10; i++)
printf ("%u\n", arr[i]);
for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
{
swapa (arr[i], arr[j]);
}
puts ("\nAfter [cough] xor permutation");
for (i = 0; i < 10; i++)
printf ("%u\n", arr[i]);
return 0;
}
/*
** As functions:
*/
#include <stdio.h>
#include <stdlib.h>
void swapa(unsigned *a, unsigned *b)
{
*a ^= *b, *b ^= *a, *a ^= *b;
}
void swapb(unsigned *a, unsigned *b, unsigned *t)
{
*t = *a; *a = *b; *b = *t;
}
int
main (void)
{
unsigned i;
unsigned j;
unsigned t;
unsigned arr[10];
puts ("\nBefore [cough] permutation");
for (i = 0; i < 10; i++)
{
arr[i] = (unsigned) rand ();
printf ("%u\n", arr[i]);
}
for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
{
swapb (arr+i, arr+j, &t);
}
puts ("\nAfter [gurgle] tmp permutation");
for (i = 0; i < 10; i++)
printf ("%u\n", arr[i]);
for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
{
swapa (arr+i, arr+j);
}
puts ("\nAfter [cough] xor permutation");
Greg Martin
<homer....@springfield.com> wrote:
>Jack Klein a écrit dans le message
><37d32f14...@netnews.worldnet.att.net>...
>>#define swap_bitwize(a,b) ( a^=b; b^=a; a^=b; )
>>int main(void)
>>{
>> double d1, d2;
>> swap_bitwize(d1, d2);
>> return 0;
>>}
>>
>>For some reason my compiler doesn't like it...
>>
>try this :
>
>#include <stdio.h>
>
>#define swap_bitwize(a,b) a^=b; b^=a; a^=b
>int main(void)
>{
> int d1=3;
> int d2=4;
> printf("d1=%u d2=%u\n",d1,d2);
> swap_bitwize(d1,d2);
> printf("d1=%u d2=%u\n",d1,d2);
> return 0;
>}
>
I think you missed the point Homer. Jack was pointing out the failings
of that construct.
Regards,
Greg Martin.
Homer Simpson
<37d32f14...@netnews.worldnet.att.net>...
>#define swap_bitwize(a,b) ( a^=b; b^=a; a^=b; )
>int main(void)
>{
> double d1, d2;
> swap_bitwize(d1, d2);
> return 0;
>}
>
>For some reason my compiler doesn't like it...
>
try this :
#include <stdio.h>
#define swap_bitwize(a,b) a^=b; b^=a; a^=b
int main(void)
{
int d1=3;
int d2=4;
printf("d1=%u d2=%u\n",d1,d2);
swap_bitwize(d1,d2);
printf("d1=%u d2=%u\n",d1,d2);
return 0;
}
--
HS
Jack Klein
Kylheku) wrote in comp.lang.c:
That's what I thought about 2's complement as well, especially when I
came across a compiler which defined SCHAR_MIN, SHRT_MIN, and LONG_MIN
to be exactly the required value in the standard.
After a fair amount of discussion I was convinced that it is indeed
perfectly legal and conforming for a 2's complement implementation
with 8 bit chars to have SCHAR_MAX 127 and SCHAR_MIN -127. It is
undefined behavior on such an implementation to store 0x80 in a signed
char.
In fact if you read C9X between the lines quite carefully you will
discover, as I did to my surprise, that the only object type which is
required and guaranteed to be free from trap representations is
unsigned char. The other signed and unsigned integer types can all
have trap representations.
Lawrence Kirby
ian.gr...@virgin.net "Ian Greenwood" writes:
...
>> >You need to upgrade to Microwave99 then.
>>
>> Which will take 3/4 hour to warm one cup of coffee.
>
>You may be able to speed this up by changing the jumper settings on your
>microwave and overclocking the chip
So you just change your microwave into a conventional or possibly fan oven.
Lawrence Kirby
k...@ashi.footprints.net "Kaz Kylheku" writes:
>On Fri, 03 Sep 1999 02:18:37 GMT, Jack Klein <jack...@att.net> wrote:
>>On Thu, 02 Sep 1999 03:19:16 GMT, Eric Amick <eam...@shell.clark.net>
>>wrote in comp.lang.c:
>>
>>> Barry Schwarz <schw...@aol.com.net> wrote:
>>> > If a and b are the same type of variable -
>>>
>>> > a^=b;b^=a;a^=b;
>>>
>>> > will swap their contents without using a third.
>>>
>>> You mean it will if they're both integral types; bitwise operators don't
>>> work with anything else. (It baffles me why anyone thinks this is so
>>> useful, but that's another story.)
>>
>>Actually it is only _guaranteed_ to work if they are unsigned integer
>>types. It is not _guaranteed_ to work if they are signed integer
>>types, and there are a few architectures out there where it won't.
>
>You might be thinking of the implementation-defined value that results from xor
>if one or or both operands are negative; that consideration doesn't actually
>matter since these intermediate values aren't used. The semantics of the XOR
>leads to the exchange of corresponding bits. Since the bits are exchanged, the
>values are.
You might think that, but not me. I think of the problem of of having
two representations of zero in 1's complement and sign magnitude
formats and the fact that assignment is defined in terms of value so there's
nothing to stop it storing zero in whichever representation it likes.
Lawrence Kirby
jack...@att.net "Jack Klein" writes:
...
>I do not see any guarantee in the standard that an XOR on two signed
>integers will not produce a trap representation, which signed integers
>may have.
What standard are you talking about? The current standard does not
have "trap representations". I don't see anything in it that allows
undefined behaviour for bitwise operations when their operands are
both valid integer valued expressions.
> The fact that C89 did not discuss trap values does not mean
>that it did not permit them, as the committee maintains that the
>definition of them in C9X is not a change, merely the correction of an
>oversight.
Even if that is the case I don't see anything in the current standard
that would permit the result of a "valid" bitwise operation to be
a trap representation.
>If there is such a guarantee that I missed, please supply a reference.
You have this backwards - you need to show proof that a trap
representation is allowed. Undefined behaviour can only occur when
the standard say so explicitly or through a *total* lack of definition
of behaviour. Since bitwise operations operations are defined over all
input bit patterns there can be no total lack of definition of behaviour.
So to show that a bitwise operation can result in a trap representation
you will need to quote the part of the standard that says explicitly
that a bitwise operation on two valid integer values can result in
undefined behaviour. Note that since the current standard doesn't
define trap representations explicity they can only exist under the
umbrella of undefined behaviour.
Kaz Kylheku
>You might think that, but not me. I think of the problem of of having
>two representations of zero in 1's complement and sign magnitude
>formats and the fact that assignment is defined in terms of value so there's
>nothing to stop it storing zero in whichever representation it likes.
Oh yes, good point. Because X ^= Y is really X = X ^ Y (except that X is
evaluated but once). So the XOR value may be good, but the assignment could
bugger it up by changing a zero value from one representation to another.
As a rule, whenever I need an object that behaves like a bitfield, I use
an unsigned type.
Kaz Kylheku
>On Sat, 04 Sep 99 02:16:43 GMT, Lawrence Kirby <fr...@genesis.demon.co.uk> wrote:
>>You might think that, but not me. I think of the problem of of having
>>two representations of zero in 1's complement and sign magnitude
>>formats and the fact that assignment is defined in terms of value so there's
>>nothing to stop it storing zero in whichever representation it likes.
>
>Oh yes, good point. Because X ^= Y is really X = X ^ Y (except that X is
>evaluated but once). So the XOR value may be good, but the assignment could
>bugger it up by changing a zero value from one representation to another.
Actually this is wrong: even the XOR value might not be what the programmer
expected. Because the XOR is done between the values of the operands. If
either one is zero, either representation for zero might be used for either
operand for the XOR calculation.
Al Bowers
Kaz Kylheku wrote:
> On Sat, 04 Sep 99 02:16:43 GMT, Lawrence Kirby <fr...@genesis.demon.co.uk> wrote:
> >You might think that, but not me. I think of the problem of of having
> >two representations of zero in 1's complement and sign magnitude
> >formats and the fact that assignment is defined in terms of value so there's
> >nothing to stop it storing zero in whichever representation it likes.
>
> Oh yes, good point. Because X ^= Y is really X = X ^ Y (except that X is
> evaluated but once). So the XOR value may be good, but the assignment could
> bugger it up by changing a zero value from one representation to another.
>
> As a rule, whenever I need an object that behaves like a bitfield, I use
> an unsigned type.
You are causing me concern for the safety of a generic swap() I that have defined
using the XOR routine. I have used it in without problems on three different
implementations.
#include <stdio.h>
struct bio {
char name[30];
unsigned age;
};
void swap(void *p1, void *p2,size_t size) {
unsigned char *uc1 = p1;
unsigned char *uc2 = p2;
int i;
for(i = 0;i < size;i++,uc1++,uc2++) {
*uc1 ^= *uc2; *uc2 ^= *uc1; *uc1 ^= *uc2;}
return;
}
int main(void) {
struct bio james = {"james",18},john = {"john",16};
printf("james = \"%s\" whose age is %u\n",james.name,james.age);
printf("John = \"%s\" whoose age is %u\n",john.name,john.age);
puts("After calling swap");
swap(&james,&john,sizeof(james));
printf("james = \"%s\" whose age is %u\n",james.name,james.age);
printf("John = \"%s\" whoose age is %u\n",john.name,john.age);
return 0;
}
--
Al Bowers
Tampa, FL USA
abo...@combase.com
http://www.gate.net/~abowers/
Daryle Walker
>Can you swap 2 variable without using 3rd one.. Can u show me a code in
>C or C++.
>Thanks.
You don't. There are various hacks (some worthlessly argued over
vigourously in this thread) that can do it for certain types, with certain
probablities of success, but there's no general hack around using a third
variable. With the size of most variables (esp. relative to RAM size),
it's not worth any hack.
--
Daryle Walker
Video Game, Mac, and Internet Junkie
walke751 AT concentric DOT net
Kaz Kylheku
Yes, because none of the implementations were signed-magnitude or
two's complement. Problem is that expressions like *uc1
get promoted to type int, which is signed. A zero valued byte
could give rise to the ``wrong'' zero representation in the
int type. It's an obscure worry, but still.
Anyway; see my big article about the XOR trick. Here your abstract semantics
are calling for six memory accesses each time through the loop not counting
the accesses to the uc1 and uc2 objects themselves. You also have auxiliary
storage anyway because you have declared three locals. Not to mention that
it's unlikely that any of the architectures you will port this to have a
memor-to-memory exclusive or instruction, so the compilers will generate
code that uses temporary storage, and do the XOR between two registers,
or register-to-memory.
Instead of worrying about it, why not rewrite it as:
void swap(void *av, void *bv, size_t size)
{
unsigned char *a = av, *b = *bv;
while (size--) {
unsigned temp = a[size];
a[size] = b[size];
b[size] = temp;
}
}
This works even on the obscure one's complement or sign-magnitude
architectures, because nothing here depends on the representation
of zero.
For fun, try benchmarking the two on a few of the platforms you have ported to.
Joe Maun
Dann Corbit wrote:
>
> Joe Maun <repl...@yahoo.com> wrote in message
> news:37CFFED5...@yahoo.com...
> > Dann Corbit wrote:
> > >
> > > Joe Maun <repl...@yahoo.com> wrote in message
> > > news:37CED12D...@yahoo.com...
> > > >
> > > >
> > > > Martin Ambuhl wrote:
> > > > >
> > > > > >
> > > > > > If a and b are the same type of variable -
> > > > > >
> > > > > > a^=b;b^=a;a^=b;
> > > > > >
> > > > > > will swap their contents without using a third.
> > > > >
> > > > > 1) What happens for a == b?
> > > >
> > > > Their contents are swapped. (given they have integer type.)
> > > Unless, of course, a "is" b. (e.g. they are exactly the same object):
> >
> >
> > Impossible.[1] You must be thinking about C++. (Or perhaps you are
> > seeing stars?)
> As the good fairy says in Cinderella, "Impossible things are happening every
> day."
Not today, though.
>
> > >swap(a,a);
> > >
> > > oops.
> >
> > Given the above rolled into a function:
> > swap(a,b); will not do much either.
> >
> > [1] It might be possible if you see the above as a macro before
> > expansion.
>
> /*
> ** Unsafe macros:
> */
Indeed.
[snip]
> /*
> ** As functions:
> */
>
> #include <stdio.h>
> #include <stdlib.h>
> void swapa(unsigned *a, unsigned *b)
> {
> *a ^= *b, *b ^= *a, *a ^= *b;
> }
As I said, you are seeing stars (asterisks) where in reality there are
none. The point being, a^=b in code after macro expansion can never
refer to the same object, unless you add additional operators. (They can
in C++.)
--
Joe
Dann Corbit
[snip]
> As I said, you are seeing stars (asterisks) where in reality there are
> none. The point being, a^=b in code after macro expansion can never
> refer to the same object, unless you add additional operators. (They can
> in C++.)
Dann Corbit
news:240F72C3E0CBD211806...@kartikeya.bombay.gsslco.co.in...
> You can...
> if A & B are intergers then A & B can be swapped as
> A = A + B
> B = A - B
> A = A - B
> Similarly you can make use of multiplication & division for swapping.
with signed shorts and run a simulation from SHRT_MIN to SHRT_MAX in a
double loop. You should see some surprises right off the bat.