XOR Value Swap Algorithm – Is It Still in Use or Useful?

algorithms

When I first started working a mainframe assembler programmer showed me how they swap to values without using the traditional algorithm of:

a = 0xBABE
b = 0xFADE

temp = a
a = b
b = temp

What they used to swap two values – from a bit to a large buffer – was:

a = 0xBABE
b = 0xFADE

a = a XOR b
b = b XOR a
a = a XOR b

now

b == 0xBABE
a == 0xFADE

which swapped the contents of 2 objects without the need for a third temp holding space.

My question is: Is this XOR swap algorithm still in use and where is it still applicable.

Best Answer

When using xorswap there's a danger of supplying same variable as both arguments to the function which zeroes out the said variable due to it being xor'd with itself which turns all the bits to zero. Of course this itself would result in unwanted behavior regardless of algorithm used, but the behavior might be surprising and not obvious at first glance.

Traditionally xorswap has been used for low-level implementations for swapping data between registers. In practice there are better alternatives for swapping variables in registers. For example Intel's x86 has a XCHG instruction which swaps the contents of two registers. Many times a compiler will figure out the semantics of a such function (it swaps contents of the values passed to it) and can make its own optimizations if needed, so trying to optimize something as trivial as a swap function does not really buy you anything in practice. It's best to use the obvious method unless there's a proven reason why it would be inferior to say xorswap within the problem domain.

Related Solutions

Unit Testing – Testing Random/Non-Deterministic Algorithms

What you actually want to test here, I assume, is that given a specific set of results from the randomiser, the rest of your method performs correctly.

If that's what you're looking for then mock out the randomiser, to make it deterministic within the realms of the test.

I generally have mock objects for all kinds of non-deterministic or unpredictable (at the time of writing the test) data, including GUID generators and DateTime.Now.

Edit, from comments: You have to mock the PRNG (that term escaped me last night) at the lowest level possible - ie. when it generates the array of bytes, not after you turn those into Int64s. Or even at both levels, so you can test your conversion to an array of Int64 works as intended and then test separately that your conversion to an array of DateTimes works as intended. As Jonathon said, you could just do that by giving it a set seed, or you can give it the array of bytes to return.

I prefer the latter because it won't break if the framework implementation of a PRNG changes. However, one advantage to giving it the seed is that if you find a case in production that didn't work as intended, you only need to have logged one number to be able to replicate it, as opposed to the whole array.

All this said, you must remember that it's called a Pseudo Random Number Generator for a reason. There may be some bias even at that level.

Which mathematical properties apply to XOR Swap algorithm (and similar bitwise operator algorithms)

This can be done with any invertable binary operation like XOR or addition. So you could just as well write:

 a ← a + b
 b ← a - b
 a ← a - b

Or more generally, suppose that for some binary (associative, commutative) operator # there is an identity i such that

x # i = i # x = x

and that for every value x there is a value x' such that

x # x' = i

Then you can swap two values using that operator:

a ← a # b
b ← a # b'
a ← a # b'

For addition, x' = -x, but for XOR we have x XOR x = 0 so that x' = x, so that:

a ← a XOR b
b ← a XOR b'
a ← a XOR b'

reduces to

a ← a XOR b
b ← a XOR b
a ← a XOR b

Best Answer

Related Solutions

Unit Testing – Testing Random/Non-Deterministic Algorithms

Which mathematical properties apply to XOR Swap algorithm (and similar bitwise operator algorithms)

Related Topic