Rückgabeindex von niedrigstwertigem Bit in Python

C ++ hat eine Reihe von Funktionen, ffs (), ffsl () und ffsll (), die das niedrigstwertige Bit zurückgeben, das in einer gegebenen binären Ganzzahl gesetzt ist.

Ich frage mich, ob es in Python bereits eine gleichwertige Funktion gibt. Ich sehe keinen, der für Bitarray beschrieben ist, aber vielleicht gibt es noch einen anderen. Ich hoffe zu vermeiden, die Antwort zu berechnen, indem ich alle möglichen Bitmasken durchschleife, aber natürlich ist das eine Option des letzten Resorts. Ffs () gibt einfach eine einzelne ganze Zahl zurück und ich würde gerne etwas vergleichbares in Python wissen.

    8 Solutions collect form web for “Rückgabeindex von niedrigstwertigem Bit in Python”

    Es ist in der gmpy Wrapper für die GNU Multi-Precision Bibliothek erhältlich. Auf meinem System ist es etwa 4x schneller als die Ctypes-Lösung.

     >>> import gmpy >>> gmpy.scan1(136) 3 >>> bin(136) '0b10001000' 

    Nur in Pythons 2.7 und 3.1 und höher:

     def ffs(x): """Returns the index, counting from 0, of the least significant set bit in `x`. """ return (x&-x).bit_length()-1 

    Beispiel:

     >>> ffs(136) 3 

    Es ist möglich, Funktionen aus freigegebenen Bibliotheken (DLLs für Windows Benutzer) mit dem Modul ctypes zu laden . Ich konnte die Funktion ffs() aus der C-Standardbibliothek laden, die in libc.so.6 auf Ubuntu 10.10 enthalten ist:

     >>> import ctypes >>> libc = ctypes.cdll.LoadLibrary('libc.so.6') >>> libc.ffs(136) 4 

    (Beachten Sie, dass dies eine 1-basierte Indizierung verwendet). Offensichtlich ist das nicht plattformübergreifend kompatibel; Sie müssen den Dateinamen der Bibliothek ändern, um zu laden, je nachdem, welches System Sie unter (von sys.platform oder ähnlich) erkannt haben. Ich würde nicht einmal 100% sicher sein, dass es bei verschiedenen Linux-Distributionen gleich wäre.

    Es wäre auch wert, ein richtiges Benchmarking zu machen, um zu sehen, ob es sich wirklich lohnt. Wenn es häufig genannt wird, könnte es sein, aber wenn es nur gelegentlich verwendet wird, wäre der Leistungsvorteil über eine Python-Implementierung wahrscheinlich vernachlässigbar im Vergleich zu der Wartung, um sicherzustellen, dass es auf verschiedenen Plattformen arbeitet.

    Eine Alternative wäre, Ihre eigene Implementierung der Funktion in C zu schreiben und mit einem Python-Wrapper zu kommen. Sie müssten dann für jede Plattform, die Sie wollen, kompilieren, aber Sie verlieren die Mühe, den richtigen Bibliotheksnamen zu finden, während Sie die Geschwindigkeitsvorteile behalten.

    Um den Kommentar von S.Lott auszudrücken, wenn der LSB gesetzt ist, wird der Wert ungerade und wenn es klar ist, wird der Wert gleich sein. Daher können wir einfach den Wert nach rechts verschieben, bis es merkwürdig wird und verfolgt, wie viele Verschiebungen es dauert, damit dies geschieht. Denken Sie daran zu überprüfen, dass es ein bisschen gesetzt zuerst, sonst wird die Schleife endlos, wenn es den Wert 0 gegeben wird …

     >>> def ffs(num): ... # Check there is at least one bit set. ... if num == 0: ... return None ... # Right-shift until we have the first set bit in the LSB position. ... i = 0 ... while (num % 2) == 0: ... i += 1 ... num = num >> 1 ... return i ... >>> num = 136 >>> bin(num) '0b10001000' >>> ffs(num) 3 >>> ffs(0) is None True 

    Beachten Sie, dass dies die LSB als Bit 0 behandelt; Einfach initialisiere i auf 1, wenn du lieber eine 1-basierte Indizierung hast.

    Wirklich alle diese Antworten mit externen Modulen, definieren Funktionen, etc. für eine … bitweise Betrieb ???

     (1 + (x ^ (x-1))) >> 1 

    Wird die geringste Leistung von 2 in x zurückgeben.

    Zum Beispiel, mit x = 136, Antwort ist 2 ^ 3 = 8.

    Trick erinnert sich daran, dass x-1 die gleichen Ziffern wie x hat, mit Ausnahme aller am wenigsten signifikanten 1 und alle folgenden Nullen; Dann führt ein bitweises XOR Bitwin X aus und X + 1 extrahiert diese Ziffern.

    Dann können Sie den Index mit der Methode bit_length () extrahieren.

    Sie können irgendwelche der hier identifizierten Algorithmen implementieren: http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear

    Ich kenne keine native Methode, um dies zu tun. (Du könntest auch eine Erweiterung schreiben, um die C-Funktion in Python zu exportieren, aber das wäre wohl nicht der Mühe wert 🙂

    Es ist ein bisschen dumm zu versuchen und aggressiv optimieren Python-Code, so eine einfache für Schleife mit Zähler und Rechts-Verschiebung sollte gut sein. Wenn du schneller gehen wolltest (was in C, Java oder Assembly sinnvoller wäre) könntest du die Binär-Suche nach dem richtigen 1-Bit suchen und sogar Lookup-Tabellen benutzen, um dir zu helfen.

    Angenommen, x ist 64-Bits und du willst den LSB. Maske aus den unteren 32 Bits. Angenommen, x ist ungleich null:

     Wenn x & 0xffffffff == 0:
       Wenn x & 0xffff00000000 == 0:
         # Die LSB ist in den höchsten zwei Bytes
       sonst:
         # Die LSB ist im 5. oder 6. Byte
     sonst:
       Wenn x & 0xffff0000:
         # Das LSB ist im 3. oder 4. Byte
       sonst:
         # Der LSB ist im 1. oder 2. Byte
    

    Wie Sie mit dem kommentierten Abschnitt oben umgehen, hängt davon ab, wie aggressiv Sie sein möchten: Sie könnten weitere Binärsuche analog zu dem machen, was wir haben, oder Sie könnten eine Nachschlagtabelle verwenden. Wie es steht, haben wir 16 Bits Ungewissheit, also wäre unser Tisch 65.536 Einträge. Ich habe tatsächlich Tische wie diese für extrem leistungssensitiven Code gemacht, aber das war ein C-Programm, das Schach spielte (die 64-Bit-String gab es eine binäre Darstellung des Boards).

    Ich weiß, dass es schon eine ausgewählte Antwort gibt, aber ich habe selbst das Problem gehabt, weil ich könnte. Die Lösung basiert auf der Idee, dass, wenn der Wert eine Kraft von zwei ist, können Sie die Log-Basis zwei nehmen, um ihre Position zu finden. Der Rest der Implementierung dreht sich um die Umwandlung des Wertes, so dass wir einfach das Protokoll nehmen können.

    Ich habe es nicht benchmarkiert, aber die Transformation ist O (1) wobei n die Anzahl der Bits ist (und diese Ansicht ignoriert die Komplexität, die durch das log () eingeführt wird, etwas ungerecht, obwohl es vielleicht um O (log (n)) geht [ 1]?). Die Implementierung basiert lose auf der "Dekrementierung und Vergleich" Power-of-Two-Methode von [2]:

     import math def ffs(value): """Find the first set bit in an integer, returning its index (from zero)""" if 0 > value: raise ValueError("No negative values!") if 0 == value: # No bits are set in value return None if (value & (value - 1)) != 0: # Multiple bits are set in value. Transform value such that only the # lowest bit remains set. value &= ~ (value - 1) # Only one bit is set in value, find its index from zero return int(math.log(value, 2)) 

    [1] http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog

    [2] http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is–power-of-two-in-c/

    Python ist die beste Programmiersprache der Welt.