maart@cs.vu.nl (Maarten Litmaath) (04/07/89)
sl@van-bc.UUCP (pri=-10 Stuart Lynne) writes:
\For fast generic swapping I use:
\#define swap(a,b) {a^=b;b^=a;a^= b;}
Generic? How about floats?
--
"If it isn't aesthetically pleasing, |Maarten Litmaath @ VU Amsterdam:
it's probably wrong." (jim@bilpin). |maart@cs.vu.nl, mcvax!botter!maartjlw@lznv.ATT.COM (J.L.WOOD) (04/08/89)
> sl@van-bc.UUCP (pri=-10 Stuart Lynne) writes: > \For fast generic swapping I use: > > \#define swap(a,b) {a^=b;b^=a;a^= b;} > Also be careful how you use this algorithm if you are using pointers. I once used this method in a sorting routine as my basic exchange and got badly burned. If a and b point to the same location, you get zero as in 0, nada, goose egg. Joe Wood jlw@lznv.ATT.COM
frank@zen.co.uk (Frank Wales) (04/10/89)
In article <1574@lznv.ATT.COM> jlw@lznv.ATT.COM (J.L.WOOD) writes: >> sl@van-bc.UUCP (pri=-10 Stuart Lynne) writes: >> \For fast generic swapping I use: >> >> \#define swap(a,b) {a^=b;b^=a;a^= b;} >> > >Also be careful how you use this algorithm if you are using pointers. >I once used this method in a sorting routine as my basic exchange and >got badly burned. > >If a and b point to the same location, you get zero as in 0, nada, goose egg. Well, this surprised me, since blurfl^blurfl does give 0, but blurfl^0 gives blurfl again, so you should get it back, unless some pretty funky pointer-to-int conversion is taking place. I tried the following myself (admittedly on a fairly well-behaved machine from HP), #include<stdio.h> #define ptr_swap(a,b) (a=(void *)((unsigned long)a^(unsigned long)b),\ b=(void *)((unsigned long)a^(unsigned long)b),\ a=(void *)((unsigned long)a^(unsigned long)b)) main(argc,argv) char *argv[]; { char *a=argv[0],*b=argv[0]; (void)printf("a=%lx, b=%lx\n",(unsigned long)a,(unsigned long)b); ptr_swap(a,b); (void)printf("a=%lx, b=%lx\n",(unsigned long)a,(unsigned long)b); return 0; } and got: a=68023000, b=68023000 a=68023000, b=68023000 I'd be interested to find out the machine on which this XOR trick fails to swap integral values correctly. [I hardly ever use it, but I'd still expect it to work.] Or is there some portability problem lurking here that my Monday morning mind has missed? -- Frank Wales, Systems Manager, [frank@zen.co.uk<->mcvax!zen.co.uk!frank] Zengrange Ltd., Greenfield Rd., Leeds, ENGLAND, LS9 8DB. (+44) 532 489048 x217
frank@zen.co.uk (Frank Wales) (04/11/89)
In article <1558@zen.UUCP> I wrote: >In article <1574@lznv.ATT.COM> jlw@lznv.ATT.COM (J.L.WOOD) writes: >>> sl@van-bc.UUCP (pri=-10 Stuart Lynne) writes: >>> \For fast generic swapping I use: >>> >>> \#define swap(a,b) {a^=b;b^=a;a^= b;} >>> >> >>Also be careful how you use this algorithm if you are using pointers. >>I once used this method in a sorting routine as my basic exchange and >>got badly burned. >> >>If a and b point to the same location, you get zero as in 0, nada, goose egg. > >Well, this surprised me, [example of why I thought there was no problem deleted] >I'd be interested to find out the machine on which this XOR trick >fails to swap integral values correctly. [I hardly ever use it, but >I'd still expect it to work.] And indeed it does, except when a and b are the *same* (not the same value, but the same object), because the first a^=b toasts both a and b, and you've lost your recovery information. >Or is there some portability problem >lurking here that my Monday morning mind has missed? Well, it's Tuesday now -- thanks to those who mailed me with a wake-up call [I did say I hardly used the trick myself; good job, too ;-)]. -- Frank Wales, Systems Manager, [frank@zen.co.uk<->mcvax!zen.co.uk!frank] Zengrange Ltd., Greenfield Rd., Leeds, ENGLAND, LS9 8DB. (+44) 532 489048 x217
chasm@killer.Dallas.TX.US (Charles Marslett) (04/11/89)
In article <1558@zen.UUCP>, frank@zen.co.uk (Frank Wales) writes: :: In article <1574@lznv.ATT.COM> jlw@lznv.ATT.COM (J.L.WOOD) writes: :: >> sl@van-bc.UUCP (pri=-10 Stuart Lynne) writes: :: >> \For fast generic swapping I use: :: >> :: >> \#define swap(a,b) {a^=b;b^=a;a^= b;} :: >> :: > :: >Also be careful how you use this algorithm if you are using pointers. :: >I once used this method in a sorting routine as my basic exchange and :: >got badly burned. :: > :: >If a and b point to the same location, you get zero as in 0, nada, goose egg. :: :: Well, this surprised me, since blurfl^blurfl does give 0, but blurfl^0 :: gives blurfl again, so you should get it back, unless some pretty funky :: pointer-to-int conversion is taking place. I tried the following :: myself (admittedly on a fairly well-behaved machine from HP), The problem is that the second part "blurfl^0" is really "0^0" and if the original algorithm works at all, the result of swapping "blurfl" with "blurfl" will be zero. :: #include<stdio.h> :: #define ptr_swap(a,b) (a=(void *)((unsigned long)a^(unsigned long)b),\ :: b=(void *)((unsigned long)a^(unsigned long)b),\ :: a=(void *)((unsigned long)a^(unsigned long)b)) :: :: main(argc,argv) :: char *argv[]; :: { :: char *a=argv[0],*b=argv[0]; :: :: (void)printf("a=%lx, b=%lx\n",(unsigned long)a,(unsigned long)b); :: ptr_swap(a,b); The mistake you made here is that you are swapping "a" and "b", too uncover the problem with the macro, try substituting the following line: ptr_swap(a,a); The problem arises with pointers because that is where aliasing (and calling a subroutine with two arguments that are the same address) becomes a problem, not because the swapped values are pointers. What I mean to say, is that the problem is an aliasing one, not a pointer one (Fie!, I can't say anything clearly today...). :: (void)printf("a=%lx, b=%lx\n",(unsigned long)a,(unsigned long)b); :: return 0; :: } :: -- :: Frank Wales, Systems Manager, [frank@zen.co.uk<->mcvax!zen.co.uk!frank] :: Zengrange Ltd., Greenfield Rd., Leeds, ENGLAND, LS9 8DB. (+44) 532 489048 x217 Charles =========================================================================== Charles Marslett STB Systems, Inc. <== Apply all standard disclaimers Wordmark Systems <== No disclaimers required -- that's just me chasm@killer.dallas.tx.us
pinkas@hobbit.intel.com (Israel Pinkas ~) (04/12/89)
In article <1558@zen.UUCP> frank@zen.co.uk (Frank Wales) writes: > In article <1574@lznv.ATT.COM> jlw@lznv.ATT.COM (J.L.WOOD) writes: > >> sl@van-bc.UUCP (pri=-10 Stuart Lynne) writes: > >> \For fast generic swapping I use: > >> > >> \#define swap(a,b) {a^=b;b^=a;a^= b;} > >> > > > >Also be careful how you use this algorithm if you are using pointers. > >I once used this method in a sorting routine as my basic exchange and > >got badly burned. > > > >If a and b point to the same location, you get zero as in 0, nada... > > Well, this surprised me, since blurfl^blurfl does give 0, but blurfl^0 > gives blurfl again, so you should get it back, unless some pretty funky > pointer-to-int conversion is taking place. I tried the following > myself (admittedly on a fairly well-behaved machine from HP), [Code deleted] > I'd be interested to find out the machine on which this XOR trick > fails to swap integral values correctly. [I hardly ever use it, but > I'd still expect it to work.] Or is there some portability problem > lurking here that my Monday morning mind has missed? This fails if you pass the same object to swap() for both arguments. The code that Frank posted passed two copies of the object: #include <stdio.h> #define swap(a,b) {a^=b;b^=a;a^= b;} main() { int a = 10, b = 10, c = 10; printf("a = %x b = %x c = %x\n", a, b, c); swap(a,a) swap(b,c) printf("a = %x b = %x c = %x\n", a, b, c); } Results in: a = a b = a c = a a = 0 b = a c = a A compiler that gives different results is probably broken. -Israel Pinkas -- -------------------------------------- Disclaimer: The above are my personal opinions, and in no way represent the opinions of Intel Corporation. In no way should the above be taken to be a statement of Intel. UUCP: {amdcad,decwrl,hplabs,oliveb,pur-ee,qantel}!intelca!mipos3!cadev4!pinkas ARPA: pinkas%cadev4.intel.com@relay.cs.net CSNET: pinkas@cadev4.intel.com
maart@cs.vu.nl (Maarten Litmaath) (04/13/89)
dg@lakart.UUCP (David Goodenough) writes:
\#define swap(a, b, n) ((a) ^= ((b) & (n)), (b) ^= ((a) & (n)), \
\ (a) ^= ((b) & (n)))
This one still suffers from the following:
swap(*p, *q, ~0);
where p and q point at the same location.
--
"If it isn't aesthetically pleasing, |Maarten Litmaath @ VU Amsterdam:
it's probably wrong." (jim@bilpin). |maart@cs.vu.nl, mcvax!botter!maart