有没有一种简单的方法只使用位运算从2的幂中提取指数?
编辑:虽然问题最初是关于按位操作的,但如果您想知道“在Python中,在Y=2的情况下,找到X的最快方法是什么,那么这个线程也是一个很好的读物?”**
我目前正在尝试优化一个例程(Rabin-Miller primality test),该例程可以以2**s * d
的形式减少偶数N。我可以通过以下方法获得2**s
部分:
two_power_s = N & -N
但是我找不到一种方法来通过按位操作提取“s”。我目前正在测试的解决方案没有太多的满足感(它们都非常缓慢)是:
我使用的是python,但我想这个问题的答案应该是语言不可知的。
简短的回答
就python而言:
初步说明
timeit.Timer.repeat(testn, cycles)
获得的,其中testn
被设置为3,并且cycles
被脚本自动调整以获得秒范围内的时间(注意:此自动调整机制中存在一个错误,该错误已在2010年2月18日修复)。结果
函数(25)**
函数(231)**
函数(2128)**
函数(21024)**
代码
有一个页面有很多这样的技巧和黑客。它是为C编写的,但其中许多也应该在Python中工作(尽管性能显然会有所不同)。你想要的位子是here及以后的位子。
您可以尝试this例如:
看起来它可以很容易地转换成Python。
“语言不可知论”和对性能的担忧几乎是不相容的概念。
大多数现代处理器都有一条CLZ指令“count leading zero”。在GCC中,您可以使用内置的clz(x)来实现它(如果不是最快的话,也可以为缺少clz的目标生成合理的代码)。请注意,这个CLZ没有为零定义,因此如果在应用程序中很重要,您将需要一个额外的分支来捕获这种情况。
在CELT(http://celt-codec.org)中,我们用于缺少CLZ的编译器的无枝CLZ是由Timothy B.Terriberry编写的:
(注释表明,这比分支版本和基于查找表的版本快)
但是,如果性能如此关键,您可能不应该用python实现这部分代码。
相关问题 更多 >
编程相关推荐