Trovare l'esponente n = 2 ** x utilizzando operazioni bit per bit [logaritmo in base 2 di n]
https://stackoverflow.com/questions/2255177
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
C'è un modo semplice per estrarre l'esponente da una potenza di 2 usando solo operazioni bit per bit?
Modifica Anche se la questione era in origine sulle operazioni bit per bit, il filo è una buona lettura anche se vi state chiedendo "Qual è il modo più veloce per trovare X dato Y = 2 X in Python ? "**
Attualmente sto cercando di ottimizzare una routine ( Rabin-Miller test di primalità ) che riduce un numero pari N nelle forme 2**s * d . Posso ottenere il 2**s di articoli per:
two_power_s = N & -N
, ma non riesco a trovare un modo per estrarre solo " s " con un'operazione bit per bit. Soluzioni alternative Attualmente sto test senza troppa soddisfazione (sono tutti più o meno lento) sono:
- utilizzando la funzione logaritmica
- manipolare la rappresentazione binaria di 2 s ** (cioè contando gli zeri finali)
- loop su una divisione per 2 fino a quando il risultato è 1
Sto usando python, ma la risposta a questa domanda dovrebbe essere la lingua agnostico, suppongo.
Soluzione 2
Risposta breve
Per quanto riguarda il pitone è interessato:
- Il metodo più veloce di tutto per trovare l'esponente del 2 ** x è da cercare in un dizionario la cui hash sono le potenze di 2 (vedi " hashlookup " nel codice)
- Il Metodo di bit per bit più veloce è quella denominata " unrolled_bitwise ".
- Entrambi i metodi precedenti sono ben definiti (ma estendibile) limiti superiori. Il metodo più veloce, senza limiti superiori hard-coded (che scala fino, per quanto di pitone in grado di gestire numeri) è " log_e ".
Note preliminari
- Tutte le misurazioni di velocità al di sotto sono stati ottenuti tramite
timeit.Timer.repeat(testn, cycles)dovetestnè stato fissato a 3 ecyclesè stato regolato automaticamente dallo script per ottenere tempi nella gamma di secondi ( Nota: c'era un bug in questo meccanismo di auto-regolazione, che è stato fissato sul 18/02/2010). - Non tutti i metodi in grado di scalare , questo è il motivo per cui non ho la prova di tutte le funzioni per le varie potenze di 2
- non sono riuscito a ottenere alcuni dei metodi proposti per lavorare (la funzione restituisce un risultato sbagliato). Io non avevo ancora tiem di fare una sessione di debug step-by-step: ho inserito il codice (commentato) nel caso in cui qualcuno ha visto l'errore mediante ispezione (o voglia per eseguire debug stessi)
Risultati
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%
funz (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%
funz (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%
Codice
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
Altri suggerimenti
"lingua agnostico" e preoccuparsi di prestazioni sono praticamente concetti incompatibili.
La maggior parte dei processori moderni hanno un'istruzione CLZ, "contare gli zeri iniziali". Nel GCC si può arrivare ad essa con __builtin_clz (x) (che produce anche ragionevole, se non il più veloce, il codice per gli obiettivi che mancano CLZ). Si noti che questo CLZ non è definito per lo zero, quindi avrai bisogno di un ramo in più per catturare quel caso se è importante nella vostra applicazione.
In CELT ( http://celt-codec.org ) il CLZ branchless che usiamo per compliers manca un CLZ è stato scritto da 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;
}
(I commenti indicano che questo è risultato essere più veloce di una versione di ramificazione e una versione tabella di ricerca basato)
Ma se le prestazioni è che critica probabilmente non dovrebbe essere di attuazione della presente parte del codice in Python.
C'è una pagina con un sacco di questi tipi di trucchi e hack. E 'scritto in C, ma molti di loro dovrebbe funzionare in Python troppo (anche se la prestazione sarà ovviamente diverso). Il bit che si desidera è qui in poi.
Si potrebbe provare a questo ad esempio:
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];
}
}
Questo sembra che potrebbe essere convertito in Python abbastanza facilmente.
È possibile farlo in tempo O (lg s) per gli interi di lunghezza arbitraria usando un 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
Per gli interi di dimensioni fisse, una tabella di ricerca dovrebbe essere la soluzione più veloce, e probabilmente migliore in generale.
Sembra che la gamma è noto. Supponiamo che si va fino a 1 << 20, solo per renderlo più interessante:
max_log2=20
Quindi, fare una lista che (in effetti) associa un numero intero per la sua base di 2 logaritmi. Di seguito farà il trucco:
log2s_table=[0]*((1<<max_log2)+1)
for i in range(max_log2+1):
log2s_table[1<<i]=i
(Questo non fa niente di utile per i numeri che non sono potenze di due,.. La dichiarazione del problema suggerisce che non hanno bisogno di essere trattati Sarebbe abbastanza facile da risolvere che però)
La funzione per ottenere il logaritmo è molto semplice, e potrebbe facilmente essere inline:
def table(v):
return log2s_table[v]
Non posso garantire che il codice di prova che ho scritto è esattamente la stessa di quella utilizzata per ottenere l'esempio tempi, ma questo è piuttosto più rapidamente di quanto il codice stringcount:
stringcount: 0.43 s.
table: 0.16 s.
Poiché tutti i valori nella tabella sono meno di 256, ho chiesti se utilizzare una stringa invece di un elenco sarebbe più veloce, o forse un array.array di byte, ma nessun dadi:
string: 0.25 s.
arr: 0.21 s.
Utilizzo di un dict per fare la ricerca è un'altra possibilità, sfruttando il modo in cui solo potenze di due vengono controllati:
log2s_map=dict([(1<<x,x) for x in range(max_log2+1)])
def map(v):
return log2s_map[v]
I risultati di questo non erano così buoni, anche se:
map: 0.20 s.
E solo per divertimento si potrebbe anche utilizzare il metodo hex su oggetti galleggianti per ottenere una stringa che include (come la sua ultima parte) l'esponente base 2 del numero. Questo è un po 'lento per estrarre in generale, ma se l'esponente è sempre e solo sarà una cifra che potrebbe essere fatto semplicemente abbastanza:
def floathex(v):
return ord(float(v).hex()[-1])-48
Questo è puramente per valore di intrattenimento anche se, come è stato uncompetetive - anche se, sorprendentemente, ancora più veloce rispetto all'approccio bit a bit
.Quindi sembra che utilizzando una lista è la strada da percorrere.
(Questo approccio non scala a tempo indeterminato, a causa della memoria limitata, ma per compensare che la velocità di esecuzione non dipenderà max_log2, oppure i valori di input, in alcun modo che si noterà quando si esegue il codice python . per quanto riguarda il consumo di memoria, se non ricordo male i miei interni pitone, la tabella occupa circa byte (1<<max_log2)*4, perché i contenuti sono tutti piccoli numeri interi che l'interprete sarà stagista automaticamente. Così, quando max_log2 è di 20, che è di circa 4 MB.)
Questo è in realtà un commento alla prova le prestazioni postato da mac. Ho questo post come una risposta per avere una corretta formattazione del codice e il rientro
mac, si potrebbe provare un'implementazione srotolato della bitseach suggerita da Mark Byers? Forse è solo l'accesso matrice che lo rallenta. In teoria, questo approccio dovrebbe essere più veloce rispetto agli altri.
Sarebbe simile a questa, anche se non sono sicuro se la formattazione è giusto per Python, ma credo che si può vedere ciò che dovrebbe fare.
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 la mancanza di azioni di pitone di java di interi unsingned sarebbe bisogno di essere qualcosa di simile:
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 );
in ritardo alla festa, ma come circa int.bit_length(n) - 1? Avete chiesto semplice, e che sembra il più semplice per me. L'implementazione CPython sembra ragionevolmente performante.
