Ich versuche einige Pack- und Entpackroutinen zu optimieren. Um das Packen durchzuführen, muss ich die Anzahl der Bits berechnen, die benötigt werden, um ganzzahlige Werte zu speichern. Hier ist der aktuelle Code.
%Vor%Sie suchen nach der Ganzzahl log base 2 einer Zahl (das l = höchste gesetzte Bit). Sean Andersons "Bit Twiddling Hacks" -Seite hat mehrere Methoden, die von den offensichtlichen Zählbits in einer Schleife bis zu Versionen reichen, die eine Tabellensuche verwenden. Beachten Sie, dass die meisten der vorgestellten Methoden etwas modifiziert werden müssen, um mit 64-Bit-Ints zu arbeiten, wenn diese Art der Portabilität für Sie wichtig ist.
Stellen Sie nur sicher, dass jede Verschiebung, die Sie verwenden, um das höchste Bit-Set zu erstellen, auf einer unsigned Version der Zahl ausgeführt werden muss, da eine Compilerimplementierung die Operation >> möglicherweise verlängert oder nicht verlängert ein signierter Wert.
Verwenden Sie nicht portabel den Bit-Scan-Reverse-Opcode, der auf den meisten modernen Architekturen verfügbar ist. Es wird als intrinsisch in Visual C ++ veröffentlicht.
>Portabel benötigt der Code in der Frage die Edge-Case-Behandlung nicht. Warum benötigen Sie ein Bit für die Speicherung von 0? In jedem Fall werde ich die Ränder des Problems ignorieren. Die Eingeweide können so effizient gemacht werden:
%Vor%Was Sie versuchen, ist das wichtigste Bit zu finden. Einige Architekturen haben eine spezielle Anweisung nur für diesen Zweck. Für diejenigen, die dies nicht tun, verwenden Sie eine Tabellen-Lookup-Methode.
Erstellen Sie eine Tabelle mit 256 Einträgen, wobei jedes Element das oberste Bit identifiziert.
Durchlaufen Sie jedes Byte in der Zahl oder verwenden Sie einige if-Anweisungen, um das höchstwertige Nicht-Null-Byte zu finden.
Ich lasse Sie den Rest von hier nehmen.
Sie müßten die Ausführungszeit überprüfen, um die Granularität zu bestimmen, aber meine Vermutung ist, dass es 4 Bits gleichzeitig macht und dann wieder auf ein Bit zu einem Zeitpunkt zurückgeht, würde es schneller machen. Protokolloperationen wären wahrscheinlich langsamer als logische / Bit-Operationen.
%Vor%Tags und Links c++ bit-manipulation bits