Many programmers are aware of a special case where you can use a bitwise shift for multiplication or division when you’re multiplying or dividing by a power of two. For example, you can replace i * 2 with i << 1 and i / 2 with i >> 1. A lesser-known trick works for modulus. But are these alternatives actually any faster? Today's article puts them to the test!

Here are today's competitors:

// Multiplication
i * 8; // normal
i << 3; // bitwise [8 = 2^3, so use 3]
 
// Division
i / 16; // normal
i >> 4; // bitwise [16 = 2^4, so use 4]
 
// Modulus
i % 4; // normal
i & 3; // bitwise [4 = 1 << 2, apply ((1 << 2) - 1), so use 3]

Here's a performance test that performs each of these operations a lot of times:

package
{
	import flash.display.*;
	import flash.utils.*;
	import flash.text.*;
 
	public class FasterDivMod extends Sprite
	{
		private var __logger:TextField = new TextField();
		private function row(...cols): void
		{
			__logger.appendText(cols.join(",")+"\n");
		}
 
		public function FasterDivMod()
		{
			stage.align = StageAlign.TOP_LEFT;
			stage.scaleMode = StageScaleMode.NO_SCALE;
 
			__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 absInt:int;
 
			row("Method", "Time");
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				absInt = i / 4;
			}
			afterTime = getTimer();
			row("Div: i / 4", (afterTime-beforeTime), absInt);
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				absInt = i >> 2;
			}
			afterTime = getTimer();
			row("Div: i >> 2", (afterTime-beforeTime), absInt);
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				absInt = i * 4;
			}
			afterTime = getTimer();
			row("Mul: i * 4", (afterTime-beforeTime), absInt);
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				absInt = i << 2;
			}
			afterTime = getTimer();
			row("Mul: i << 2", (afterTime-beforeTime), absInt);
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				absInt = i % 4;
			}
			afterTime = getTimer();
			row("Mod: i % 4", (afterTime-beforeTime), absInt);
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				absInt = i & 3; // ((1 << 2) - 1) == 3
			}
			afterTime = getTimer();
			row("Mod: i & 3", (afterTime-beforeTime), absInt);
		}
	}
}

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.3.300.271
  • 2.3 Ghz Intel Core i7
  • Mac OS X 10.8.0

And here are the results I got:

Method Time
Div: i / 4 358
Div: i >> 2 224
Mul: i * 4 206
Mul: i << 2 255
Mod: i % 4 918
Mod: i & 3 254

Performance Chart

The above results validate the bitwise versions in two out of three tests: division and modulus. In the multiplication case, the normal version actually performs about 20% faster than the bitwise equivalent. On the other hand, division is nearly twice as fast with the bitwise shift and the bitwise modulus (really just an &) is more than three times faster! So if you're got a lot of divides or mods in your performance-critical code, swap them over to the bitwise versions!

Spot a bug? Know why multiplication is faster than a left bitwise shift and want to fill us all in? Post a comment!