Using Bitwise XOR to exchange variable values in ActionScript
I have been studying some Objective-C in my spare time, and was reading up on Bitwise operators tonight. I came across a simple way to exchange the value of two variables using the Exclusive-OR (XOR) operator that doesn’t require creating a temporary variable.
Normally, if you wanted to exchange the value of two variables, you would have to create a temp variable to store values temporarily (which uses additional memory). For example:
package
{
import flash.display.Sprite;
import flash.system.System;
public class SwitchVariables extends Sprite
{
public function SwitchVariables()
{
var a:int = 5;
var b:int = 6;
var temp:int;
trace("a = " + a + " : b = " + b);
temp = a;
a = b;
b = temp;
trace("a = " + a + " : b = " + b);
}
}
}
Notice that you have to create an additional variable, named temp to temporarily store the value while it is switched.
However, you can use the Bitwise XOR Operator to switch the values without having to create the temporary variable. For example:
package
{
import flash.display.Sprite;
import flash.system.System;
public class SwitchVariables extends Sprite
{
public function SwitchVariables()
{
var a:int = 5;
var b:int = 6;
trace("a = " + a + " : b = " + b);
a ^= b;
b ^= a;
a ^= b;
trace("a = " + a + " : b = " + b);
}
}
}
You can find a good explanation of what the Exclusive OR operator does here and a discussion of the XOR swap algorithm here.
This is probably not needed in most cases (it can make the code a little harder to read), but if you are exchanging the value of variables in a loop and running into memory issues, this might come in handy.
Have any other bitwise operator tips? Post them in the comments.
[...] Lees verder… [...]
XOR Swap algoritme … at PePo’s weblog
22 Oct 07 at 10:22 pm
There is another way:
a=b-a;
b=b-a;
a=b+a;
It works and everyone knows what + or – means:) XOR looks more complicated (but in Your example You can’t go out of range).
Draco
22 Oct 07 at 11:28 pm
You going to start doing some OS X Cocoa programming?
Kyle Hayes
23 Oct 07 at 4:39 am
Even in a loop you’re still only using one additional memory location–reusing the same one over and over again. I don’t think there are any practical applications, especially in ActionScript, where it’s necessary to avoid the extra memory loop. A lot of people ask questions like this in interviews and that’s pretty much all it’s good for, trivia.
Draco,
The +/- operation seems to do the same thing but doesn’t work in edge conditions (values close to min/max number).
Sam
Samuel Neff
23 Oct 07 at 5:11 am
Like others mention clarity in code is really important, but nevertheless this is interesting, thanks.
Tink
23 Oct 07 at 7:04 am
Very interesting, thanks
Julien
23 Oct 07 at 8:43 am
Out of pure curiosity, I just ran some performance tests to see how the two approaches compare. All three tests that I ran were inside a 10 million iteration for-loop. Results are in milliseconds.
Test #1:
c = a;
a = b;
b = c;
Time: 42 ms
–
Test #2:
a ^= b;
b ^= a;
Time: 49ms
–
Test #3:
var d:int = a;
a = b;
b = d;
Time: 48ms
–
So in light of the better performance and code clarity, I would definitely recommend sticking with the temporary variable approach. Thanks for sharing that though Mike, I had not seen that before.
Ryan Taylor
23 Oct 07 at 11:34 am
>Out of pure curiosity, I just ran some performance tests to
Wow. That surprises me a little, as I would expect the XOR to be a little faster…
Can you run your example and look at memory usage?
flash.system.System.totalMemory
I ran it with a simple test (one exchange) and saw no difference, but I assumed that was because the player had been allocated memory by the OS and my code didnt go over that.
mike chambers
mesh@adobe.com
mikechambers
23 Oct 07 at 12:24 pm
Keep in mind. This only works on integers, not on floats.
Luke
23 Oct 07 at 1:58 pm
Mike, I re-ran those tests and checked memory – it was the same each test, every time. So your hypothesis about the allocated memory seems to be accurate. I found an explanation for these results on wikipedia:
“On modern (desktop) CPUs, the XOR technique is considerably slower than using a temporary variable to do swapping. One reason is that modern CPUs strive to execute commands in parallel; see Instruction pipeline. In the XOR technique, the inputs to each operation depend on the results of the previous operation, so they must be executed in strictly sequential order. If efficiency is of tremendous concern, it is advised to test the speeds of both the XOR technique and temporary variable swapping on the target architecture.”
Ryan Taylor
23 Oct 07 at 5:38 pm
@ Samuel
Thats a pretty brutal interview question!
Phil Douglas
23 Oct 07 at 8:23 pm
Good point Ryan. It should run the XORs faster on a RISC system, which are usually optimized for scientific functions. Tested on the my old G4 powerbook and it is the case, but still similar memory usage. Not much use in a practical sense outside a science lab now that most client machines for Flash are now Intel based… ActionScript and bitwise operators!! Are you going to start making Flex Karnaugh maps next Mike? :-)
Doug
24 Oct 07 at 11:55 am
There are virtually unlimited places to make minor improvements of this type…. same way if you need to multiply fixed range numbers, instead of doing the multiplication you can get around it by using a pre-calculated table of log(x) values and accomplish the multiplication with a simple add which should be significantly faster.
Simple logic behind that is that:
a * b = x
exp ( log(a) + log(b) ) = x
log(a) + log(b) = log(x)
So by reading from a table of log values you can replace the multiplication with a simple add.
Obviously this is only an advantage when you multiply fairly small numbers, but nonetheless…. an advantage.
I used many many years ago to multiply 8bit numbers.
–Allan
Allan Pichler
16 Apr 08 at 4:31 pm