发现N = 2 ** X上使用按位运算的指数[对数为n基地2] [英] Finding the exponent of n = 2**x using bitwise operations [logarithm in base 2 of n]
问题描述
有没有使用按位运算是2的功率提取指数一个简单的方法只？
Is there a straightforward way to extracting the exponent from a power of 2 using bitwise operations only?
编辑：虽然这个问题原本是关于位操作，线程是一个很好看的也是，如果你想知道的什么是求x的最快方法给出Y = 2 **点¯x的在Python 的？
Although the question was originally about bitwise operations, the thread is a good read also if you are wondering "What's the fastest way to find X given Y = 2**X in Python?"
我目前正在优化常规（拉宾 - 米勒素性测试）减少一个偶数 N的形式 2 ** S * D 。我可以在 2 ** S 按部分：
I am currently trying to optimize a routine (Rabin-Miller primality test) that reduces an even number N in the forms 2**s * d. I can get the 2**s part by:
two_power_s = N & -N
但我不能找到一种方法，只提取的取值有位运算。解决方法我目前正在测试没有太多的满意度（他们都是pretty多慢）是：
but I can't find a way to extract just "s" with a bitwise operation. Workarounds I am currently testing without too much satisfaction (they are all pretty much slow) are:
- 使用对数函数
- 操纵的2 ** S二元再presentation（即计算尾随零）
- 循环上除以2，直到结果为1
我用的蟒蛇，但这个问题的答案应该是语言无关的，我想。
I am using python, but the answer to this question should be language agnostic, I suppose.
感谢您提前为您的时间。
Thank you in advance for your time.
推荐答案
至于蟒蛇来说：
- 所有的2指数发现的最快速的方法** x是在一本字典的哈希查找是2（见的权力的 hashlookup 的在code）
- 在按位最快方法是一个叫* unrolled_bitwise *。
- 这两个previous方法已经明确的（但可扩展）的上限。没有硬codeD上限在最快方法（这只要蟒蛇可以处理数最多扩展）为* log_e *。
- The fastest method of all to find the exponent of 2**x is by looking up in a dictionary whose hashes are the powers of 2 (see "hashlookup" in the code)
- The fastest bitwise method is the one called "*unrolled_bitwise*".
- Both previous methods have well-defined (but extensible) upper limits. The fastest method without hard-coded upper limits (which scales up as far as python can handle numbers) is "*log_e*".
- 所有的测量速度低于已通过的
timeit.Timer.repeat（testn，周期），其中testn <已获得/ code>设置为3和周期被自动脚本调整以秒（范围，以获得时间注意：有在已固定在这18/02/2010自动调节机制的错误）。 - 并不是所有的方法可以扩展，这就是为什么我没有测试所有的功能2 的各种权力
- 我没能得到一些建议的方法工作（该函数返回一个错误的结果）。我当时还没有TIEM做一步一步的调试会话：我包括code（评论），以防万一有人察觉通过检查错误（或要执行的调试本身）
- All speed measurements below have been obtained via
timeit.Timer.repeat(testn, cycles)wheretestnwas set to 3 andcycleswas automatically adjusted by the script to obtain times in the range of seconds (note: there was a bug in this auto-adjusting mechanism that has been fixed on 18/02/2010). - Not all methods can scale, this is why I did not test all functions for the various powers of 2
- I did not manage to get some of the proposed methods to work (the function returns a wrong result). I did not yet have tiem to do a step-by-step debugging session: I included the code (commented) just in case somebody spots the mistake by inspection (or want to perform the debug themselves)
FUNC（2 ** 5）
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（2 ** 31）
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（2 ** 128）
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（2 ** 1024）
log_e: 0.00s 100%
log_2: 0.01s 118%
stringcount: 0.02s 354%
olgn: 0.03s 707%
bitcounter: 1.73s 37695%
code
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
这篇关于发现N = 2 ** X上使用按位运算的指数[对数为n基地2]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
