Trovare l'esponente di n = 2 ** x utilizzando operazioni bit a bit [logaritmo in base 2 di n]

Question

Esiste un modo semplice per estrarre l'esponente da una potenza di 2 utilizzando solo operazioni bit a bit?

EDIT: 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 primality test) che riduce di un numero pari N nelle forme 2**s * d. Posso ottenere la parte 2**s da:

two_power_s = N & -N 

ma non riesco a trovare un modo per estrarre solo "s" con un'operazione bit per bit. Soluzioni alternative sto testando 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.

Answer 1

Risposta breve

Per quanto riguarda il pitone è interessato:

• Il metodo più veloce di tutti per trovare l'esponente del 2 ** x è da cercare in un dizionario la cui hash sono la potenze di 2 (vedere "hashlookup" nel codice)
• il più veloce metodo di bit è quello denominato "unrolled_bitwise ".
• Entrambi i metodi precedenti hanno limiti superiori ben definiti (ma estensibili). Il metodo più veloce senza limiti hard codificati (che scala fino a che python può gestire i numeri) è "log_e".

Note preliminari

1. Tutte le misurazioni di velocità al di sotto sono stati ottenuti tramite timeit.Timer.repeat(testn, cycles) dove testn è stato fissato a 3 e cycles è stato regolato automaticamente dallo script per ottenere le ore comprese di secondi (nota : c'era un bug in questo meccanismo di autoregolazione che è stato corretto il 18/02/2010).
2. 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
3. non sono riuscito a ottenere alcuni dei metodi proposti per lavorare (la funzione restituisce un torto risultato).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% 

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% 

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% 

funz (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 

Answer 2

C'è una pagina con un sacco di questi tipi di trucchi e hack. È scritto per C, ma molti di loro dovrebbero funzionare anche in Python (anche se ovviamente le prestazioni saranno diverse). Il bit desiderato è here e successivi.

Si potrebbe provare this 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.

Answer 3

È possibile farlo in O (lg s) tempo per numeri interi di lunghezza arbitraria utilizzando 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 numeri interi a dimensione fissa, una tabella di ricerca deve essere la soluzione più rapida e probabilmente la migliore in assoluto.

Answer 4

"linguaggio agnostico" e preoccuparsi delle prestazioni sono concetti sostanzialmente incompatibili.

I processori più moderni hanno un'istruzione CLZ, "contare gli zeri iniziali". In GCC è possibile ottenerlo con __builtin_clz (x) (che produce anche un codice ragionevole, se non il più veloce, per gli obiettivi privi di clz). Nota che questo CLZ non è definito per zero, quindi avrai bisogno di un ramo aggiuntivo per catturare quel caso se è importante nella tua applicazione.

In CELT (http://celt-codec.org) il CLZ senza ramo che utilizziamo per i compilatori privi di 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 sono critiche che probabilmente non dovrebbe essere applicazione della presente parte del tuo codice in python.

Answer 5

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. risolvere questo 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 essere utilizzato per ottenere i tempi di esempio, ma questo è piuttosto più veloce dello.471.010.285,66321 milione codice:

stringcount: 0.43 s. 
table: 0.16 s. 

Poiché tutti i valori nella tabella sono meno di 256, mi chiese 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. 

Utilizzando 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 buoni, però:

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) la base 2 esponente il numero.Questo è un po 'lento per estrarre in generale, ma se l'esponente è sempre e solo sarà una cifra che potrebbe essere fatto abbastanza semplicemente:

def floathex(v): 
    return ord(float(v).hex()[-1])-48 

Questo è puramente per valore di intrattenimento anche se, come è stato uncompetetive - anche se , incredibilmente, ancora più veloce dell'approccio bit a bit.

Quindi sembra che usare una lista sia la strada da percorrere.

(Questo approccio non si ridimensionerà indefinitamente a causa della memoria limitata, ma per compensare che la velocità di esecuzione non dipenderà da max_log2 o dai valori di input, in alcun modo che si noterà quando si esegue python Per quanto riguarda il consumo di memoria, se ricordo correttamente i miei interni Python, la tabella occuperà circa (1<<max_log2)*4 byte, perché i contenuti sono tutti interi piccoli che l'interprete eseguirà internamente, quindi, quando max_log2 è 20, è circa 4 MB.)

Answer 6

Questo è in realtà un commento al test delle prestazioni pubblicato da mac. Inserisco questo messaggio come risposta per avere una corretta formattazione del codice e il rientro

mac, potresti provare un'implementazione srotolata del bitseach suggerito da Mark Byers? Forse è solo l'accesso alla matrice che lo rallenta. In teoria questo approccio dovrebbe essere più veloce degli altri.

Sarebbe simile a questo, anche se non sono sicuro che la formattazione sia corretta per Python ma immagino che tu possa vedere cosa 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 avrebbe 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);