Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!ginosko!uunet!mfci!karzes From: karzes@mfci.UUCP (Tom Karzes) Newsgroups: comp.lang.c Subject: Re: swap(x,y) Message-ID: <987@m3.mfci.UUCP> Date: 23 Aug 89 04:34:11 GMT References: <40@dgis.daitc.mil> Sender: karzes@mfci.UUCP Reply-To: karzes@mfci.UUCP (Tom Karzes) Organization: Multiflow Computer Inc., Branford Ct. 06405 Lines: 30 In article <40@dgis.daitc.mil> generous@dgis.daitc.mil (Curtis Generous) writes: >tg1e+@andrew.cmu.edu (Timothy R. Gottschalk) writes: >> To swap two variables x,y in C without using a temporary variable: Here are some ways to do it: 1. x += y y = x - y x -= y 2. x -= y y += x x = y - x 3. x = y - x y -= x x += y 4. x ^= y y ^= x x ^= y In each case, the operation used is such that given the value of x op y, along with either x or y, one can recover the original value of the other variable. This reminds me of an old space saving trick for doubly linked lists. One can create a linked list which may be traversed in either direction using a single pointer field. In that field, store the xor (or the sum, or the difference) of the predecessor and successor addresses. (I know this isn't legal C, so don't bother flaming. The point is that it works on normal computer hardware.) All you have to do to traverse the list in a given direction is keep the value of the previous node around and xor it with the pointer field in the current node. In fact, the code which does this doesn't even have to know the direction in which it's going. You just have to keep pointers to the first and last elements, and seed the walk at either end with a zero previous pointer. The catch is that this method only works for walking the list from the head or the tail. You can't start in the middle because you don't have any adjacent address to get you started. For example, you can't delete an element from the list if all you have is its address; some additional context is needed.