Swap function without temp variable

[Insectoid]

Found this over on Cprogramming.com. Nice use of the XOR operator to eliminate the temp variable from a swap function.

code:

swap(a, b){     a = a XOR b;     b = a XOR b;     a = a XOR b; }

This takes advantage of the fact that a XOR b XOR a = b, similar to the way a RAID works.

after a=a XOR b, a hold the data for both a and b, given that another variable is holding a or b (in this case b).
b = a XOR b retrieves the original a value from a. This can be re-written as b=(a XOR b) XOR b which is equal to b = a XOR b XOR b, which equals the original a.
a = a XOR b retrieves the original b value from a. Since b is now equal to the original a, this is the same as a = a XOR b XOR a, which equals the original b.


It's this kind of stuff that makes me love programming and computer science in general. There's always the naive way (in this case, swapping with a temp variable) and then there's a cool way that involves a bit of creativity.

[bbi5291]

This code will fail if a and b initially point to the same memory address...

[Insectoid]

Who's to say that a and b are pointers? This is pseudocode, I intentionally kept it very general.

if a = b, then a XOR a = 0 XOR a = a

So this should still hold true, unless XORing pointers works differently than other types.

[md]

'Course xor isn't fast except for integer types (pointers, ints, lots, etc.) and it isn't defined for floating point types (so you'd need to cast) and doesn't work with structs.

This is a classic case of premature optimization. There is no good reason for trying to optimize away the swap variable, especially when it's not a universal optimization *and* it decreases readability so much.

[Insectoid]

I never said it was more efficient. I said it was cool and creative. I enjoy writing interesting code to make the reader think a bit. Not expressly obfuscated, just contrasting the norm.

[RandomLetters]

Insectoid @ Sat Feb 12, 2011 1:04 pm wrote:

Who's to say that a and b are pointers? This is pseudocode, I intentionally kept it very general.

if a = b, then a XOR a = 0 XOR a = a

So this should still hold true, unless XORing pointers works differently than other types.

This is not true.
if a = b,
a = a XOR a = 0;
a = a XOR a = 0;
a = a XOR a = 0;

a = 0

edit: this is if the memory location is the same, not if the values are the same

[Insectoid]

You're thinking about this wrong.

Well, I assumed you were XORing the memory addresses themselves. If the compiler didn't throw some sort of error then I would be correct. If you are XORing the values they point to then yeah, you'll end up with zero. I don't see this happening in conventional sorting algorithms or any situation where you'd want to sort though, and if you ever used this in a situation where two pointers could potentially point to the same thing, you shouldn't ever touch a compiler again.

[Tony]

Insectoid @ Sat Feb 12, 2011 1:36 pm wrote:

Not expressly obfuscated, just contrasting the norm.

I trust that you have heard of 0x5f3759df?

[bbi5291]

Also, on the topic of XOR: XOR linked list.

[z_cross_fire]

Insectoid @ Sat Feb 12, 2011 1:36 pm wrote:

I never said it was more efficient. I said it was cool and creative. I enjoy writing interesting code to make the reader think a bit. Not expressly obfuscated, just contrasting the norm.

You can do this too:

code:

a = a + b; b = a - b; a = a - b;

This switches the values of 'a' and 'b'.

[md]

bbi5291 @ 2011-02-12, 11:28 pm wrote:

Also, on the topic of XOR: XOR linked list.

Nifty solution to space constraints... but I shudder to think that it might actually be in use somewhere...

[mirhagk]

md @ Sun Feb 13, 2011 9:12 pm wrote:

bbi5291 @ 2011-02-12, 11:28 pm wrote:

Also, on the topic of XOR: XOR linked list.

Nifty solution to space constraints... but I shudder to think that it might actually be in use somewhere...

I mean why not, you have to iterate to get to middle elements anyways, so why not? It'll save memory, and minimize cache misses (although linked lists already have major cache misses lol).

Along these lines, I have taken to a three array method of declaring objects in games and such. Say for a particle engine where there is a great deal of adding and removing particles, but you really only need like less than 65535. I use an array of my elements and call new on each element. Then I push all the numbers from 0 to 65535 into a 16bit stack. These are my free elements, unused particles. Then I have a 16bit linked list of used particles. To create a new particle only requires popping a 16bit integer and adding to a linked list, so three memory calls. To delete a particle requires only removing it from the linked list and pushing back onto the stack. so again three memory calls.

This means I never have to allocate memory except after the first one, and if the element is stored in the array by value, then every element is stored together in memory, making sure to absolutely minimize cache misses.

Using regular arrays means re-allocation and copying of every element (lists minimize it to every so often, but removing elements still requires copying every element after it), and most other methods actually uses more memory than my method which requires 2 pointers, and a linked list (which is the only expensive piece)

[DemonWasp]

mirhagk: Have you ever actually profiled the performance of that solution against a more naive solution (such as creating a new object each time you need it, or keeping a standard Queue object -- of whatever kind your language likes -- of "free" objects?

I think, in general, you'll find that the performance difference, if there is one, is either negligible or the opposite of what you think. I know I've had this happen to me more than a few times.

[mirhagk]

Well the thing is how do you store active ones. You kinda need a linked list. My only addition is storing unused ones in a stack. The array thing is not needed, I just though to use it so that the would be in the same spot in memory. I suppose it wouldn't have a performance difference using the array or not. Just use a linked list for active objects, and a stack to store inactive ones though. That would definetly perform better, because garbage collection is SOOOO SLOW. Seriously, garbage collection should be avoided at all costs, and recycling objects is a great way to avoid garbage.

[DemonWasp]

Garbage collection can be slow, yes. Or it can be astoundingly fast and helpful: in some JVM implementations, memory allocation is purportedly almost free because the JVM can just hand you the space without making a system call (which tends to be expensive). See here: http://www.ibm.com/developerworks/java/library/j-jtp01274.html

Iteration over a linked list is also quite slow. Depending on implementation (and I don't believe any serious implementation would do this), adding to the end of a linked list can involve iterating over the list.

If you know you'll have at most N items, why not have an array of elements of size N, each with a boolean isActive()? Have you tried this approach and found it to be significantly slower than your current approach?