Recherche de l'exposant de n = 2 ** x en utilisant des opérations au niveau du bit [logarithme en base 2 du n]
https://stackoverflow.com/questions/2255177
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Yat-il un moyen simple d'extraire l'exposant d'une puissance de 2 en utilisant des opérations au niveau du bit seulement?
EDIT: Bien que la question était à l'origine sur les opérations de manipulation de bits, le fil est une bonne lecture même si vous vous demandez «Ce qui est le meilleur moyen de trouver X donnée Y = 2 X en Python ? "**
Je suis en train d'essayer d'optimiser une routine ( Rabin-Miller primalité 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'extraire juste « s » avec une opération de bits. 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 ** (par exemple le comptage des zéros)
- boucle sur une division par deux jusqu'à ce que le résultat est 1
J'utilise python, mais la réponse à cette question devrait être la langue agnostique, je suppose.
La solution 2
Réponse courte
En ce qui concerne python:
- 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)
- méthode la plus rapide de bit est celui appelé " unrolled_bitwise ".
- Les deux méthodes précédentes ont bien défini (mais extensible) limites supérieures. méthode la plus rapide sans limites supérieures codées en dur (qui adapte aussi loin que python peut gérer des nombres) est " log_e ".
Notes préliminaires
- Toutes les mesures de vitesse ci-dessous ont été obtenus via
timeit.Timer.repeat(testn, cycles)oùtestna été fixé à 3 etcyclesa été ajusté automatiquement par le script pour obtenir des temps dans l'intervalle de quelques secondes ( Note: il y avait un bug dans ce mécanisme d'ajustement automatique qui a été fixé sur 18/02/2010). - Toutes les méthodes peuvent échelle , voilà pourquoi je n'ai pas testé toutes les fonctions pour les différentes puissances de 2
- Je ne l'ai pas réussi à obtenir quelques-unes des méthodes proposées pour travailler (la fonction retourne un résultat erroné). Je n'ai pas encore tiem faire un débogage étape par étape session: J'inclus le code (commenté) juste 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
Autres conseils
« 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éfini pour zéro, vous aurez donc besoin d'une branche supplémentaire pour attraper ce cas, si cela importe dans votre application.
Dans CELT ( http://celt-codec.org ) le CLZ de nous utilisons pour sans branches observants manque un 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 critique vous ne devriez probablement pas implémentez cette partie de votre code en python.
Il y a une page avec beaucoup de ces types de trucs et hacks. Il est écrit C, mais beaucoup d'entre eux devrait travailler en Python aussi (bien que la performance sera évidemment différente). Le bit que vous voulez est et les années suivantes.
Vous pouvez essayer cette 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.
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 consultation devrait être la solution la plus rapide, et probablement meilleur dans l'ensemble.
Il semble que la plage est connue. Supposons que cela va jusqu'à 1 << 20, juste pour le rendre plus intéressant:
max_log2=20
Alors faites 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 rien 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 nécessairement être manutentionnés assez facile à corriger que 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 utilisé pour obtenir les exemples horaires, mais cela est plutôt plus rapide que le code stringcount:
stringcount: 0.43 s.
table: 0.16 s.
Étant donné que toutes les valeurs du tableau sont inférieurs à 256, je me suis demandé 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 pour ce ne sont pas aussi bien, cependant:
map: 0.20 s.
Et juste pour le plaisir on pourrait aussi 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 du 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 - mais, étonnamment, encore plus rapide que l'approche binaire
.Il ressemble à l'aide d'une liste est le chemin à parcourir.
(Cette approche ne sera pas indéfiniment échelle, 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 les valeurs d'entrée, de quelque façon que vous remarquerez lors de l'exécution du code python . en ce qui concerne la consommation de mémoire, si je me souviens bien mes internals python, la table prendra environ octets (1<<max_log2)*4, 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.)
Ceci est en fait un commentaire au test de performance affiché par mac. Je poster cela comme une réponse à avoir le formatage du code approprié et indenter
mac, pourriez-vous essayer une mise en œuvre de la bitseach déroulée suggérée par Mark Byers? Peut-être juste l'accès au tableau qu'il 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 );
à la fin du parti, mais que diriez-vous int.bit_length(n) - 1? Vous avez demandé simple, et que me semble le plus simple. La mise en œuvre CPython semble raisonnablement performante.
