Das Finden der Exponent von n = 2 ** x bitweise Operationen mit [Logarithmus zur Basis 2 von n]
https://stackoverflow.com/questions/2255177
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Gibt es eine einfache Möglichkeit, die Exponenten von einer Potenz von 2 mit bitweise Operationen nur zu extrahieren?
EDIT: Auch wenn die Frage war ursprünglich etwa bitweise Operationen, der Thread ist ein gut lesen Sie auch, wenn Sie sich fragen, "Was ist der schnellste Weg, X gegeben Y = 2 X in Python ? "**
Ich versuche zur Zeit eine Routine ( Rabin-Miller Primzahltest ) zu optimieren das reduziert eine gerade Zahl N in den Formen 2**s * d . Ich kann die erhalten 2**s Teil von:
two_power_s = N & -N
, aber ich kann nicht einen Weg zu extrahieren nur „ s “ mit einer bitweise Operation finden. Abhilfen I-Tests sind derzeit ohne zu viel Zufriedenheit (sie sind alle ziemlich langsam) sind:
- mit der Logarithmusfunktion
- die Binärdarstellung von 2 ** s Manipulation (d.h. die abfallenden Nullen gezählt)
- Looping auf einer Division durch 2, bis das Ergebnis ist 1
Ich bin mit Python, aber die Antwort auf diese Frage sollte sprachunabhängig sein, nehme ich an.
Lösung 2
Kurze Antwort
Was Python angeht:
- Die schnellste Methode aller die Exponenten finden von 2 ** x ist durch die in einem Wörterbuch, dessen Hashes aufzublicken sind die Potenzen von 2 (siehe " hashlookup " im Code)
- Die schnellste bitweise Methode ist die sogenannte " unrolled_bitwise ".
- Die beiden bisherigen Methoden haben gut definierten (aber erweiterbar) Obergrenzen. Die schnellste Methode ohne hartcodierte Obergrenzen (die so weit skaliert wie Python Zahlen umgehen kann) ist " log_e ".
Vorbemerkungen
- Alle Geschwindigkeitsmessungen unterhalb wurden über erhalten
timeit.Timer.repeat(testn, cycles), wotestnbis 3 undcycleseingestellt wurde automatisch durch das Skript angepasst zu erhalten Zeiten im Bereich von Sekunden ( Hinweis: gibt es in diesem auto-Verstellmechanismus ein Fehler, der am 18.02.2010 festgelegt wurde). - Nicht alle Methoden skalieren , das ist, warum ich nicht alle Funktionen für die verschiedenen Potenzen von 2 testen haben
- Ich habe es geschafft, nicht einige der vorgeschlagenen Methoden an die Arbeit (die Funktion gibt ein falsches Ergebnis). Ich habe noch tiem keinen Schritt-für-Schritt-Debugging-Sitzung zu tun haben: Ich habe den Code enthalten (kommentiert) für den Fall, jemand sieht den Fehler durch Inspektion (oder wollen die Debug selbst ausführen)
Ergebnisse
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
Andere Tipps
„sprachunabhängig“ und sich Gedanken über die Leistung sind ziemlich unvereinbar Konzepte.
Die meisten modernen Prozessoren haben eine CLZ Anweisung „zählen führende Nullen“. In GCC können Sie es bekommen mit __builtin_clz (x) (das auch sinnvoll, wenn nicht der schnellste, Code für Ziele, die clz fehlt produziert). Beachten Sie, dass diese CLZ ist nicht definiert für Null, so dass Sie einen zusätzlichen Zweig benötigen, diesen Fall zu fangen, wenn es in Ihrer Anwendung von Bedeutung ist.
In CELT ( http://celt-codec.org ) die branchless CLZ wir für compliers verwenden ein fehlt CLZ wurde von Timothy B. Terriberry geschrieben:
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;
}
(Die Kommentare zeigen, dass dies schneller zu sein als eine Verzweigung-Version und eine Lookup-Tabelle basierten Version gefunden wurde)
Wenn aber die Leistung ist, dass kritische sollten Sie wahrscheinlich nicht, diesen Teil des Codes in Python umsetzen.
Es gibt eine Seite mit vielen dieser Arten von Tricks und Hacks. Es ist für C geschrieben, aber viele von ihnen sollten auch in Python arbeiten (obwohl die Leistung offensichtlich anders sein). Das Bit Sie wollen, ist hier und weiter.
Sie könnten versuchen, diese zum Beispiel:
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];
}
}
Das sieht aus wie es in Python umgewandelt werden könnte ganz leicht.
Sie können es in O tun (lg n) Zeit für beliebige Länge ganzer Zahlen mit einem binsearch verwenden.
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
Für feste Größe ganzer Zahlen, eine Lookup-Tabelle die schnellste Lösung sein sollte, und wahrscheinlich beste Gesamt.
Es scheint, wie der Bereich bekannt ist. Nehmen wir an, es bis zu 1 geht << 20, nur um es noch interessanter:
max_log2=20
So eine Liste machen, dass (in der Tat) ordnet eine ganze Zahl seiner Logarithmus zur Basis 2. Im Folgenden wird der Trick:
log2s_table=[0]*((1<<max_log2)+1)
for i in range(max_log2+1):
log2s_table[1<<i]=i
(Dies tut nichts nützlich für die Zahlen, die nicht Potenzen von zwei sind,.. Die Problemstellung legt nahe, dass sie nicht behandelt werden muß, leicht genug, um fix sein würde, dass, obwohl)
Die Funktion des Logarithmus zu bekommen, ist sehr einfach und leicht inlined werden:
def table(v):
return log2s_table[v]
Ich kann nicht garantieren, dass der Test Code, den ich geschrieben habe, ist genau das gleiche wie die verwendet werden, um die Beispiel-Timings zu bekommen, aber das ist eher schneller als der stringcount Code:
stringcount: 0.43 s.
table: 0.16 s.
Da alle Werte in der Tabelle sind weniger als 256, fragte ich mich, ob eine Zeichenfolge anstelle einer Liste schneller sein würde, oder vielleicht ein array.array von Bytes, aber keine Würfel:
string: 0.25 s.
arr: 0.21 s.
ein dict Verwenden der Lookup zu tun, ist eine andere Möglichkeit, die Vorteile der Art und Weise nehmen nur Zweierpotenzen geprüft werden:
log2s_map=dict([(1<<x,x) for x in range(max_log2+1)])
def map(v):
return log2s_map[v]
Die Ergebnisse für diese waren nicht so gut, aber:
map: 0.20 s.
Und nur so zum Spaß man auch die hex Methode auf Float-Objekte verwenden könnte einen String zu erhalten, die (als letzter Teil) umfasst die Basis 2 Exponent der Zahl. Das ist ein bisschen langsam Extrakt im Allgemeinen, aber wenn der Exponent ist immer nur eine Stelle sein würde es ohne weiteres genug getan werden könnte:
def floathex(v):
return ord(float(v).hex()[-1])-48
Dies ist rein zur Unterhaltung obwohl, wie es war uncompetetive -. Aber erstaunlich, immer noch schneller als der bitweise Ansatz
So ist es wie mit einer Liste aussieht, ist der Weg zu gehen.
(Dieser Ansatz wird nicht unbegrenzt skalieren, aufgrund des begrenzten Speichers, aber für bilden, dass die Ausführungsgeschwindigkeit auf max_log2 nicht ab, oder die Eingabewerten, in irgendeiner Weise, dass Sie werden feststellen, wenn Python-Code ausgeführt werden . der Speicherverbrauch angeht, wenn ich, dass der Dolmetscher wird intern automatisch korrekt, nimmt der Tisch über (1<<max_log2)*4 Bytes, da die Inhalte alle kleinen ganzen Zahlen sind meine python-Interna erinnern. SO, wenn max_log2 20, das ist etwa 4 MB).
Dies ist eigentlich ein Kommentar an den Performance-Test von Mac geschrieben. Ich poste dies als eine Antwort richtigen Code zu haben, Formatierung und Einrücken
mac, könnten Sie eine abgerollt Umsetzung des bitseach versuchen von Mark Byers vorgeschlagen? Vielleicht ist es nur der Array-Zugriff, die es verlangsamt. Theoretisch sollte dieser Ansatz schneller als die anderen.
Es wäre in etwa so aussehen, obwohl ich nicht sicher bin, ob die Formatierung richtig für Python, aber ich denke, kann man sehen, was es tun soll.
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 );
Wenn Python Aktien Javas von unsingned ganzen Zahlen fehlen würde es brauchen, so etwas sein:
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 );
spät zur Party, aber wie wäre es int.bit_length(n) - 1? Sie baten um unkompliziert, und das scheint die einfachste für mich. Die CPython Implementierung sieht recht performant.
