Ich möchte den schnellsten Weg finden, um den Index des niedrigstwertigen Bits einer langen Länge zu erhalten. zB:
%Vor%Lösungen mit Looping und Shifting sind zu langsam. zB:
%Vor%EDIT: Info zur Verwendung
Die Funktion, die fsll verwendet, kann ihre Verwendung nicht wirklich reduzieren, aber hier ist sie (vereinfacht natürlich). Es iteriert nur durch die Indizes und macht etwas mit ihnen. Diese Funktion ist vielleicht die am meisten verwendete Funktion in meiner gesamten Anwendung, trotz einer Menge Caching ihres Wertes. Es ist ein legaler Move-Generator in meiner alpha-beta Suchmaschine.
%Vor%Intel hat spezielle Anweisungen zum Auffinden von Bits mit der niedrigsten oder höchsten Ordnung. BSF scheint wie, was Sie brauchen. Soweit es in C zu tun hat, hat die Bit Twiddling Hacks Seite , was Sie brauchen.
>Zumindest könnten Sie eine Tabelle mit Nibbles oder Bytes verwenden, um die Dinge zu beschleunigen. So etwas (demonstriert für int, aber leicht änderbar, wenn nötig).
%Vor% Sie können das niedrigste gesetzte Bit mit x & (~x + 1) isolieren; Dadurch erhalten Sie den niedrigsten Bitwert, nicht den Index (z. B. wenn x = 01101000, dann ist das Ergebnis 00001000). Der schnellste Weg, den ich kenne, um von dort zu einem Index zu gelangen, ist wahrscheinlich eine switch-Anweisung:
Hässlich, aber keine Looping beteiligt.
Wie wäre es mit einer Art binärer Suche?
Betrachten Sie die niedrigen Bits, die sich aus einem bitweisen und einem Maskenwert ergeben, die alle Einsen in der unteren Hälfte sind. Wenn dieser Wert Null ist, wissen Sie, dass das kleinste Bit in der oberen Hälfte der Zahl ist.
schneiden Sie die Sache anders halb und gehen Sie wieder.
Wie wäre es mit so etwas? Es reduziert die Anzahl der Schleifen erheblich.
%Vor%Um das am meisten gesetzte Bit zu erhalten, kann der folgende Ausdruck verwendet werden:
Betrachte die Variable als X
x & amp; ~ (x - 1) gibt eine Binärzahl, die nur das gesetzte Bit enthält, mit dem Rest alle Nullen
Beispiel
%Vor%Verschieben Sie nun fortlaufend diese Binärzahl nach rechts, bis die Zahl Null ist, und zählen Sie die Anzahl der Verschiebungen, die die am weitesten rechts gesetzte Bitnummer ergeben.