在凯尔特( http://celt-codec.org )我们用于缺少CLZ的编辑者的无分支CLZ是由Timothy B。特瑞贝里:

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

但如果性能如此关键,您可能不应该用python实现这部分代码。

简短回答

就python而言:

• 这个 最快的方法 要找到2**x的指数,需要查找哈希为2幂的字典(请参阅“ “在代码中)
• 最快逐位法 这是一个叫“的” 按位展开 ".
• 无硬编码上限的最快方法 (在python可以处理数字的范围内,它可以向上扩展)是“ 日志 ".

1. 以下所有速度测量值均通过以下方式获得: timeit.Timer.repeat(testn, cycles) 哪里 testn 设置为3,然后 cycles 由脚本自动调整,以获得秒范围内的时间( 此自动调整机构中存在一个错误,已于2010年2月18日修复)。
2. 并非所有方法都可以扩展
3. 我没有设法使一些提议的方法发挥作用

结果

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)

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

有一个页面有很多这样的技巧和黑客。它是为C语言编写的,但其中许多语言也应该使用Python(尽管性能显然会有所不同)。你想要的是 here 以及以后。

你可以试试 this 例如:

register unsigned int r = 0; // result of log2(v) will go here
for (i = 4; i >= 0; i--) // unroll for speed...
{
  if (v & b[i])
  {
    v >>= S[i];
    r |= S[i];
  } 
}

看起来它可以很容易地转换成Python。

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

对于固定大小的整数,查找表应该是最快的解决方案,而且可能是最好的整体解决方案。

晚会迟到了,那你呢 int.bit_length(n) - 1 ? 你要求的是直截了当,对我来说这似乎是最简单的。CPython实现看起来性能相当好。

• Reference documentation
• CPython source code

似乎范围是已知的。让我们假设它上升到1<&书信电报;20,只是为了让它更有趣:

max_log2=20

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

这纯粹是为了娱乐价值,尽管它没有竞争力——但令人惊讶的是,它仍然比按位方法快。

(由于内存有限,这种方法不会无限扩展,但为了弥补这一点,执行速度将不取决于 max_log2 ,或输入值,以运行python代码时会注意到的任何方式。关于内存消耗,如果我正确地记住了python的内部结构,该表将占用大约 (1<<max_log2)*4 字节,因为内容都是解释器将自动实习的小整数。那么,什么时候 最大对数2

这实际上是对mac发布的性能测试的评论。我将此作为一个答案发布,以获得正确的代码格式和缩进

它看起来是这样的,虽然我不确定格式是否适合python,但我想您可以看到它应该做什么。

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

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