Den Exponenten von n = 2 ** x mit bitweisen Operationen finden [logarithm in base 2 von n]

Gibt es einen einfachen Weg, um den Exponenten aus einer Macht von 2 mit nur bitweisen Operationen zu extrahieren?

EDIT: Obwohl die Frage ursprünglich über bitweise Operationen war, ist der Thread auch gut lesbar, wenn du dich fragtest "Was ist der schnellste Weg, um X gegeben zu geben, Y = 2 X in Python ?" **

  • Bit-weise Operation unary ~ (invertieren)
  • Lesen von niedrigstwertigen Bits in Python
  • Bitweise Operationen in Python
  • Konvertieren von Bits in Bytes in Python
  • Ist es möglich, bitweise Operationen auf einem String in Python zu machen?
  • Wie vertrete und arbeite ich mit n-Bit-Vektoren in Python?
  • Ich versuche derzeit, eine Routine zu optimieren ( Rabin-Miller-Primitiv-Test ), die eine gerade Zahl N in den Formen 2**s * d reduziert. Ich kann die 2**s Teil von:

     two_power_s = N & -N 

    Aber ich kann keinen Weg finden, nur " s " mit einer bitweisen Operation zu extrahieren. Workarounds Ich teste derzeit ohne zu viel Zufriedenheit (sie sind alle ziemlich langsam) sind:

    • Mit der Logarithmusfunktion
    • Manipulieren der binären Darstellung von 2 ** s (dh das Zählen der nachlaufenden Nullen)
    • Schleife auf eine Division von 2 bis das Ergebnis 1 ist

    Ich benutze Python, aber die Antwort auf diese Frage sollte Sprache agnostisch sein, nehme ich an.

    Vielen Dank im Voraus für Ihre Zeit.

  • Rufen Sie die Methode von der Spitzenklasse in der Hierarchie an, anstatt zu überschreiben
  • Python: Ändern Sie Klassenart mit Dekorateur und halten Sie die Methoden
  • Python3 - Verhalten von super () auf Multi-Vererbung
  • Mehrere Konstruktoren in Python, mit Vererbung
  • Python vererbbare Funktionen
  • Alle Basisklassen in einer Hierarchie der angegebenen Klasse auflisten?
  • 6 Solutions collect form web for “Den Exponenten von n = 2 ** x mit bitweisen Operationen finden [logarithm in base 2 von n]”

    "Sprache agnostisch" und beunruhigend über die leistung sind so ziemlich inkompatible konzepte.

    Die meisten modernen Prozessoren haben eine CLZ-Anweisung, "zählen führende Nullen". In GCC kannst du es mit __builtin_clz (x) (das auch produziert vernünftige, wenn nicht die schnellste, Code für Ziele, die clz fehlen). Beachten Sie, dass diese CLZ für null unbestimmt ist, also benötigen Sie einen zusätzlichen Zweig, um diesen Fall zu fangen, wenn es in Ihrer Anwendung wichtig ist.

    In CELT ( http://celt-codec.org ) ist die verzweigte CLZ, die wir für Compliers ohne CLZ verwenden, 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 gefunden wurde, um schneller als eine Verzweigung Version und eine Lookup-Tabelle basierte Version)

    Aber wenn Leistung ist das kritisch Sie wahrscheinlich nicht implementieren diesen Teil Ihres Codes in Python.

    Kurze Antwort

    Was Python betrifft:

    • Die schnellste Methode von allen , um den Exponenten von 2 ** x zu finden, ist durch das Aufschauen in einem Wörterbuch, dessen Hashes die Kräfte von 2 sind (siehe " hashlookup " im Code)
    • Die schnellste bitweise Methode ist die " unrolled_bitwise ".
    • Beide bisherigen Methoden haben klar definierte (aber erweiterbare) Obergrenzen. Die schnellste Methode ohne hartcodierte Obergrenzen (die bis zu Python skaliert ist, kann mit Zahlen umgehen) ist " log_e ".

    Vorbemerkungen

    1. Alle Geschwindigkeitsmessungen unten wurden über timeit.Timer.repeat(testn, cycles) wo testn auf 3 gesetzt wurde und cycles wurde automatisch durch das Skript angepasst, um Zeiten im Sekundenbereich zu erhalten ( Anmerkung: da war ein Fehler in diesem Auto Einstellmechanismus, der am 18/02/2010 festgelegt wurde).
    2. Nicht alle Methoden können skalieren , deshalb habe ich nicht alle Funktionen für die verschiedenen Potenzen von 2 getestet
    3. Ich habe es nicht geschafft, einige der vorgeschlagenen Methoden zu erwerben (die Funktion gibt ein falsches Ergebnis zurück). Ich hatte noch keine Bindung, um eine Schritt-für-Schritt-Debugging-Session zu machen: Ich habe den Code (kommentiert) nur für den Fall, dass jemand den Fehler durch Inspektion (oder will das 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 

    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 wird). Das Bit, das du willst, ist hier und weiter.

    Sie könnten dies zum Beispiel versuchen:

     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 so aus, dass es ganz einfach in Python umgewandelt werden könnte.

    Sie können es in O (lg s) Zeit für beliebige Länge ganze Zahlen mit einem binsearch tun.

     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 Integers, sollte eine Nachschlagetabelle die schnellste Lösung sein, und wahrscheinlich am besten insgesamt.

    Es scheint, wie die Reichweite bekannt ist. Nehmen wir an, es geht bis zu 1 << 20, nur um es interessanter zu machen:

     max_log2=20 

    So machen Sie eine Liste, die (in der Tat) eine Ganzzahl auf ihre Basis 2 Logarithmus. Das folgende wird den Trick machen:

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

    (Das tut nichts Nützliches für Zahlen, die keine Potenzen von zwei sind, die Problemerklärung deutet darauf hin, dass sie nicht behandelt werden müssen. Wäre einfach genug, um das zu beheben.)

    Die Funktion, den Logarithmus zu bekommen, ist sehr einfach und könnte leicht inlineiert werden:

     def table(v): return log2s_table[v] 

    Ich kann nicht garantieren, dass der stringcount , den ich schrieb, genau der gleiche ist wie derjenige, der verwendet wird, um die Beispiel-Timings zu erhalten, aber das ist eher schneller als der stringcount Code:

     stringcount: 0.43 s. table: 0.16 s. 

    Da alle Werte in der Tabelle kleiner als 256 sind, fragte ich mich, ob die Verwendung eines Strings statt einer Liste schneller wäre, oder vielleicht ein array.array von Bytes, aber kein Würfel:

     string: 0.25 s. arr: 0.21 s. 

    Mit einem dict , um die Suche zu tun ist eine andere Möglichkeit, unter Ausnutzung der Art und Weise nur Befugnisse von zwei werden überprüft:

     log2s_map=dict([(1<<x,x) for x in range(max_log2+1)]) def map(v): return log2s_map[v] 

    Die Ergebnisse dafür waren aber nicht so gut:

     map: 0.20 s. 

    Und nur zum Spaß könnte man auch die hex Methode auf Float-Objekten verwenden, um einen String zu erhalten, der (als letzter Teil) den Basis-2-Exponenten der Nummer enthält. Dies ist ein bisschen langsam, um im Allgemeinen zu extrahieren, aber wenn der Exponent wird nur jemals eine Ziffer sein, könnte es einfach genug gemacht werden:

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

    Dies ist nur für Unterhaltungswert, denn es war uncompetetive – aber erstaunlich, noch schneller als der bitweise Ansatz.

    So sieht es aus wie eine Liste ist der Weg zu gehen.

    (Dieser Ansatz wird nicht auf unbestimmte Zeit skaliert, aufgrund des begrenzten Gedächtnisses, aber um max_log2 , dass die Ausführungsgeschwindigkeit nicht von max_log2 oder den Eingabewerten abhängt, in irgendeiner Weise, die Sie bei der Ausführung von Python-Code bemerken werden Gedächtnisverbrauch, wenn ich mich an meine Python Internets richtig erinnere, wird der Tisch über (1<<max_log2)*4 Bytes aufnehmen, denn der Inhalt ist alles kleine ganze Zahlen, die der Interpreter automatisch max_log2 . SO, wenn max_log2 20 ist, geht's 4MB.)

    Dies ist eigentlich ein Kommentar zum Performance-Test von Mac gepostet. Ich poste dies als Antwort auf ordnungsgemäße Code-Formatierung und Einzug

    Mac, könnten Sie versuchen, eine abgerollte Umsetzung der Bitseach vorgeschlagen von Mark Byers? Vielleicht ist es nur der Array-Zugang, der es verlangsamt. In der Theorie sollte dieser Ansatz schneller sein als die anderen.

    Es würde so etwas aussehen, obwohl ich mir nicht sicher bin ob die Formatierung für Python richtig ist, aber ich vermute, dass Sie sehen können, 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 java fehlt unsingned integers teilt, müsste es 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 ); 
    Python ist die beste Programmiersprache der Welt.