按位运算代替乘、除和取模:哪个更快?

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽
本文为转载文章,若有侵权或违规行为,请联系我,会及时处理相关内容。

支付宝微  信

许多程序员都意识到这个特例,就是当你乘或除一个2次幂的时候,你可以用位移运算符来代替乘法和除法。比如:你可以用i << 1代替i*2和用i>>1代替i / 2。还有一个不太为人所知的方法是取模。但是这些方法实际上哪个更快呢?今天这篇文章就要来测试它们!

以下就是今天的竞争对手:

// 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]

 

这就是多次执行这些操作后的性能测试:

 

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);
		}
	}
}

我在以下环境中运行了这个测试应用程序:
• 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

下面就是我得到的结果:

上述结果表明按位操作方法在三分之二的测试中取胜:除法和取模。在乘法案例中,正常方法在同等情况下实际上比按位操作快20%。另一方面,除法几乎是按位操作的两倍,并且按位取模(实际上仅仅是个&)更是快3倍以上。所以如果在你的效率关键代码中有很多除法或取模运算的话,将它们用按位运算代替吧!


原文链接:http://jacksondunstan.com/articles/1946


分类: JAVA, 技术, 效率, 编程 | 标签: , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。