oesterle@wpi.wpi.edu (Shawn H. Oesterle) (03/28/90)
Problem:
Swap two pointers without using a third pointer.
Example:
{
void * x, * y, * tmp;
tmp = x;
x = y;
y = x;
}
Make a piece of code which has the same effect as this, but without
using the 'tmp' variable (in C, of course).
Hint:
Two numbers may be swaped without using any other memory by executing
the following statements:
int x, y; /* or you can chose double, long, etc. */
x += y;
y = x - y;
x -= y;
Answer:
I don't know, that's why I'm asking you!
Shawn Oesterle {oesterle@wpi.wpi.edu}mcdaniel@amara.uucp (Tim McDaniel) (03/28/90)
oesterle@wpi.wpi.edu (Shawn H. Oesterle) asks how to swap two pointers
without using a third pointer.
Swap-macros-that-use-no-intermediate-variables appear in comp.lang.c
every so often. They usually use exclusive-OR, and hence only work
for integral types. Oesterle's Variant,
x += y; y = x - y; x -= y;
can fail if an intermediate expression overflows.
You can't do portably swap arbitrary legal pointer values without
using an intermediate variable. In short, "no".
(I've never had a problem scrounging data space for an intermediate
value, and I *never* want to burn the extra CPU time or risk overflow.
If this discussion is fresh and interesting to you, I'm glad, and you
have a perfect right to discuss it in comp.lang.c all you want. But
I'm sorry to tell you I'm an old sourpuss, and I'm afraid that this
subject is going into my KILL file immediately.)
--
Tim McDaniel
Applied Dynamics International, Ann Arbor, MI
Internet: mcdaniel%amara.uucp@mailgw.cc.umich.edu
UUCP: {uunet,sharkey}!amara!mcdanieljc@atcmp.nl (Jan Christiaan van Winkel) (03/28/90)
From article <10289@wpi.wpi.edu>, by oesterle@wpi.wpi.edu (Shawn H. Oesterle):
! Problem:
! Swap two pointers without using a third pointer.
! Example:
! {
! void * x, * y, * tmp;
! tmp = x;
! x = y;
! y = x;
! }
!
! Make a piece of code which has the same effect as this, but without
! using the 'tmp' variable (in C, of course).
The problem is that pointers cannot be used in arithmatic operations
without the danger for inportability. Supposing x and y are ints (or longs),
you can do the following:
x=x^y; y=x^y; x=x^y; /* swap x and y */
casting the pointers x and y to a long and v.v. is your responsability...
JC
--
=============================================================================
Jan Christiaan van Winkel Tel: +31 80 566880 jc@atcmp.nl
AT Computing P.O. Box 1428 6501 BK Nijmegen The Netherlands
=============================================================================rmacfarq@cs.strath.ac.uk (Roderick F MacFarquhar IE87) (03/28/90)
In article <10289@wpi.wpi.edu> oesterle@wpi.wpi.edu (Shawn H. Oesterle) writes: > >Problem: > Swap two pointers without using a third pointer. [code using temp deleted] >Hint: > Two numbers may be swaped without using any other memory by executing > the following statements: > > int x, y; /* or you can chose double, long, etc. */ > > x += y; > y = x - y; > x -= y; But isn't there is a problem of potential overflow on the x += y instruction. I think its been given before in this group but how about.. #define SWAP(X,Y) \ {(X) ^= (Y) ; \ (Y) ^= (X) ; \ (X) ^= (Y) ;} >Shawn Oesterle {oesterle@wpi.wpi.edu} _._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._ Roderick MacFarquhar - Information Eng IV, Strathclyde University Janet rmacfarq@cs.strath.ac.uk Internet rmacfarq%cs.strath.ac.uk@nsf.ac.uk Voice (but I'm rarely home - sob :'{ ) +44 (0)41 339 0263 'How many fibres are intertwined in a shreaded wheat biscuit ?' ~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~"~
swh@hpcupt1.HP.COM (Steve Harrold) (03/29/90)
>>> Problem: >>> Swap two pointers without using a third pointer. Answer: The sequence: x ^= y ; y ^= x ; x ^= y ; will exchange the contents of two like-sized values, "x" and "y". To answer your specific question, you will probably have to coerce your pointer variables to int (or long) to make this sequence work. Of course, once you do that, you no longer have portable code!!. Do you have a practical need to bypass the use of a temporary variable? If this is just an intellectual exercise, then post some more. I think many of us would enjoy them.
kdq@demott.COM (Kevin D. Quitt) (03/29/90)
In article <MCDANIEL.90Mar27200111@rollmops.amara.uucp> mcdaniel@amara.uucp (Tim McDaniel) writes: > >>oesterle@wpi.wpi.edu (Shawn H. Oesterle) asks how to swap two pointers >>without using a third pointer. > >You can't do portably swap arbitrary legal pointer values without >using an intermediate variable. In short, "no". ???????????? (God, I love it when people say things are impossible (:-{>} ) I originally just mailed the answer, since I didn't want to clutter the net. However... void swap_pointers( x, y ) long *x, *y; /* whichever declaration is required */ { *x ^= *y; *y ^= *x; *x ^= *y; } Or you can do it in-line. (Seems silly to do it either way, but this *is* a puzzle, not a request for practical code). Note that this technique can actually be used to exchange two (presumably large) strings - it's insensitive to data type or contents, and cannot cause overflow or any other error condition that wouldn't happen by reading or writing the same locations. Disclaimer: This assumes that pointers are not longer than longs (or some other defined type). On the other hand, how many machines do you know that have longer addresses than data? kdq -- Kevin D. Quitt Manager, Software Development DeMott Electronics Co. VOICE (818) 988-4975 14707 Keswick St. FAX (818) 997-1190 Van Nuys, CA 91405-1266 MODEM (818) 997-4496 Telebit PEP last 34 12 N 118 27 W srhqla!demott!kdq kdq@demott.com "Next time, Jack, write a God-damned memo!" - Jack Ryan - Hunt for Red October
buck@granite.cr.bull.com (Ken Buck) (03/29/90)
In article <99@demott.COM> kdq@demott.COM (Kevin D. Quitt) writes: [re: the 'swap()' brain teaser] > Disclaimer: This assumes that pointers are not longer than longs (or >some other defined type). On the other hand, how many machines do you >know that have longer addresses than data? Hate to rain on your parade, but machines which don't implement byte addressing will cause you problems! In these cases, char pointers are implemented as a word address (typically 32 bits) plus a byte offset (perhaps 16 bits), hence we have a pointer type which is bigger than a long. Trust me - these things exist! :-) (Of course, this is not meant to dampen the spirits of ingenious problem-solving - just realize that your solution is not portable...)
cjc@ulysses.att.com (Chris Calabrese) (03/29/90)
In article <99@demott.COM>, kdq@demott.COM (Kevin D. Quitt) writes: > In article <MCDANIEL.90Mar27200111@rollmops.amara.uucp> mcdaniel@amara.uucp (Tim McDaniel) writes: | > | >>oesterle@wpi.wpi.edu (Shawn H. Oesterle) asks how to swap two pointers | >>without using a third pointer. | > | >You can't do portably swap arbitrary legal pointer values without | >using an intermediate variable. In short, "no". | ???????????? | | (God, I love it when people say things are impossible (:-{>} ) | | I originally just mailed the answer, since I didn't want to clutter the | net. However... | | | void swap_pointers( x, y ) | | long *x, *y; /* whichever declaration is required */ | { | *x ^= *y; | *y ^= *x; | *x ^= *y; | } | | | Or you can do it in-line. (Seems silly to do it either way, but | this *is* a puzzle, not a request for practical code). Note that this | technique can actually be used to exchange two (presumably large) | strings - it's insensitive to data type or contents, and cannot cause | overflow or any other error condition that wouldn't happen by reading or | writing the same locations. | | Disclaimer: This assumes that pointers are not longer than longs (or | some other defined type). On the other hand, how many machines do you | know that have longer addresses than data? NO, NO, NO, NO, NO!!! This only works on machines where a pointer is a simple number!!! It doesn't work on machines with segmented architecture (intel, etc). And, it doesn't work on machines with different sized pointers for different types of pointers (Dual 86/80?). -- Name: Christopher J. Calabrese Brain loaned to: AT&T Bell Laboratories, Murray Hill, NJ att!ulysses!cjc cjc@ulysses.att.com Obligatory Quote: ``Anyone who would tell you that would also try and sell you the Brooklyn Bridge.''
will@kfw.COM (Will Crowder) (03/30/90)
In article <99@demott.COM> kdq@demott.COM (Kevin D. Quitt) writes: > >(God, I love it when people say things are impossible (:-{>} ) > >void swap_pointers( x, y ) > >long *x, *y; /* whichever declaration is required */ > { > *x ^= *y; > *y ^= *x; > *x ^= *y; > } (God, I love it when people post wrong answers to the net. :) :) ) The code above swaps the longs *pointed to* by x and y, it does not swap the pointers themselves. I assume what you meant was: void swap_pointers(void **x,void **y) { *x ^= *y; *y ^= *x; *x ^= *y; } which you would then call as: int main(void) { void *x,*y; x = &something1; y = &something2; swap_pointers(&x,&y); /* * x now points to something2 and y points to something1; note * that something1 and something2 are still at the same location * in memory */ } Of course, this is not in the least bit portable, or even advisable. Avoiding a temp in this case, and retaining portability and ANSI compliance, is probably darn near impossible if not actually impossible. I can't think of any way to do it. The restrictions on the arithmetic you can do with pointers prevent any of the "wow-neato" swap methods from being used. Use a temp, save a life. Will
kdq@demott.COM (Kevin D. Quitt) (03/30/90)
In article <12726@ulysses.att.com> cjc@ulysses.att.com (Chris Calabrese) writes: >In article <99@demott.COM>, kdq@demott.COM (Kevin D. Quitt) writes: [... my stuff deleted ] >NO, NO, NO, NO, NO!!! >This only works on machines where a pointer is a simple number!!! >It doesn't work on machines with segmented architecture (intel, etc). It *DOES* work on the intel machines. The only Intel processors it might not work on are the 386 and 486, since they have 48 bit addresses. But the C compilers for these processors don't give you direct access to 48bit addresses. >And, it doesn't work on machines with different sized pointers for >different types of pointers (Dual 86/80?). It *WILL* work on any machine whose long data is as big as the address. It will not work (as has been pointed out to me) on some of the BULL machines, which have 32 bit addresses (for words) and an additional 16 bits for character address offset, and whose C compiler use 48 bits for pointers. On the other hand, you could union the pointer to a character, int or long array and do the conversion piecewise. (Again, nobody said anything about efficiency). (Asbestos undergarments in place... (:-{>} kdq -- Kevin D. Quitt Manager, Software Development DeMott Electronics Co. VOICE (818) 988-4975 14707 Keswick St. FAX (818) 997-1190 Van Nuys, CA 91405-1266 MODEM (818) 997-4496 Telebit PEP last 34 12 N 118 27 W srhqla!demott!kdq kdq@demott.com "Next time, Jack, write a God-damned memo!" - Jack Ryan - Hunt for Red October
boyd@necisa.ho.necisa.oz (Boyd Roberts) (03/30/90)
From article <10289@wpi.wpi.edu>, by oesterle@wpi.wpi.edu (Shawn H. Oesterle): > Problem: > Swap two pointers without using a third pointer. > Arithmetic operations with pointers that don't point to `the same array' are not defined. Apart from that, this `Brain Teaser' is a pointless discourse into abstruse and non-portable constructs. Boyd Roberts boyd@necisa.ho.necisa.oz.au ``When the going gets wierd, the weird turn pro...''
peter@ficc.uu.net (Peter da Silva) (03/30/90)
swap(x,y,len)
char *x, *y;
size_t len;
{
while(len>0) {
*x^=*y; *y^=*x; *x^=*y;
x++; y++; len--;
}
}
Usage: swap(x, y, sizeof(x));
Sort of a pyrrhic victory, though.
--
_--_|\ `-_-' Peter da Silva. +1 713 274 5180. <peter@ficc.uu.net>.
/ \ 'U`
\_.--._/
vhays@nosun.UUCP (Kirk Hays) (04/04/90)
In article <100@demott.COM> kdq@demott.COM (Kevin D. Quitt) writes: [ discussion of (nasty) micro-efficiency hack eliminated, one guaranteed not to work on machines with disjoint address spaces, sizeof (char*) > sizeof (long), or 'active' pointers] > It *DOES* work on the intel machines. The only Intel processors it >might not work on are the 386 and 486, since they have 48 bit addresses. >But the C compilers for these processors don't give you direct access to >48bit addresses. Wrong. I know of at least six (6) different compilers for the 386/486, some of them non-Intel, that support 48 bit pointers. They're very good for shaking bugs out of programs which are written with the "all the world is a flat address space of 32 bits" mentality. I say, use a temporary variable, and let the compiler figure out that you're doing a swap. Nasty hacks like this one should be a last resort, and should probably appear only in device drivers and the like... -- Kirk Hays - I'm the NRA, NRA-ILA, CCRKBA, SAF, and Neal Knox is my lobbyist.
lucio@proxima.UUCP (Lucio de Re) (04/07/90)
In article <10289@wpi.wpi.edu> oesterle@wpi.wpi.edu (Shawn H. Oesterle) writes: >Problem: > Swap two pointers without using a third pointer. >Hint: > Two numbers may be swaped without using any other memory by executing > the following statements: > > int x, y; /* or you can chose double, long, etc. */ > > x += y; > y = x - y; > x -= y; Well, I'd never have thought of it, thanks. Might be useful when programming the i8051. As for the pointers swap, I suppose you can't do the same because you need an integer in the middle. Maybe a cast will save you, but is it worth it (or portable?). ---------------------------------------------------------------------- I used to design nuclear reactors and you should see the code that engineers and scientists come up with. Yuuuck! Spaghetti everywhere. -------------------------------------------------- (Kenneth L Moore) - Lucio de Re ...uunet!ddsw1!olsa99!proxima!lucio -------------------------------------------------------- lucio@proxima Disclaimer: He must have been joking!
unhd (Anthony Lapadula) (04/10/90)
In a response from someone who shall remain nameless [regarding swap()]: > [Swap() cannot be portably implemented.] > > Period. End of Quote. Followups directed to alt.stupid.solutions.to. > stupid.questions. Looks like the sharks are out in force, eh? Lets remember that you, too, were once an amateur. Perhaps you even asked a stupid.question yourself. -- Anthony (uunet!unhd!al) Lapadula
condict@cs.vu.nl (Michael Condict) (04/12/90)
In article <2039@awdprime.UUCP> cs.utexas.edu!ibmchs!auschs!sanders.austin.ibm.com!sanders (Tony Sanders) writes: |In article <10289@wpi.wpi.edu> oesterle@wpi.wpi.edu (Shawn H. Oesterle) writes: |-Example: |- { |- void * x, * y, * tmp; |- |- tmp = x; |- x = y; |- y = x; |- } |- Make a piece of code which has the same effect as this, but without |- using the 'tmp' variable (in C, of course). |This is really quite easy AND ANSI compliant. | |You see, to "make a piece of code which has the same effect" as your |sample code, this will suffice: | void *x, *y; | x = y; | |If you don't believe me then double check your sample code. Actually, the sample code can be optimized more than that. It is exactly equivalent to the following statement: ; since the variables are all local to the block. -- Michael Condict condict@cs.vu.nl Vrije University Amsterdam