寻找指数n=2**使用x bitwise operations[对数在基2n]
https://stackoverflow.com/questions/2255177
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
是有一个简单的方式提取的指数从2使用bitwise operations仅?
编辑： 虽然这个问题最初是大约按位操作的，该线是一个很好的阅读如果您想知道 "什么是最快的方式找到X给Y=2X 在蟒蛇?"**
我目前想要优化程序(Rabin-米勒素性测试)，减少了一个 即使是数量 N中的形式 2**s * d.我可以得到的 2**s 部分：
two_power_s = N & -N
但是我不能找到一种方法取的只是"s"一位作。解决方法，我是目前的测试没有太多的满意度(他们都是非常缓慢的)是：
- 使用对数函数
- 操纵的二进制代表2**s(即计数的尾零)
- 循环上分2，直到的结果是1
我使用的蟒蛇，但这个问题的答案应当语言无关，我想。
解决方案 2
简短的回答
尽蟒蛇是有关:
- 的 最快的方法的所有 寻找指数的2**x是通过查找在字典中的散列的权力2(见"hashlookup"在代码)
- 的 最快的一位的方法 是的一个叫做"unrolled_bitwise".
- 这两个以前的方法有明确界定的(但可扩展)的上限制。的 最快的方法，而不硬编码的上限 (其扩展尽蟒蛇可以处理数字)是"log_e".
初步说明
- 所有的速度测量下已经获得通过
timeit.Timer.repeat(testn, cycles)哪里testn设定为3cycles自动调整的脚本以获得时间范围秒(注： 有一个错误，该自动调节机制，该机制已经被固定在18/02/2010). - 不是所有的方法可能的规模, 这就是为什么我没有试验的所有功能的各种权力的2
- 我没能得到一些拟议方法的工作 (功能返回一个错误的结果)。我还没有tiem做一步步骤调试届会议：包括我的代码(注释)只是在情况下，有人点错误地通过检查(或希望执行"调试"本身)
结果，
func(25)**
hashlookup: 0.13s 100%
lookup: 0.15s 109%
stringcount: 0.29s 220%
unrolled_bitwise: 0.36s 272%
log_e: 0.60s 450%
bitcounter: 0.64s 479%
log_2: 0.69s 515%
ilog: 0.81s 609%
bitwise: 1.10s 821%
olgn: 1.42s 1065%
func(231)**
hashlookup: 0.11s 100%
unrolled_bitwise: 0.26s 229%
log_e: 0.30s 268%
stringcount: 0.30s 270%
log_2: 0.34s 301%
ilog: 0.41s 363%
bitwise: 0.87s 778%
olgn: 1.02s 912%
bitcounter: 1.42s 1264%
func(2128)**
hashlookup: 0.01s 100%
stringcount: 0.03s 264%
log_e: 0.04s 315%
log_2: 0.04s 383%
olgn: 0.18s 1585%
bitcounter: 1.41s 12393%
func(21024)**
log_e: 0.00s 100%
log_2: 0.01s 118%
stringcount: 0.02s 354%
olgn: 0.03s 707%
bitcounter: 1.73s 37695%
代码
import math, sys
def stringcount(v):
"""mac"""
return len(bin(v)) - 3
def log_2(v):
"""mac"""
return int(round(math.log(v, 2), 0)) # 2**101 generates 100.999999999
def log_e(v):
"""bp on mac"""
return int(round(math.log(v)/0.69314718055994529, 0)) # 0.69 == log(2)
def bitcounter(v):
"""John Y on mac"""
r = 0
while v > 1 :
v >>= 1
r += 1
return r
def olgn(n) :
"""outis"""
if n < 1:
return -1
low = 0
high = sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but...
while True:
mid = (low+high)//2
i = n >> mid
if i == 1:
return mid
if i == 0:
high = mid-1
else:
low = mid+1
def hashlookup(v):
"""mac on brone -- limit: v < 2**131"""
# def prepareTable(max_log2=130) :
# hash_table = {}
# for p in range(1, max_log2) :
# hash_table[2**p] = p
# return hash_table
global hash_table
return hash_table[v]
def lookup(v):
"""brone -- limit: v < 2**11"""
# def prepareTable(max_log2=10) :
# log2s_table=[0]*((1<<max_log2)+1)
# for i in range(max_log2+1):
# log2s_table[1<<i]=i
# return tuple(log2s_table)
global log2s_table
return log2s_table[v]
def bitwise(v):
"""Mark Byers -- limit: v < 2**32"""
b = (0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000)
S = (1, 2, 4, 8, 16)
r = 0
for i in range(4, -1, -1) :
if (v & b[i]) :
v >>= S[i];
r |= S[i];
return r
def unrolled_bitwise(v):
"""x4u on Mark Byers -- limit: v < 2**33"""
r = 0;
if v > 0xffff :
v >>= 16
r = 16;
if v > 0x00ff :
v >>= 8
r += 8;
if v > 0x000f :
v >>= 4
r += 4;
if v > 0x0003 :
v >>= 2
r += 2;
return r + (v >> 1)
def ilog(v):
"""Gregory Maxwell - (Original code: B. Terriberry) -- limit: v < 2**32"""
ret = 1
m = (not not v & 0xFFFF0000) << 4;
v >>= m;
ret |= m;
m = (not not v & 0xFF00) << 3;
v >>= m;
ret |= m;
m = (not not v & 0xF0) << 2;
v >>= m;
ret |= m;
m = (not not v & 0xC) << 1;
v >>= m;
ret |= m;
ret += (not not v & 0x2);
return ret - 1;
# following table is equal to "return hashlookup.prepareTable()"
hash_table = {...} # numbers have been cut out to avoid cluttering the post
# following table is equal to "return lookup.prepareTable()" - cached for speed
log2s_table = (...) # numbers have been cut out to avoid cluttering the post
其他提示
"语言无关"，并担心表现都非常不兼容的概念。
最现代的处理器有我的指令，"最领先的零".在海湾合作委员会，你可以得到它与__内_工具(x)(这也产生合理的，如果不是最快的，代码为目标，缺少的工具).注意，这个工具是不确定的为零，所以你需要一个额外的分支，以赶上这种情况下，如果它事项中应用程序。
在凯尔特人( http://celt-codec.org )的无网点我们用于编译器缺乏一个工具是由Timothy B.Terriberry:
int ilog(uint32 _v){
int ret;
int m;
ret=!!_v;
m=!!(_v&0xFFFF0000)<<4;
_v>>=m;
ret|=m;
m=!!(_v&0xFF00)<<3;
_v>>=m;
ret|=m;
m=!!(_v&0xF0)<<2;
_v>>=m;
ret|=m;
m=!!(_v&0xC)<<1;
_v>>=m;
ret|=m;
ret+=!!(_v&0x2);
return ret;
}
(评论表明，这被发现是用于支版本和一个查找表的基础版本)
但是如果业绩是关键，你可能不应该是实现这一部分代码在蟒蛇。
你可以做到这一点(lg s)的时间对于任意的长度整数使用一个binsearch.
import sys
def floorlg(n):
if n < 1:
return -1
low=0
high=sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but...
while True:
mid = (low+high)//2
i = n >> mid
if i == 1:
return mid
if i == 0:
high = mid-1
else:
low = mid+1
为固定的尺寸整数，一个查找表应该以最快的速度解决方案，而且很可能最好的整体。
它似乎喜欢的范围内是已知的。让我们假设它上升到1<<20，只是为了使它更加有意思：
max_log2=20
因此作一个清单，(生效)的地图的一个整数，其基2对数。下面将要做的把戏：
log2s_table=[0]*((1<<max_log2)+1)
for i in range(max_log2+1):
log2s_table[1<<i]=i
(这不会做任何有用的号码，是不是权力的两个；问题陈述表明，他们不需要处理。将会很容易解决，虽然。)
功能，以获得对数是很简单的，并且可以很容易地以内联:
def table(v):
return log2s_table[v]
我不能保证测试码我写的是完全相同的，因为一个正在用来获得的实例的时间安排，但这是相当快的 stringcount 代码:
stringcount: 0.43 s.
table: 0.16 s.
由于所有数值在本表的不到256个，我想知道是否使用一串而不是一个列表中，将更快，或者也许 array.array 字节，但没有骰子：
string: 0.25 s.
arr: 0.21 s.
使用 dict 要做到查找的是另一种可能性，考虑利用的方式只有权力的两个正在检查：
log2s_map=dict([(1<<x,x) for x in range(max_log2+1)])
def map(v):
return log2s_map[v]
结果这不是因为好，但：
map: 0.20 s.
只是为了好玩一个还可以使用 hex 方法上的浮动对象为得到一串，包括(作为它的最后一部分)的基2指数的数量。这是一点点慢慢来提取在一般，但是，如果指数是永远只会是一个数字这是可以做到直截了当的：
def floathex(v):
return ord(float(v).hex()[-1])-48
这纯粹是出于娱乐的价值，但因为它是uncompetetive--虽然令人惊讶的是，仍然快于按位的方法。
因此它看起来像使用一个清单是要走的路。
(这种做法不会的规模无限期的，由于有限的记忆，但弥补的执行速度将不会取决于 max_log2, 或者输入值、以任何方式，你会注意到，当运行蟒蛇的代码。关于存储的消耗，如果我记得我python内部是否正确，这表将占约 (1<<max_log2)*4 字节，因为其内容是所有小整数的解释将实习生。因此，当 max_log2 是20,这是关于4M.)
这实际上是一个注释性能测试发布的。我发布此作为一个答案有适当的代码格式和缩进
mac,你可以尝试一展开执行bitseach建议通过马克*拜尔斯?也许它只是列入，减慢下来。在理论上这个方法应该比别人快。
它看起来像这样的东西，尽管我不确定是否格式是正确的蟒蛇但是我想你可以看到它是什么应该做的。
def bitwise(v):
r = 0;
if( v > 0xffff ) : v >>= 16; r = 16;
if( v > 0x00ff ) : v >>= 8; r += 8;
if( v > 0x000f ) : v >>= 4; r += 4;
if( v > 0x0003 ) : v >>= 2; r += 2;
return r + ( v >> 1 );
如果python股java缺乏unsingned整数将需要这样的事情：
def bitwise(v):
r = 0;
if( v & 0xffff0000 ) : v >>>= 16; r = 16;
if( v > 0x00ff ) : v >>= 8; r += 8;
if( v > 0x000f ) : v >>= 4; r += 4;
if( v > 0x0003 ) : v >>= 2; r += 2;
return r + ( v >> 1 );
迟到的缔约方，但如何 int.bit_length(n) - 1?你的要求简单，这似乎是最简单的到我.该CPython实现合理的性能。
