Trouver l'exposant n = 2 ** x en utilisant des opérations au niveau du bit [logarithme en base 2 de n]

Question

est-il un moyen simple d'extraire l'exposant d'une puissance de 2 en utilisant uniquement des opérations au niveau du bit?

EDIT: Bien que la question était à l'origine sur les opérations au niveau du bit, le fil est une bonne lecture même si vous vous demandez « ? Quel est le meilleur moyen de trouver X donnée Y = 2 X en Python » * *

Je suis actuellement en train d'optimiser une routine (Rabin-Miller primality test) qui réduit un nombre pair N dans les formes 2**s * d. Je peux obtenir le 2**s partie par:

two_power_s = N & -N 

mais je ne peux pas trouver un moyen d'une opération pour extraire bitwise juste « s ». Contournements Je teste actuellement sans trop de satisfaction (ils sont tous à peu près lent) sont:

• en utilisant la fonction logarithme
• manipulation de la représentation binaire de 2 ** s (c.-à compter les zéros)
• en boucle sur une division par 2 jusqu'à ce que le résultat est 1

J'utilise python, mais la réponse à cette question devrait être la langue agnostique, je suppose.

Answer 1

Réponse courte

En ce qui concerne python:

• La méthode la plus rapide de tous pour trouver l'exposant de 2 x ** est en regardant dans un dictionnaire dont hash sont les puissances de 2 (voir "hashlookup" dans le code)
• la méthode la plus rapide de est au niveau du bit celui qui est appelé "unrolled_bitwise ".
• Les deux méthodes précédentes ont des limites supérieures bien définies (mais extensibles). La méthode la plus rapide sans les limites supérieures codées en dur (qui évolue aussi loin que python peut gérer les nombres) est "log_e".

Notes préliminaires

1. Toutes les mesures de vitesse ci-dessous ont été obtenus par timeit.Timer.repeat(testn, cycles) où testn a été fixé à 3 et cycles a été ajusté automatiquement par le script pour obtenir des temps de l'ordre de quelques secondes (note : il y avait un bug dans ce mécanisme de réglage automatique qui a été corrigé le 18/02/2010).
2. Toutes les méthodes peuvent échelle, c'est pourquoi je n'ai pas testé toutes les fonctions pour les différentes puissances de 2
3. Je n'ai pas réussi à obtenir quelques-unes des méthodes proposées pour travailler (la fonction retourne une mauvaise résultat).Je n'ai pas encore tiem faire un débogage étape par étape session: J'ai inclus le code (commenté) juste au cas où quelqu'un SPOTS l'erreur par l'inspection (ou si vous voulez effectuer le débogage eux-mêmes)

Résultats

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 

Answer 2

Il y a une page avec beaucoup de ces types de trucs et hacks. C'est écrit pour C, mais beaucoup d'entre eux devraient aussi fonctionner en Python (bien que la performance soit évidemment différente). Le bit que vous voulez est here et au-delà.

Vous pouvez essayer this par exemple:

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

Cela ressemble à cela pourrait être converti en Python assez facilement.

Answer 3

Vous pouvez le faire en O (s lg) temps pour les entiers de longueur arbitraire en utilisant 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 

Pour les entiers de taille fixe, une table de recherche devrait être la solution la plus rapide et probablement la meilleure dans l'ensemble.

Answer 4

« langue agnostique » et se soucier de la performance sont à peu près les concepts incompatibles.

La plupart des processeurs modernes ont une instruction de CLZ, « compter des zéros à gauche ». Dans GCC vous pouvez obtenir avec __builtin_clz (x) (qui produit également raisonnable, sinon le plus rapide, le code pour les cibles qui manquent clz). Notez que cette CLZ n'est pas définie pour zéro, donc vous aurez besoin d'une branche supplémentaire pour attraper ce cas si cela compte dans votre application.

En CELT (http://celt-codec.org) le CLZ sans branchement que nous utilisons pour les compliants dépourvus de CLZ a été écrit par 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; 
} 

(Les commentaires indiquent que cela a été jugé plus rapide qu'une version de branchement et une version table de consultation)

Mais si la performance est que vous devriez probablement pas critique implantera cette partie de votre code en python.

Answer 5

Il semble que la plage est connue . Supposons que cela va jusqu'à 1 < < 20, juste pour le rendre plus intéressant:

max_log2=20 

donc faire une liste (en vigueur) mappe un nombre entier à son logarithme en base 2. Ce qui suit fera l'affaire:

log2s_table=[0]*((1<<max_log2)+1) 
for i in range(max_log2+1): 
    log2s_table[1<<i]=i 

(Cela ne fait pas quelque chose d'utile pour les numéros qui ne sont pas des puissances de deux, l'énoncé du problème suggère qu'ils ne doivent pas être manipulés serait assez facile. résoudre ce problème si)

la fonction pour obtenir le logarithme est très simple, et pourrait facilement être inline.

def table(v): 
    return log2s_table[v] 

Je ne peux pas garantir que le code de test je l'ai écrit est exactement le même que celui étant utilisé pour obtenir les timings d'exemple, mais c'est plutôt plus rapide que leCode:

stringcount: 0.43 s. 
table: 0.16 s. 

Puisque toutes les valeurs du tableau sont inférieurs à 256, je me demandais si l'aide d'une chaîne au lieu d'une liste serait plus rapide, ou peut-être un array.array d'octets, mais pas de dés:

string: 0.25 s. 
arr: 0.21 s. 

l'utilisation d'un dict pour faire la recherche est une autre possibilité, en profitant de la manière que des puissances de deux sont en cours de vérification:

log2s_map=dict([(1<<x,x) for x in range(max_log2+1)]) 

def map(v): 
    return log2s_map[v] 

Les résultats de ce ne sont pas aussi bien, si:

map: 0.20 s. 

Et juste pour le plaisir on pourrait également utiliser la méthode hex sur des objets flottants pour obtenir une chaîne qui comprend (comme sa dernière partie) la base 2 exposant le nombre.Ceci est un peu lent à extraire en général, mais si l'exposant n'est jamais va être un chiffre, il pourrait se faire assez sans détour:

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

Ceci est purement pour la valeur de divertissement mais comme il était uncompetetive - si , étonnamment, toujours plus rapide que l'approche bitwise.

il ressemble à l'aide d'une liste est le chemin à parcourir. (Cette approche ne sera pas mise à l'échelle indéfiniment, en raison de la mémoire limitée, mais pour compenser que la vitesse d'exécution ne dépendra pas de max_log2, ou des valeurs d'entrée, de quelque façon que vous remarquerez lors de l'exécution de python code. en ce qui concerne la consommation de mémoire, si je me souviens bien mes internals python, la table prendra environ (1<<max_log2)*4 octets, car le contenu sont tous petits entiers que l'interprète stagiaire automatiquement. Donc, quand max_log2 est 20, qui est à peu près 4Mo.)

Answer 6

Ceci est en fait un commentaire au test de performance affiché par mac. Je publie ceci comme une réponse pour mettre en forme et mettre en retrait le code correct

mac, pourriez-vous essayer une implémentation déroulée du nombre de bits proposée par Mark Byers? Peut-être que c'est juste l'accès au tableau qui le ralentit. En théorie, cette approche devrait être plus rapide que les autres.

Il ressemblerait à quelque chose comme ça, même si je ne suis pas sûr que la mise en forme est bon pour python mais je suppose que vous pouvez voir ce qu'il est censé faire.

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

Si le manque d'actions python java d'entiers unsingned il devrait être quelque chose comme ceci:

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