Stanford’s Sean Eron Anderson has a great page titled Bit Twiddling Hacks. This is a great resource for C programmers looking to employ bitwise operators (& | ^ ~ << <<< >> >>> etc.) to speed up their code. But what about AS3 programmers? We have bitwise operators too, but will the same tricks work for us? Today’s article ports some of these bit twiddling hacks to AS3 and tests to see if any ground is gained.

A few months ago I tested just one of these bit twiddling hacks and found that Math.abs could be sped up by 20% for integers. Today I’ll test several more of the hacks:

  • Sign of integer
  • Detect different signs
  • Minimum integer (like Math.min)
  • Maximum integer (like Math.max)
  • Conditionally set or clear bits
  • Conditionally negate a value without branching
  • Count bits set

Here’s the test app that does the testing:

package
{
	import flash.utils.getTimer;
	import flash.text.TextFieldAutoSize;
	import flash.text.TextField;
	import flash.display.Sprite;
 
	public class BitTwiddlingHacks extends Sprite
	{
		private static const BITS_SET_TABLE_256:Vector.<int> = new <int>[0, 0 +1, 0 +1, 0 +2, 0 +1, 0 +1 +1, 0 +1 +1, 0 +1 +2, 0 +1, 0 +1 +1, 0 +1 +1, 0 +1 +2, 0 +2, 0 +2 +1, 0 +2 +1, 0 +2 +2, 0 +1, 0 +1 +1, 0 +1 +1, 0 +1 +2, 0 +1 +1, 0 +1 +1 +1, 0 +1 +1 +1, 0 +1 +1 +2, 0 +1 +1, 0 +1 +1 +1, 0 +1 +1 +1, 0 +1 +1 +2, 0 +1 +2, 0 +1 +2 +1, 0 +1 +2 +1, 0 +1 +2 +2, 0 +1, 0 +1 +1, 0 +1 +1, 0 +1 +2, 0 +1 +1, 0 +1 +1 +1, 0 +1 +1 +1, 0 +1 +1 +2, 0 +1 +1, 0 +1 +1 +1, 0 +1 +1 +1, 0 +1 +1 +2, 0 +1 +2, 0 +1 +2 +1, 0 +1 +2 +1, 0 +1 +2 +2, 0 +2, 0 +2 +1, 0 +2 +1, 0 +2 +2, 0 +2 +1, 0 +2 +1 +1, 0 +2 +1 +1, 0 +2 +1 +2, 0 +2 +1, 0 +2 +1 +1, 0 +2 +1 +1, 0 +2 +1 +2, 0 +2 +2, 0 +2 +2 +1, 0 +2 +2 +1, 0 +2 +2 +2, 1, 1 +1, 1 +1, 1 +2, 1 +1, 1 +1 +1, 1 +1 +1, 1 +1 +2, 1 +1, 1 +1 +1, 1 +1 +1, 1 +1 +2, 1 +2, 1 +2 +1, 1 +2 +1, 1 +2 +2, 1 +1, 1 +1 +1, 1 +1 +1, 1 +1 +2, 1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +2, 1 +1 +2 +1, 1 +1 +2 +1, 1 +1 +2 +2, 1 +1, 1 +1 +1, 1 +1 +1, 1 +1 +2, 1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +2, 1 +1 +2 +1, 1 +1 +2 +1, 1 +1 +2 +2, 1 +2, 1 +2 +1, 1 +2 +1, 1 +2 +2, 1 +2 +1, 1 +2 +1 +1, 1 +2 +1 +1, 1 +2 +1 +2, 1 +2 +1, 1 +2 +1 +1, 1 +2 +1 +1, 1 +2 +1 +2, 1 +2 +2, 1 +2 +2 +1, 1 +2 +2 +1, 1 +2 +2 +2, 1, 1 +1, 1 +1, 1 +2, 1 +1, 1 +1 +1, 1 +1 +1, 1 +1 +2, 1 +1, 1 +1 +1, 1 +1 +1, 1 +1 +2, 1 +2, 1 +2 +1, 1 +2 +1, 1 +2 +2, 1 +1, 1 +1 +1, 1 +1 +1, 1 +1 +2, 1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +2, 1 +1 +2 +1, 1 +1 +2 +1, 1 +1 +2 +2, 1 +1, 1 +1 +1, 1 +1 +1, 1 +1 +2, 1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +2, 1 +1 +2 +1, 1 +1 +2 +1, 1 +1 +2 +2, 1 +2, 1 +2 +1, 1 +2 +1, 1 +2 +2, 1 +2 +1, 1 +2 +1 +1, 1 +2 +1 +1, 1 +2 +1 +2, 1 +2 +1, 1 +2 +1 +1, 1 +2 +1 +1, 1 +2 +1 +2, 1 +2 +2, 1 +2 +2 +1, 1 +2 +2 +1, 1 +2 +2 +2, 2, 2 +1, 2 +1, 2 +2, 2 +1, 2 +1 +1, 2 +1 +1, 2 +1 +2, 2 +1, 2 +1 +1, 2 +1 +1, 2 +1 +2, 2 +2, 2 +2 +1, 2 +2 +1, 2 +2 +2, 2 +1, 2 +1 +1, 2 +1 +1, 2 +1 +2, 2 +1 +1, 2 +1 +1 +1, 2 +1 +1 +1, 2 +1 +1 +2, 2 +1 +1, 2 +1 +1 +1, 2 +1 +1 +1, 2 +1 +1 +2, 2 +1 +2, 2 +1 +2 +1, 2 +1 +2 +1, 2 +1 +2 +2, 2 +1, 2 +1 +1, 2 +1 +1, 2 +1 +2, 2 +1 +1, 2 +1 +1 +1, 2 +1 +1 +1, 2 +1 +1 +2, 2 +1 +1, 2 +1 +1 +1, 2 +1 +1 +1, 2 +1 +1 +2, 2 +1 +2, 2 +1 +2 +1, 2 +1 +2 +1, 2 +1 +2 +2, 2 +2, 2 +2 +1, 2 +2 +1, 2 +2 +2, 2 +2 +1, 2 +2 +1 +1, 2 +2 +1 +1, 2 +2 +1 +2, 2 +2 +1, 2 +2 +1 +1, 2 +2 +1 +1, 2 +2 +1 +2, 2 +2 +2, 2 +2 +2 +1, 2 +2 +2 +1, 2 +2 +2 +2];
 
		private var logger:TextField = new TextField();
		private function row(...cols): void { logger.appendText(cols.join(",")+"\n"); }
 
		public function BitTwiddlingHacks()
		{
			logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(logger);
 
			init();
		}
 
		private function init(): void
		{
			var beforeTime:int;
			var afterTime:int;
			var i:int;
			var REPS:int = 100000000;
			var normalTime:int;
			var twiddlingTime:int;
			var input:int;
			var input2:int;
			var inputBool:Boolean;
			var result:int;
			var resultBool:Boolean;
			var BitsSetTable256:Vector.<int> = BITS_SET_TABLE_256;
 
			row("Function,Normal,Twiddling");
 
			//////////////////////////////////
			// Sign of integer (when positive)
			//////////////////////////////////
 
			input = 10;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = input < 0 ? -1 : 0;
			}
			afterTime = getTimer();
			normalTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = -(input>>31);
			}
			afterTime = getTimer();
			twiddlingTime = afterTime - beforeTime;
 
			row("Sign of integer (when positive)", normalTime, twiddlingTime);
 
			//////////////////////////////////
			// Sign of integer (when negative)
			//////////////////////////////////
 
			input = -10;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = input < 0 ? -1 : 0;
			}
			afterTime = getTimer();
			normalTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = -(input>>31);
			}
			afterTime = getTimer();
			twiddlingTime = afterTime - beforeTime;
 
			row("Sign of integer (when negative)", normalTime, twiddlingTime);
 
			/////////////////////////
			// Detect different signs
			/////////////////////////
 
			input = 10;
			input2 = 30;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				resultBool = (input < 0 && input2 < 0) || (input >= 0 && input2 >= 0);
			}
			afterTime = getTimer();
			normalTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				resultBool = ((input ^ input2) < 0);
			}
			afterTime = getTimer();
			twiddlingTime = afterTime - beforeTime;
 
			row("Detect different signs", normalTime, twiddlingTime);
 
			//////////////////
			// Minimum integer
			//////////////////
 
			input = 10;
			input2 = 30;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = input < input2 ? input : input2;
			}
			afterTime = getTimer();
			normalTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = input2 ^ ((input ^ input2) & -(input < input2 ? 1 : 0));
			}
			afterTime = getTimer();
			twiddlingTime = afterTime - beforeTime;
 
			row("Minimum integer", normalTime, twiddlingTime);
 
			//////////////////
			// Maximum integer
			//////////////////
 
			input = 10;
			input2 = 30;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = input > input2 ? input : input2;
			}
			afterTime = getTimer();
			normalTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = input ^ ((input ^ input2) & -(input < input2 ? 1 : 0));
			}
			afterTime = getTimer();
			twiddlingTime = afterTime - beforeTime;
 
			row("Maximum integer", normalTime, twiddlingTime);
 
			/////////////////////////////////////////
			// Conditionally set or clear bits (true)
			/////////////////////////////////////////
 
			input = 0; // to modify
			input2 = 6; // mask
			inputBool = true; // set bits
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = inputBool ? (input | input2) : (input & ~input2);
			}
			afterTime = getTimer();
			normalTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = (input & ~input2) | (-(inputBool ? 1 : 0) & input2);
			}
			afterTime = getTimer();
			twiddlingTime = afterTime - beforeTime;
 
			row("Conditionally set or clear bits (true)", normalTime, twiddlingTime);
 
			//////////////////////////////////////////
			// Conditionally set or clear bits (false)
			//////////////////////////////////////////
 
			input = 0; // to modify
			input2 = 6; // mask
			inputBool = false; // clear bits
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = inputBool ? (input | input2) : (input & ~input2);
			}
			afterTime = getTimer();
			normalTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = (input & ~input2) | (-(inputBool ? 1 : 0) & input2);
			}
			afterTime = getTimer();
			twiddlingTime = afterTime - beforeTime;
 
			row("Conditionally set or clear bits (false)", normalTime, twiddlingTime);
 
			////////////////////////////////////////////////////////
			// Conditionally negate a value without branching (true)
			////////////////////////////////////////////////////////
 
			input = 30;
			inputBool = false; // do negate (this flag is to NOT negate)
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = inputBool ? -input : input;
			}
			afterTime = getTimer();
			normalTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				input2 = inputBool ? 1 : 0; // temp
				result = (input2 ^ (input2 - 1)) * input;
			}
			afterTime = getTimer();
			twiddlingTime = afterTime - beforeTime;
 
			row("Conditionally negate a value without branching (true)", normalTime, twiddlingTime);
 
			/////////////////////////////////////////////////////////
			// Conditionally negate a value without branching (false)
			/////////////////////////////////////////////////////////
 
			input = 30;
			inputBool = true; // don't negate (this flag is to NOT negate)
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = inputBool ? -input : input;
			}
			afterTime = getTimer();
			normalTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				input2 = inputBool ? 1 : 0; // temp
				result = (input2 ^ (input2 - 1)) * input;
			}
			afterTime = getTimer();
			twiddlingTime = afterTime - beforeTime;
 
			row("Conditionally negate a value without branching (false)", normalTime, twiddlingTime);
 
			/////////////////
			// Count bits set
			/////////////////
 
			input = 30;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				input2 = input; // temp
				for (result = 0; input2; input2 >>= 1)
				{
					result += input2 & 1;
				}
			}
			afterTime = getTimer();
			normalTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				result = BitsSetTable256[input & 0xff] + 
					BitsSetTable256[(input >> 8) & 0xff] + 
					BitsSetTable256[(input >> 16) & 0xff] + 
					BitsSetTable256[input >> 24];
			}
			afterTime = getTimer();
			twiddlingTime = afterTime - beforeTime;
 
			row("Count bits set", normalTime, twiddlingTime);
		}
	}
}

I ran this test app in the following environment:

  • Flex SDK (MXMLC) 4.6.0.23201, compiling in release mode (no debugging or verbose stack traces)
  • Release version of Flash Player 11.5.31.2
  • 2.3 Ghz Intel Core i7
  • Mac OS X 10.8.2

And here are the results I got:

Function Normal Twiddling
Sign of integer (when positive) 220 220
Sign of integer (when negative) 217 216
Detect different signs 261 164
Minimum integer 216 370
Maximum integer 156 372
Conditionally set or clear bits (true) 194 402
Conditionally set or clear bits (false) 205 402
Conditionally negate a value without branching (true) 184 186
Conditionally negate a value without branching (false) 282 216
Count bits set 957 586

Performance Graph

There’s definitely a mixed bag of performance here. Sometimes the bit twiddling version is two times slower, sometimes it’s just as fast, sometimes it’s a little faster, and sometimes it’s two times faster. While always fancier, bitwise methods are not always faster. Thankfully, the above performance results should serve as a handy reference guide for the next time you’re thinking of using some bitwise tricks. You could double your performance… or cut it in half.

Spot a bug? Have a suggestion? Post a comment!