445,926 Members | 1,828 Online
Need help? Post your question and get tips & solutions from a community of 445,926 IT Pros & Developers. It's quick & easy.

swap() function without tmp

 P: n/a Hi, I found the swap() function without a temporary variable. void swap(int *x, int *y){ *x ^= *y; *y ^= *x; *x ^= *y; } So, I wrote the next code that exchange the double. void dswap(double *x, double *y){ *(int *)x ^= *(int *)y; *((int *)x + 1) ^= *((int *)y + 1); *(int *)y ^= *(int *)x; *((int *)y + 1) ^= *((int *)x + 1); *(int *)x ^= *(int *)y; *((int *)x + 1) ^= *((int *)y + 1); } But it is dirty. Does it rewrite more simply? --- Regards, OSHIMA Nov 14 '05 #1
28 Replies

 P: n/a sh*************@mail.goo.ne.jp (OSHIMA) writes: Hi, I found the swap() function without a temporary variable. void swap(int *x, int *y){ *x ^= *y; *y ^= *x; *x ^= *y; } So, I wrote the next code that exchange the double. void dswap(double *x, double *y){ *(int *)x ^= *(int *)y; *((int *)x + 1) ^= *((int *)y + 1); *(int *)y ^= *(int *)x; *((int *)y + 1) ^= *((int *)x + 1); *(int *)x ^= *(int *)y; *((int *)x + 1) ^= *((int *)y + 1); } But it is dirty. Does it rewrite more simply? This is nonportable, slow, and counterproductive. Use a temporary, and read the FAQ: 20.15c: How can I swap two values without using a temporary? A: The standard hoary old assembly language programmer's trick is: a ^= b; b ^= a; a ^= b; But this sort of code has little place in modern, HLL programming. Temporary variables are essentially free, and the idiomatic code using three assignments, namely int t = a; a = b; b = t; is not only clearer to the human reader, it is more likely to be recognized by the compiler and turned into the most-efficient code (e.g. using a swap instruction, if available). The latter code is obviously also amenable to use with pointers and floating-point values, unlike the XOR trick. See also questions 3.3b and 10.3. -- "To get the best out of this book, I strongly recommend that you read it." --Richard Heathfield Nov 14 '05 #2

 P: n/a OSHIMA wrote: Hi, I found the swap() function without a temporary variable. I would still recommend using a temporary variable. -- == Eric Gorr ========= http://www.ericgorr.net ========= ICQ:9293199 === "Therefore the considerations of the intelligent always include both benefit and harm." - Sun Tzu == Insults, like violence, are the last refuge of the incompetent... === Nov 14 '05 #3

 P: n/a OSHIMA wrote: void swap(int *x, int *y){ *x ^= *y; *y ^= *x; *x ^= *y; } So, I wrote the next code that exchange the double. void dswap(double *x, double *y){ *(int *)x ^= *(int *)y; *((int *)x + 1) ^= *((int *)y + 1); *(int *)y ^= *(int *)x; *((int *)y + 1) ^= *((int *)x + 1); *(int *)x ^= *(int *)y; *((int *)x + 1) ^= *((int *)y + 1); } Hmm, if there was a memxor() function that would exclusive or one region of memory with another, then this could be done somewhat portably. memand() and memor() to complete the set. Maybe it should be added to C2009. -- glen Nov 14 '05 #4

 P: n/a Daniel scribbled the following: On 13 May 2004 19:57:29 -0700 sh*************@mail.goo.ne.jp (OSHIMA) wrote: void swap(int *x, int *y){ *x ^= *y; *y ^= *x; *x ^= *y; } Beware that this function will not work if *x == *y. I'd say you should not swap in this case and notify the impossibility somehow. Or just use a function or a macro that uses a third variable. Speaking for myself only. It won't work if x == y, you mean. If x == y, the first line will set *x to 0, and the remaining lines will be XORing 0 by 0, yielding 0. If x != y but *x == *y it can still work. Imagine *x == 10 and *y == 10. First line: *x = 10 ^ 10, i.e. *x = 0 Second line: *y = 10 ^ 0, i.e. *y = 10 Third line: *x = 0 ^ 10, i.e. *x = 10 Output: *x == 10 and *y == 10, as requested. -- /-- Joona Palaste (pa*****@cc.helsinki.fi) ------------- Finland --------\ \-- http://www.helsinki.fi/~palaste --------------------- rules! --------/ Nov 14 '05 #5

 P: n/a sh*************@mail.goo.ne.jp (OSHIMA) writes: Hi, I found the swap() function without a temporary variable. void swap(int *x, int *y){ *x ^= *y; *y ^= *x; *x ^= *y; } This fails if x and y point to the same int object. It can also fail if type int has trap representations. I'm not sure whether it's reliable if the representation is either one's-complement or sign-magnitude (each of which has two distinct representations for 0) -- and even if it is, it's probably not worth the effort to prove it. If your goal is to swap two variables, just use a temporary. If you're doing this as an intellectual exercise, have fun, but watch out for the pitfalls. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> Schroedinger does Shakespeare: "To be *and* not to be" Nov 14 '05 #6

 P: n/a OSHIMA wrote: So, I wrote the next code that exchange the double. void dswap(double *x, double *y){ *(int *)x ^= *(int *)y; *((int *)x + 1) ^= *((int *)y + 1); *(int *)y ^= *(int *)x; *((int *)y + 1) ^= *((int *)x + 1); *(int *)x ^= *(int *)y; *((int *)x + 1) ^= *((int *)y + 1); } How do you know for sure that sizeof double is 2 * sizeof int? Kees Nov 14 '05 #7

 P: n/a sh*************@mail.goo.ne.jp (OSHIMA) wrote in message news:... I found the swap() function without a temporary variable. void swap(int *x, int *y){ *x ^= *y; *y ^= *x; *x ^= *y; } basically this is a silly trick. It is also well known. It only works on scalars. It probably isn't faster than the sane version. And what does this do? swap (&a, &a); So, I wrote the next code that exchange the double. void dswap(double *x, double *y){ *(int *)x ^= *(int *)y; *((int *)x + 1) ^= *((int *)y + 1); *(int *)y ^= *(int *)x; *((int *)y + 1) ^= *((int *)x + 1); *(int *)x ^= *(int *)y; *((int *)x + 1) ^= *((int *)y + 1); } But it is dirty. Does it rewrite more simply? void dswap(double *x, double *y) { double t; t = &a; &a = &b; &b = t; } -- Nick Keighley Nov 14 '05 #8

 P: n/a In sh*************@mail.goo.ne.jp (OSHIMA) writes: Hi,I found the swap() function without a temporary variable. void swap(int *x, int *y){ *x ^= *y; *y ^= *x; *x ^= *y; }So, I wrote the next code that exchange the double. void dswap(double *x, double *y){ *(int *)x ^= *(int *)y; *((int *)x + 1) ^= *((int *)y + 1); *(int *)y ^= *(int *)x; *((int *)y + 1) ^= *((int *)x + 1); *(int *)x ^= *(int *)y; *((int *)x + 1) ^= *((int *)y + 1); }But it is dirty. Does it rewrite more simply? Before wasting time with such things, ask yourself: what is the point of not doing the swap the natural way, using a temporary? The *portable* way of doing what you want to do is to swap the two doubles on a byte by byte basis. The result is going to be ludicrously slow, compared to the normal procedure. The nonportable way of solving your problem is aliasing your doubles with unsigned long long's and swapping the latter. It relies on a few assumptions not guaranteed by the standard and on the existence of the type long long (or some other 64-bit type) on your implementation. Dan -- Dan Pop DESY Zeuthen, RZ group Email: Da*****@ifh.de Nov 14 '05 #9

 P: n/a In glen herrmannsfeldt writes: the set. Maybe it should be added to C2009. ^^^^^ Apparently, there is going to be no such thing. C99 is far too good to be replaced after a mere decade ;-) Dan -- Dan Pop DESY Zeuthen, RZ group Email: Da*****@ifh.de Nov 14 '05 #10

 P: n/a Nick Keighley wrote: sh*************@mail.goo.ne.jp (OSHIMA) wrote in message news:... I found the swap() function without a temporary variable. void swap(int *x, int *y){ *x ^= *y; *y ^= *x; *x ^= *y; } basically this is a silly trick. It is also well known. It only works on scalars. "scalars" is too general. Bitwise operations are only defined for integer types. -- pete Nov 14 '05 #11

 P: n/a ni***********@marconi.com (Nick Keighley) wrote in message news:<8a**************************@posting.google. com>... void dswap(double *x, double *y) { double t; t = &a; &a = &b; &b = t; } I didn't know you could store the address of a variable in a non-pointer(here double) variable. Or was that a typo? Nov 14 '05 #12

 P: n/a In Keith Thompson writes: sh*************@mail.goo.ne.jp (OSHIMA) writes: Hi, I found the swap() function without a temporary variable. void swap(int *x, int *y){ *x ^= *y; *y ^= *x; *x ^= *y; }This fails if x and y point to the same int object. This can be trivially tested. It can also fail if type int has trap representations. I'm not surewhether it's reliable if the representation is either one's-complementor sign-magnitude (each of which has two distinct representations for0) -- and even if it is, it's probably not worth the effort to proveit. Trivially avoided by using pointers to unsigned int instead. Unless we start introducing padding bits and other nonsense into the picture... If your goal is to swap two variables, just use a temporary. Couldn't agree more. If you're doing this as an intellectual exercise, have fun, but watch outfor the pitfalls. The more you study it as an intellectual exercise, the more its futility becomes obvious. However, memswap() would have made sense in the standard C library, as there is no portable and efficient method of implementing it in C. Dan -- Dan Pop DESY Zeuthen, RZ group Email: Da*****@ifh.de Nov 14 '05 #13

 P: n/a "Beni" wrote in message news:e5**************************@posting.google.c om... ni***********@marconi.com (Nick Keighley) wrote in message news:<8a**************************@posting.google. com>... void dswap(double *x, double *y) { double t; t = &a; &a = &b; &b = t; } I didn't know you could store the address of a variable in a non-pointer(here double) variable. Or was that a typo? Should be * instead of & throughout, and either a and b should be x and y (or y and x) throughout, or x and y should be a and b (or b and a). Other than that, it was perfect :). Alex Nov 14 '05 #14

 P: n/a Dan Pop wrote: In glen herrmannsfeldt writes: the set. Maybe it should be added to C2009. ^^^^^ Apparently, there is going to be no such thing. C99 is far too good to be replaced after a mere decade ;-) Or there might not be enough C99 compilers available by 2009? I was always so disappointed the Fortran didn't keep up the trend from 66 to 77 with 88 and 99. -- glen Nov 14 '05 #15

 P: n/a pete writes: [...] "scalars" is too general. Bitwise operations are only defined for integer types. And personally, I value my sanity too much to try to use bitwise operators on anything other than unsigned integer types. That's not to say that you *can't* use bitwise operators on signed integer types, but it rarely makes sense to do so. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> Schroedinger does Shakespeare: "To be *and* not to be" Nov 14 '05 #16

 P: n/a Hi, Thanks a lot of reply messages. How do you know for sure that sizeof double is 2 * sizeof int? Kees It is my mistake. A 'int' means a 'long'. :) Hmm, if there was a memxor() function that would exclusive or one region of memory with another, then this could be done somewhat portably. memand() and memor() to complete the set. Maybe it should be added to C2009. -- glen A memxor() not implemeted my environment(library) yet. But it's easy to implement for me. Thanks a valuable information. I would still recommend using a temporary variable. Eric *portable* way of doing what you want to do is to swap the two doubles on a byte by byte basis. The result is going to be ludicrously slow, Dan Yes, I know my program is slow and tricky. But, imagine the microchip programming like a PIC. (which has 64/128 byte's mem only --It is off topic here?) A double tmp variable needs 8 bytes stack and microchip has not engough memory. So, I need a double swap() without tmp rather than a speed. Don't say 'Use Assembly Language'. :( The nonportable way of solving your problem is aliasing your doubles with unsigned long long's and swapping the latter. void dswap(double *x, double *y){ *(long long *)x ^= *(long long *)y; *(long long *)y ^= *(long long *)x; *(long long *)x ^= *(long long *)y; } In my programming environment, it worked correctly and object code has not use the surplus mem. Thanks a lot. >> for all --- Regards, OSHIMA Nov 14 '05 #17

 P: n/a Keith Thompson wrote: pete writes: [...] "scalars" is too general. Bitwise operations are only defined for integer types. And personally, I value my sanity too much to try to use bitwise operators on anything other than unsigned integer types. That's not to say that you *can't* use bitwise operators on signed integer types, but it rarely makes sense to do so. I have only one code example where it is OK to use a bitwise operator on an int. The code example is unsigned mask = ((unsigned char)-1 >> 1) + 1; for masking the most significant bit of a byte. The left operand of the shift operator is promoted to either int or unsigned. In the case when it is promoted to int, the sign bit is not involved in the operations. -- pete Nov 14 '05 #18

 P: n/a On 15 May 2004 04:33:10 -0700, in comp.lang.c , sh*************@mail.goo.ne.jp (OSHIMA) wrote: Hi,Thanks a lot of reply messages. How do you know for sure that sizeof double is 2 * sizeof int? KeesIt is my mistake. A 'int' means a 'long'. :) It doesn't matter, the question still stands. The answer by the way is "you can't - C doesn't mandate the sizes of types, only how much data they must be able to hold". -- Mark McIntyre CLC FAQ CLC readme: ----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==---- http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups ---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =--- Nov 14 '05 #20

 P: n/a In glen herrmannsfeldt writes: Dan Pop wrote: In glen herrmannsfeldt writes:the set. Maybe it should be added to C2009. ^^^^^ Apparently, there is going to be no such thing. C99 is far too good to be replaced after a mere decade ;-)Or there might not be enough C99 compilers available by 2009? Then, it is a fair bet that there will NEVER be enough C99 compilers. Any provider of C implementations who didn't upgrade to C99 after 10 years most likely is not interested in providing a C99 implementation at all. Dan -- Dan Pop DESY Zeuthen, RZ group Email: Da*****@ifh.de Nov 14 '05 #21

 P: n/a In Keith Thompson writes: pete writes:[...] "scalars" is too general. Bitwise operations are only defined for integer types.And personally, I value my sanity too much to try to use bitwiseoperators on anything other than unsigned integer types. That's notto say that you *can't* use bitwise operators on signed integer types,but it rarely makes sense to do so. It makes sense to do so any time you (have good reasons to) expect a positive result. Dan -- Dan Pop DESY Zeuthen, RZ group Email: Da*****@ifh.de Nov 14 '05 #22

 P: n/a Dan Pop wrote: In glen herrmannsfeldt writes:Dan Pop wrote:In glen herrmannsfeldt writes:the set. Maybe it should be added to C2009. ^^^^^Apparently, there is going to be no such thing. C99 is far too good tobe replaced after a mere decade ;-)Or there might not be enough C99 compilers available by 2009? Then, it is a fair bet that there will NEVER be enough C99 compilers. Any provider of C implementations who didn't upgrade to C99 after 10 years most likely is not interested in providing a C99 implementation at all. Dan I keep getting subliminal messages from here and elsewhere that C99 is a non-starter. C89 on the other hand did the right thing. It seems nobody 'needs' C99. K&R2 is a best-seller at \$40. All of us have one and newbies are still buying. The C99 Standard doesn't draw flies at \$18. Maybe nobody wants it. I could be wrong. I have been before. I'll spare you all the list. -- Joe Wright mailto:jo********@comcast.net "Everything should be made as simple as possible, but not simpler." --- Albert Einstein --- Nov 14 '05 #23

 P: n/a On Tue, 18 May 2004 19:23:55 -0400, Joe Wright wrote: I keep getting subliminal messages from here and elsewhere that C99 is a non-starter. C89 on the other hand did the right thing. It seems nobody 'needs' C99. K&R2 is a best-seller at \$40. All of us have one and newbies are still buying. The C99 Standard doesn't draw flies at \$18. Maybe nobody wants it. I could be wrong. I have been before. I'll spare you all the list. I won't speak to the long-term viability of C99 as a whole, but I do know this: GCC, the GNU Compiler Collection, implements a conforming C89 compiler. It gives all the right warnings (after a bit of command-line prodding) and implements all the right semantics. It also implements a non-conforming attempt at a C99 compiler, some of which is accomplished by simply not giving warnings or errors for traditional GNU C extensions. This state of affairs seems to trouble nobody important. Nearly all new code in the open-source community is either (nominally) C89 or GNU C, and none that I've found require C99 features beyond what GCC will provide in a non-conforming mode. GCC is the standard compiler for this market. If GCC supports it, there's a chance it will be used. Contrariwise, if GCC ignores it, there's a chance the community as a whole just doesn't care. (Of course, I don't see the need for C99, so I'm biased. I think C89 gives us function prototypes, the ability to return structs and unions, good pointer semantics and limitations, and the ability to write idiomatic code in a conforming way. C99 gives us compound literals, the bool type, restricted pointers, and long long. No killer features, nothing I really missed when programming C before.) -- yvoregnevna gjragl-guerr gjb-gubhfnaq guerr ng lnubb qbg pbz To email me, rot13 and convert spelled-out numbers to numeric form. "Makes hackers smile" makes hackers smile. Nov 14 '05 #24

 P: n/a In Joe Wright writes: I keep getting subliminal messages from here and elsewhere that C99is a non-starter. C89 on the other hand did the right thing. Itseems nobody 'needs' C99. K&R2 is a best-seller at \$40. All of us ^^^^^^have one and newbies are still buying. The C99 Standard doesn't drawflies at \$18. Maybe nobody wants it. ^^^^^^ "Nobody" is too strong. The demand exists, but it's not significant enough to justify the effort of producing conforming C99 implementations. Dan -- Dan Pop DESY Zeuthen, RZ group Email: Da*****@ifh.de Nov 14 '05 #25

 P: n/a In August Derleth writes: I won't speak to the long-term viability of C99 as a whole, but I doknow this: GCC, the GNU Compiler Collection, implements a conforming C89compiler. It gives all the right warnings (after a bit of command-lineprodding) and implements all the right semantics. It also implements anon-conforming attempt at a C99 compiler, some of which is accomplished bysimply not giving warnings or errors for traditional GNU C extensions.This state of affairs seems to trouble nobody important. Nearly all newcode in the open-source community is either (nominally) C89 or GNU C, andnone that I've found require C99 features beyond what GCC will provide ina non-conforming mode.GCC is the standard compiler for this market. If GCC supports it, there'sa chance it will be used. Contrariwise, if GCC ignores it, there's achance the community as a whole just doesn't care. It was a major blunder to ignore GNU C when designing C99. If a few C99 features didn't have semantics conflicting with the semantics of the same features in GNU C, gcc would have had a conforming -std=c99 mode by now. The issue is purely political, there are no technical difficulties. Furthermore, if C99 had more GNU C features, the demand for C99 would have been far greater. E.g. the addition of typeof and block expressions would have greatly improved the capabilities of the function-like macros. Of course, these considerations have nothing to do with the standard C99 library, which is where most of work of upgrading from C89 to C99 goes. (Of course, I don't see the need for C99, so I'm biased. I think C89 givesus function prototypes, the ability to return structs and unions, goodpointer semantics and limitations, and the ability to write idiomatic codein a conforming way. C99 gives us compound literals, the bool type,restricted pointers, and long long. No killer features, nothing I reallymissed when programming C before.) Integer 64-bit support seems to be important to many people, but most C89 implementations in current use provide it, one way or another, so people see no point in switching to C99 just for that. And those liking the idea of , can have it for C89, too (free implementations exist). And Fortran programmers are not going to abandon their favourite programming language and switch to C99 simply because it now supports many traditional Fortran features (VLAs, complex arithmetic and library functions, generic function calls). Dan -- Dan Pop DESY Zeuthen, RZ group Email: Da*****@ifh.de Nov 14 '05 #26

 P: n/a Dan Pop wrote: It was a major blunder to ignore GNU C when designing C99. GNU C wasn't ignored, but it wasn't considered to be any more important than any other existing implementation. And since none of the GCC developers or serious users could be bothered to join the committee or attend meetings (not even occasionally), it probably didn't receive as much attention as implementations that had advocates attending committee meetings, or as much as it deserved. Microsoft C was in much the same boat for the same reason. If a few C99 features didn't have semantics conflicting with the semantics of the same features in GNU C, gcc would have had a conforming -std=c99 mode by now. The issue is purely political, there are no technical difficulties. That is simply incorrect. Although some of the conflicts were undoubtedly caused inadvertently due to simple ignorance (see above), others were deliberate reactions to technical shortcomings in GCC. Describing the issue as "political" is not accurate -- the committee has never had any animosity toward GCC, despite the converse not being true. (But I must hasten to add that that attitude is long gone and the current GCC developers seem genuinely interested in producing a conforming implementation.) -Larry Jones That gives me a FABULOUS idea. -- Calvin Nov 14 '05 #27

 P: n/a la************@ugsplm.com wrote: Dan Pop wrote: It was a major blunder to ignore GNU C when designing C99. GNU C wasn't ignored, but it wasn't considered to be any more important than any other existing implementation. And since none of the GCC developers or serious users could be bothered to join the committee or attend meetings (not even occasionally), it probably didn't receive as much attention as implementations that had advocates attending committee meetings, or as much as it deserved. Microsoft C was in much the same boat for the same reason. I suspect that the high price of such 'joining', together with the unpaid volunteer aspect of gcc development, had more than a little to do with it. Microsoft simply doesn't care, any standards impede their freedom to 'innovate, foul, and charge'. -- Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net) Available for consulting/temporary embedded and systems. USE worldnet address! Nov 14 '05 #28

 P: n/a In <8i************@jones.homeip.net> la************@ugsplm.com writes: Dan Pop wrote: It was a major blunder to ignore GNU C when designing C99.GNU C wasn't ignored, but it wasn't considered to be any more importantthan any other existing implementation. Which is sheer stupidity. Not all existing implementations are equally important. And since none of the GCCdevelopers or serious users could be bothered to join the committee orattend meetings (not even occasionally), it probably didn't receive asmuch attention as implementations that had advocates attending committeemeetings, or as much as it deserved. GNU C is pretty well documented. And its extensions are nicely grouped together in a separate chapter. Microsoft C was in much the same boat for the same reason. In other words, the two implementations *by far* the most important have been given Cinderella status, for purely bureaucratic reasons. Yeah, that's typical committee thinking and a clear explanation for why the C programming community at large is turning a deaf ear and a blind eye to C99. If gcc and Microsoft C were C99-conforming today, C89 would have been history: any implementor targeting major hosted platforms and still willing to survive would have followed their example. If a few C99 features didn't have semantics conflicting with the semantics of the same features in GNU C, gcc would have had a conforming -std=c99 mode by now. The issue is purely political, there are no technical difficulties.That is simply incorrect. Although some of the conflicts wereundoubtedly caused inadvertently due to simple ignorance (see above),others were deliberate reactions to technical shortcomings in GCC. The idea was not to introduce semantic differences between GNU C features with a well established status and new C99 features with the same name and/or purpose. Not to adopt all the technical shortcomings of GNU C in the C99 standard... Describing the issue as "political" is not accurate -- the committee hasnever had any animosity toward GCC, despite the converse not being true. You misunderstood my words. I was talking about gcc's conformance issue as being purely political: the gcc people don't want to break their semantics, apparently not even in -std=c99 mode. I attribute the ignorance of GNU C features to sheer committee stupidity, not to any political agenda. (But I must hasten to add that that attitude is long gone and thecurrent GCC developers seem genuinely interested in producing aconforming implementation.) Well, I haven't noticed any *documented* progress since 2001 or so... Dan -- Dan Pop DESY Zeuthen, RZ group Email: Da*****@ifh.de Nov 14 '05 #29