Encontrando o expoente de n = 2 ** x usando operações bitwise [logaritmo na base 2 de n
https://stackoverflow.com/questions/2255177
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Existe uma maneira direta de extrair o expoente de uma potência de 2 usando apenas operações bitwise?
EDITAR: Embora a questão fosse originalmente sobre operações bit -bit, o tópico é uma boa leitura também se você está se perguntando "Qual é a maneira mais rápida de encontrar x dado y = 2X em Python?"**
Atualmente, estou tentando otimizar uma rotina (Teste de Primalidade Rabin-Miller) que reduz um numero par N nas formas 2**s * d. Eu posso conseguir o 2**s parte por:
two_power_s = N & -N
Mas não consigo encontrar uma maneira de extrair apenas "s"Com uma operação uma operação bit. Atualmente, as soluções alternativas estou testando sem muita satisfação (elas são praticamente lentas) são:
- usando a função logaritmo
- manipulando a representação binária de 2 ** s (ou seja, contando os zeros à direita)
- loop em uma divisão por 2 até o resultado ser 1
Estou usando o Python, mas a resposta a essa pergunta deve ser agnóstica da linguagem, suponho.
Solução 2
Resposta curta
No que diz respeito a Python:
- o Método mais rápido de todos Para encontrar o expoente de 2 ** x, olhando para cima em um dicionário cujos hashes são os poderes de 2 (ver "hashlookup"No código)
- o Método mais rápido bit -bit é aquele chamado "Unrolled_bitwise".
- Ambos os métodos anteriores têm limites superiores bem definidos (mas extensíveis). o Método mais rápido sem limites superiores com código duro (que escala o quanto o python pode lidar com números) é "log_e".
Notas preliminares
- Todas as medidas de velocidade abaixo foram obtidas via
timeit.Timer.repeat(testn, cycles)Ondetestnfoi definido como 3 ecyclesfoi ajustado automaticamente pelo script para obter tempos na faixa de segundos (Nota: Houve um bug neste mecanismo de ajuste automático que foi corrigido em 18/02/2010). - Nem todos os métodos podem escalar, é por isso que não testei todas as funções para os vários poderes de 2
- Não consegui obter alguns dos métodos propostos para funcionar (A função retorna um resultado errado). Eu ainda não tinha Tiem para fazer uma sessão de depuração passo a passo: incluí o código (comentado), caso alguém perceba o erro pela inspeção (ou quero executar a depuração)
Resultados
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%
Código
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
Outras dicas
"Agnóstico da linguagem" e preocupação com o desempenho são conceitos praticamente incompatíveis.
A maioria dos processadores modernos tem uma instrução da CLZ, "Conde líder zeros". No GCC, você pode chegar a ele com __builtin_clz (x) (que também produz um código razoável, se não o mais rápido, para alvos que não têm CLZ). Observe que esse CLZ está indefinido para zero, portanto, você precisará de uma ramificação extra para capturar esse caso, se ele importa em seu aplicativo.
Em Celt ( http://celt-codec.org ) O Clz sem ramificação que usamos para complicados sem um CLZ foi escrito por 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;
}
(Os comentários indicam que isso foi considerado mais rápido que uma versão ramificada e uma versão baseada na tabela de pesquisa)
Mas se o desempenho é crítico, você provavelmente não deve implementar essa parte do seu código no Python.
Há uma página com muitos desses tipos de truques e hacks. Está escrito para C, mas muitos deles também devem funcionar em Python (embora o desempenho obviamente seja diferente). A parte que você quer é aqui e em diante.
Você poderia tentar isto por exemplo:
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];
}
}
Parece que poderia ser convertido em Python com bastante facilidade.
Você pode fazê -lo no tempo O (LG S) para inteiros de comprimento arbitrário usando uma pesquisa de bins.
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
Para números inteiros de tamanho fixo, uma tabela de pesquisa deve ser a solução mais rápida e provavelmente o melhor em geral.
Parece que o alcance é conhecido. Vamos supor que ele suba para 1 << 20, apenas para torná -lo mais interessante:
max_log2=20
Portanto, faça uma lista que (com efeito) mapeie um número inteiro do seu logaritmo base 2. O seguinte fará o truque:
log2s_table=[0]*((1<<max_log2)+1)
for i in range(max_log2+1):
log2s_table[1<<i]=i
(Isso não faz nada útil para números que não são poderes de dois; a declaração do problema sugere que eles não precisam ser tratados. Seria fácil o suficiente para corrigir isso.)
A função de obter o logaritmo é muito simples e pode ser facilmente inlinada:
def table(v):
return log2s_table[v]
Não posso garantir que o código de teste que escrevi seja exatamente o mesmo que o usado para obter os horários de exemplo, mas isso é mais rápido que o stringcount código:
stringcount: 0.43 s.
table: 0.16 s.
Como todos os valores da tabela são inferiores a 256, eu me perguntei se usar uma string em vez de uma lista seria mais rápido, ou talvez um array.array de bytes, mas sem dados:
string: 0.25 s.
arr: 0.21 s.
Usando um dict Para fazer a pesquisa é outra possibilidade, aproveitando a maneira como apenas os poderes de dois estão sendo verificados:
log2s_map=dict([(1<<x,x) for x in range(max_log2+1)])
def map(v):
return log2s_map[v]
Os resultados para isso não foram tão bons, no entanto:
map: 0.20 s.
E apenas por diversão também poderia usar o hex Método em objetos flutuantes para obter uma string que inclua (como sua última parte) o expoente base 2 do número. Isso é um pouco lento para extrair em geral, mas se o expoente só será um dígito, poderá ser feito de maneira direta o suficiente:
def floathex(v):
return ord(float(v).hex()[-1])-48
Isso é puramente para o valor do entretenimento, porém, como não era competitivo - porém, surpreendentemente, ainda mais rápido do que a abordagem bittusiva.
Parece que usar uma lista é o caminho a percorrer.
(Essa abordagem não será escalada indefinidamente, devido à memória limitada, mas para compensar isso a velocidade de execução não dependerá de max_log2, ou os valores de entrada, de qualquer maneira que você notará ao executar o código Python. Em relação ao consumo de memória, se bem me lembro dos meus internos do Python, a tabela assumirá sobre (1<<max_log2)*4 Bytes, porque o conteúdo são todos pequenos números inteiros que o intérprete será interno automaticamente. Então quando max_log2 tem 20 anos, isso é cerca de 4 MB.)
Na verdade, este é um comentário para o teste de desempenho publicado pelo Mac. Eu posto isso como uma resposta para ter formatação de código adequada e recuo
Mac, você poderia tentar uma implementação desenrolada do BitsEach sugerido por Mark Byers? Talvez seja apenas o acesso da matriz que a diminui. Em teoria, essa abordagem deve ser mais rápida que os outros.
Pareceria algo assim, embora não tenha certeza se a formatação é adequada para o Python, mas acho que você pode ver o que deveria fazer.
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 );
Se Python compartilha a falta de números inteiros de Java, seria necessário ser algo assim:
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 );
Atrasado para a festa, mas que tal int.bit_length(n) - 1? Você pediu direto, e isso parece o mais simples para mim. A implementação do CPYTHON parece razoavelmente executada.
