Finde das höchstwertige Bit (ganz links), das in einem Bit-Array gesetzt ist

Ich habe eine Bit-Array-Implementierung, wobei der 0. Index das MSB des ersten Bytes in einem Array ist, der 8. Index das MSB des zweiten Bytes usw.

Was ist ein schneller Weg, um das erste Bit zu finden, das in diesem Bit-Array gesetzt ist? Alle verwandten Lösungen, die ich gesucht habe, finden das erste niedrigstwertige Bit, aber ich brauche das erste signifikanteste Bit. Also, mit 0x00A1, will ich 8 (da es das 9. Bit von links ist).

   

GCC hat __builtin_clz , das in BSR auf x86 / x64, CLZ auf ARM usw. übersetzt wird, und emuliert den Befehl, wenn die Hardware ihn nicht implementiert.
Visual C ++ 2005 und _BitScanReverse hat _BitScanReverse .

Als Performance-Junkie habe ich eine Menge Variationen für MSB-Set ausprobiert, das Folgende ist das Schnellste, auf das ich gestoßen bin,

 unsigned int msb32(unsigned int x) { static const unsigned int bval[] = {0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4}; unsigned int r = 0; if (x & 0xFFFF0000) { r += 16/1; x >>= 16/1; } if (x & 0x0000FF00) { r += 16/2; x >>= 16/2; } if (x & 0x000000F0) { r += 16/4; x >>= 16/4; } return r + bval[x]; } 

tl: dr; Für 32 Bits verwenden Sie de Bruijn Multiplikation .

Es ist der “schnellste” portable Algorithmus. Es ist wesentlich schneller und korrekter als alle anderen tragbaren 32-Bit-MSB-Algorithmen in diesem Thread.

Der de Bruijn-Algorithmus gibt auch ein korrektes Ergebnis zurück, wenn die Eingabe Null ist. Die Befehle __builtin_clz und _BitScanReverse geben falsche Ergebnisse zurück, wenn die Eingabe Null ist.

Auf x86-64 läuft de Bruijn-Multiplikation mit einer Geschwindigkeit, die mit der entsprechenden (errorshaften) Hardware-statement vergleichbar ist , mit einer performancesdifferenz von nur etwa 3%.

Hier ist der Code.

 u32 msbDeBruijn32( u32 v ) { static const int MultiplyDeBruijnBitPosition[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; v |= v >> 1; // first round down to one less than a power of 2 v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; return MultiplyDeBruijnBitPosition[( u32 )( v * 0x07C4ACDDU ) >> 27]; } 

Alle anderen Antworten in diesem Thread laufen entweder viel schlechter, als ihre Autoren vorschlagen, oder berechnen das Ergebnis nicht richtig oder beides. Lassen Sie uns sie alle benchmarken und lassen Sie uns überprüfen, ob sie das tun, was sie vorgeben.

Hier ist ein einfacher C ++ 11-Kabelbaum, um alle diese Implementierungen zu testen. Es kompiliert Clean in Visual Studio, sollte aber an allen modernen Compilern funktionieren. Sie können den Benchmark im Performance-Modus (bVerifyResults = false) und im Prüfmodus (bVerifyResults = true) ausführen.

Hier sind die Ergebnisse im Verifikationsmodus:

 Verification failed for msbNative64: input was 0; output was 818af060; expected 0 Verification failed for msbFfs: input was 22df; output was 0; expected d Verification failed for msbPerformanceJunkie32: input was 0; output was ffffffff; expected 0 Verification failed for msbNative32: input was 0; output was 9ab07060; expected 0 

Der “Performance-Junkie” und die nativen Implementierungen von Microsoft machen verschiedene Dinge, wenn die Eingabe Null ist. msbPerformanceJunkie32 erzeugt -1 und Microsofts _BitScanReverse erzeugt eine Zufallszahl, die mit der zugrunde liegenden Hardwareanweisung übereinstimmt. Auch die msbPerformanceJunkie32-Implementierung erzeugt ein Ergebnis, das um eins von allen anderen Antworten abweicht.

Hier sind die Ergebnisse im Performance-Modus, läuft auf meinem Laptop i7-4600, im Freigabemodus kompiliert:

 msbLoop64 took 2.56751 seconds msbNative64 took 0.222197 seconds msbLoop32 took 1.43456 seconds msbFfs took 0.525097 seconds msbPerformanceJunkie32 took 1.07939 seconds msbDeBruijn32 took 0.224947 seconds msbNative32 took 0.218275 seconds 

Die de Bruijn-Version übertrifft die anderen Implementierungen deutlich, da sie nicht verzweigt ist und daher gut gegen Eingaben läuft, die einen gleichmäßig verteilten Satz von Ausgaben erzeugen. Alle anderen Versionen sind langsamer gegenüber willkürlichen Eingaben aufgrund der Nachteile der Verzweigungsfehlvorhersage bei modernen CPUs. Die function smbFfs erzeugt falsche Ergebnisse und kann daher ignoriert werden.

Einige der Implementierungen arbeiten an 32-Bit-Eingängen und einige an 64-Bit-Eingängen. Eine Vorlage hilft uns, Äpfel mit Äpfeln zu vergleichen, unabhängig von der Eingabegröße.

Hier ist der Code. Laden Sie die Benchmarks herunter und führen Sie sie selbst aus, wenn Sie möchten.

 #include  #include  #include  #include  #include  #include  #ifdef _MSC_VER #define MICROSOFT_COMPILER 1 #include  #endif // _MSC_VER const int iterations = 100000000; bool bVerifyResults = false; std::random_device rd; std::default_random_engine re(rd()); typedef unsigned int u32; typedef unsigned long long u64; class Timer { public: Timer() : beg_(clock_::now()) {} void reset() { beg_ = clock_::now(); } double elapsed() const { return std::chrono::duration_cast (clock_::now() - beg_).count(); } private: typedef std::chrono::high_resolution_clock clock_; typedef std::chrono::duration > second_; std::chrono::time_point beg_; }; unsigned int msbPerformanceJunkie32(u32 x) { static const unsigned int bval[] = { 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4 }; unsigned int r = 0; if (x & 0xFFFF0000) { r += 16 / 1; x >>= 16 / 1; } if (x & 0x0000FF00) { r += 16 / 2; x >>= 16 / 2; } if (x & 0x000000F0) { r += 16 / 4; x >>= 16 / 4; } return r + bval[x]; } #define FFS(t) \ { \ register int n = 0; \ if (!(0xffff & t)) \ n += 16; \ if (!((0xff < < n) & t)) \ n += 8; \ if (!((0xf << n) & t)) \ n += 4; \ if (!((0x3 << n) & t)) \ n += 2; \ if (!((0x1 << n) & t)) \ n += 1; \ return n; \ } unsigned int msbFfs32(u32 x) { FFS(x); } unsigned int msbLoop32(u32 x) { int r = 0; if (x < 1) return 0; while (x >>= 1) r++; return r; } unsigned int msbLoop64(u64 x) { int r = 0; if (x < 1) return 0; while (x >>= 1) r++; return r; } u32 msbDeBruijn32(u32 v) { static const int MultiplyDeBruijnBitPosition[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; v |= v >> 1; // first round down to one less than a power of 2 v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; return MultiplyDeBruijnBitPosition[(u32)(v * 0x07C4ACDDU) >> 27]; } #ifdef MICROSOFT_COMPILER u32 msbNative32(u32 val) { unsigned long result; _BitScanReverse(&result, val); return result; } u32 msbNative64(u64 val) { unsigned long result; _BitScanReverse64(&result, val); return result; } #endif // MICROSOFT_COMPILER template  void test(unsigned int msbFunc(InputType), const std::string &name, const std::vector< InputType > &inputs, std::vector< unsigned int > &results, bool bIsReference = false ) { if (bIsReference) { int i = 0; for (int i = 0; i < iterations; i++) results[i] = msbFunc(inputs[i]); } InputType result; if (bVerifyResults) { bool bNotified = false; for (int i = 0; i < iterations; i++) { result = msbFunc(inputs[i]); if ((result != results[i]) && !bNotified) { std::cout << "Verification failed for " << name << ": " << "input was " << std::hex << inputs[i] << "; output was " << result << "; expected " << results[i] << std::endl; bNotified = true; } } } else { Timer t; for (int i = 0; i < iterations; i++) { result = msbFunc(inputs[i]); } double elapsed = t.elapsed(); if ( !bIsReference ) std::cout << name << " took " << elapsed << " seconds" << std::endl; if (result == -1.0f) std::cout << "this comparison only exists to keep the compiler from " << "optimizing out the benchmark; this branch will never be called"; } } void main() { std::uniform_int_distribution  dist64(0, std::numeric_limits< u64 >::max()); std::uniform_int_distribution  shift64(0, 63); std::vector< u64 > inputs64; for (int i = 0; i < iterations; i++) { inputs64.push_back(dist64(re) >> shift64(re)); } std::vector< u32 > results64; results64.resize(iterations); test< u64 >(msbLoop64, "msbLoop64", inputs64, results64, true); test< u64 >(msbLoop64, "msbLoop64", inputs64, results64, false); #ifdef MICROSOFT_COMPILER test< u64 >(msbNative64, "msbNative64", inputs64, results64, false); #endif // MICROSOFT_COMPILER std::cout < < std::endl; std::uniform_int_distribution  dist32(0, std::numeric_limits< u32 >::max()); std::uniform_int_distribution  shift32(0, 31); std::vector< u32 > inputs32; for (int i = 0; i < iterations; i++) inputs32.push_back(dist32(re) >> shift32(re)); std::vector< u32 > results32; results32.resize(iterations); test< u32 >(msbLoop32, "msbLoop32", inputs32, results32, true); test< u32 >(msbLoop32, "msbLoop32", inputs32, results32, false); test< u32 >(msbFfs32, "msbFfs", inputs32, results32, false); test< u32 >(msbPerformanceJunkie32, "msbPerformanceJunkie32", inputs32, results32, false); test< u32 >(msbDeBruijn32, "msbDeBruijn32", inputs32, results32, false); #ifdef MICROSOFT_COMPILER test< u32 >(msbNative32, "msbNative32", inputs32, results32, false); #endif // MICROSOFT_COMPILER } 

Es gibt mehrere Möglichkeiten, dies zu tun, und die relative performance der verschiedenen Implementierungen ist etwas maschinenabhängig (ich habe dies zu einem ähnlichen Zweck für einen ähnlichen Zweck getestet). Auf einigen Rechnern gibt es sogar einen eingebauten Befehl (verwenden Sie einen, wenn verfügbar und Portabilität kann behandelt werden).

Sehen Sie sich hier einige Implementierungen an (unter “integer log base 2”). Wenn Sie GCC verwenden, überprüfen Sie die functionen __builtin_clz und __builtin_clzl (die dies für nicht null vorzeichenlose Ints bzw. unsigned longs tun). Der “clz” steht für “count führenden Nullen”, die eine andere Möglichkeit ist, das gleiche Problem zu beschreiben.

Wenn Ihr Bit-Array nicht in ein geeignetes Maschinenwort passt, müssen Sie natürlich über Wörter im Array iterieren, um das erste von Null verschiedene Wort zu finden, und dann diese Berechnung nur für dieses Wort durchführen.

Lesen Sie die BSR (Bit Scan Reverse) x86 asm statement für den schnellsten Weg, dies zu tun. Aus dem Dokument von Intel: Searches the source operand (second operand) for the most significant set bit (1 bit). If a most significant 1 bit is found, its bit index is stored in the destination operand (first operand). Searches the source operand (second operand) for the most significant set bit (1 bit). If a most significant 1 bit is found, its bit index is stored in the destination operand (first operand).

Zwei beste Möglichkeiten, dies in reinem C zu tun:

Suchen Sie zuerst linear nach dem Byte- / Wort-Array, um das erste Byte / Wort zu finden, das ungleich Null ist, und führen Sie dann eine entrollte Binärsuche des gefundenen Bytes / Wortes durch.

 if (b>=0x10) if (b>=0x40) if (b>=0x80) return 0; else return 1; else if (b>=0x20) return 2; else return 3; else if (b>=0x4) if (b>=0x8) return 4; else return 5; else if (b>=0x2) return 6; else return 7; 

3 (BTW das ist log2 (8)) bedingte Sprünge, um die Antwort zu bekommen. Auf modernen x86-Rechnern wird der letzte auf eine bedingte mov optimiert.

Verwenden Sie alternativ eine Nachschlagetabelle, um das Byte dem Index des ersten gesetzten Bits zuzuordnen.

Ein verwandtes Thema, das Sie möglicherweise nachschlagen möchten, ist ganzzahlige log2-functionen. Wenn ich mich erinnere, hat ffmpeg eine nette Implementierung.

Bearbeiten: Sie können die obige binäre Suche tatsächlich zu einer zweiglosen binären Suche machen, aber ich bin mir nicht sicher, ob es in diesem Fall effizienter wäre …

Hier ist ein Codeausschnitt, der __builtin_clz () erklärt

 ////// go.c //////// #include  unsigned NUM_BITS_U = ((sizeof(unsigned) < < 3) - 1); #define POS_OF_HIGHESTBITclz(a) (NUM_BITS_U - __builtin_clz(a)) /* only works for a != 0 */ #define NUM_OF_HIGHESTBITclz(a) ((a) \ ? (1U << POS_OF_HIGHESTBITclz(a)) \ : 0) int main() { unsigned ui; for (ui = 0U; ui < 18U; ++ui) printf("%i \t %i\n", ui, NUM_OF_HIGHESTBITclz(ui)); return 0; } 

Wenn Sie x86 verwenden, können Sie praktisch jede byteweise oder wortweise Lösung mit den SSE2-Operationen kombinieren, kombiniert mit den statementen find-first-bit, die (in der gcc-Welt) mit “ffs” ausgesprochen werden “für das niedrigste Bit und” fls “für das höchste Bit. Entschuldigen Sie, dass ich Probleme habe (! @ # $% ^) Formatierung “C” -Code in einer Antwort; check out: http://mischasan.wordpress.com/2011/11/03/sse2-bit-trick-ffsfls-for-xmm-registers/

Nicht der Schnellste, aber es funktioniert …

 //// C program #include  #define POS_OF_HIGHESTBIT(a) /* 0th position is the Least-Signif-Bit */ \ ((unsigned) log2(a)) /* thus: do not use if a < = 0 */ #define NUM_OF_HIGHESTBIT(a) ((!(a)) \ ? 0 /* no msb set*/ \ : (1 << POS_OF_HIGHESTBIT(a) )) // could be changed and optimized, if it is known that the following NEVER holds: a <= 0 int main() { unsigned a = 5; // 0b101 unsigned b = NUM_OF_HIGHESTBIT(a); // 4 since 4 = 0b100 return 0; } 

Ich habe mit einer Reihe von functionen gearbeitet, um das höchstwertige Bit zu bekommen, aber Probleme treten im Allgemeinen auf, wenn man zwischen 32- und 64-Bit-Zahlen wechselt oder zwischen x86_64- und x86-Kästchen wechselt. Die functionen __builtin_clz , __builtin_clzl und __builtin_clzll funktionieren gut für 32/64 Bit-Nummern und für x86_64- und x86-Computer. Es sind jedoch drei functionen erforderlich. Ich habe ein einfaches MSB gefunden, das auf einer Rechtsverschiebung beruht, die alle Fälle für positive Zahlen behandelt. Zumindest für den Gebrauch, den ich daraus mache, ist es gelungen, wo andere versagt haben:

 int getmsb (unsigned long long x) { int r = 0; if (x < 1) return 0; while (x >>= 1) r++; return r; } 

Durch Angabe von Eingabe als unsigned long long kann sie alle Zahlenklassen von unsigned char bis unsigned long long und ist aufgrund der Standarddefinition für x86_64- und x86-Builds kompatibel. Der Fall für 0 ist so definiert, dass er 0 , kann jedoch nach Bedarf geändert werden. Ein einfacher Test und eine Ausgabe sind:

 int main (int argc, char *argv[]) { unsigned char c0 = 0; unsigned char c = 216; unsigned short s = 1021; unsigned int ui = 32768; unsigned long ul = 3297381253; unsigned long long ull = 323543844043; int i = 32767; printf (" %16u MSB : %d\n", c0, getmsb (c0)); printf (" %16u MSB : %d\n", c, getmsb (c)); printf (" %16u MSB : %d\n", s, getmsb (s)); printf (" %16u MSB : %d\n", i, getmsb (i)); printf (" %16u MSB : %d\n", ui, getmsb (ui)); printf (" %16lu MSB : %d\n", ul, getmsb (ul)); printf (" %16llu MSB : %d\n", ull, getmsb (ull)); return 0; } 

Ausgabe:

  0 MSB : 0 216 MSB : 7 1021 MSB : 9 32767 MSB : 14 32768 MSB : 15 3297381253 MSB : 31 323543844043 MSB : 38 

HINWEIS: Aus __builtin_clzll Geschwindigkeit ist die Verwendung einer einzelnen function um __builtin_clzll herum __builtin_clzll noch um einen Faktor von etwa 6 schneller.

Ich werde eins hinzufügen!

 typedef unsigned long long u64; typedef unsigned int u32; typedef unsigned char u8; u8 findMostSignificantBit (u64 u64Val) { u8 u8Shift; u8 u8Bit = 0; assert (u64Val != 0ULL); for (u8Shift = 32 ; u8Shift != 0 ; u8Shift >>= 1) { u64 u64Temp = u64Val >> u8Shift; if (u64Temp) { u8Bit |= u8Shift; // notice not using += u64Val = u64Temp; } } return u8Bit; } 

Natürlich arbeitet dies an einer 64-Bit-Nummer (unsigned long long) und nicht an einem Array. Außerdem haben viele Leute auf eingebaute g ++ functionen hingewiesen, von denen ich nicht wusste. Wie interessant.

Jedenfalls findet dies das signifikanteste Bit in 6 Iterationen und gibt eine Bestätigung, wenn Sie 0 an die function übergeben haben. Nicht die beste function, wenn Sie Zugriff auf eine statement des Chipsatzes haben.

Ich verwende auch | = anstelle von + =, weil diese immer Zweierpotenzen sind, und ODER ist (klassisch) schneller als Addition. Da ich nur einzigartige 2er-Potenzen addiere, habe ich nie einen Rollover.

Dies ist eine binäre Suche, was bedeutet, dass das Ergebnis immer in 6 Iterationen gefunden wird.

Auch das ist besser:

 u8 findMostSignificantBit2 (u64 u64Val) { assert (u64Val != 0ULL); return (u8) (__builtin_ctzll(u64Val)); } 

Hier ist ein einfacher Brute-Force-Algorithmus für ein Byte-Array beliebiger Größe:

 int msb( unsigned char x); // prototype for function that returns // most significant bit set unsigned char* p; for (p = arr + num_elements; p != arr;) { --p; if (*p != 0) break; } // p is with pointing to the last byte that has a bit set, or // it's pointing to the first byte in the array if (*p) { return ((p - arr) * 8) + msb( *p); } // what do you want to return if no bits are set? return -1; 

Ich werde es als eine Übung für den Leser, um mit einer geeigneten function msb() sowie die Optimierung zu arbeiten, um int oder long long Ritzen von Daten zu arbeiten.

Ähm, Ihr Tag zeigt 32bit an, aber es sieht so aus, als ob die Werte, die Sie verwenden, 16 Bit sind. Wenn du 32 Bit meinst, dann denke ich, dass die Antwort für 0x00a1 24 und nicht 8 sein sollte.

Angenommen, Sie suchen nach dem MSB-Bit-Index von der linken Seite und Sie wissen, dass Sie nur mit uint32_t arbeiten werden, hier ist der offensichtliche, einfältige Algorithmus:

 #include  #include  #include  int main() { uint32_t test_value = 0x00a1; int i; for (i=0; i<32; ++i) { if (test_value & (0x80000000 >> i)) { printf("i = %d\n", i); exit(0); } } return 0; } 
 #define FFS(t) \ ({ \ register int n = 0; \ \ if (!(0xffff & t)) \ n += 16; \ \ if (!((0xff < < n) & t)) \ n += 8; \ \ if (!((0xf << n) & t)) \ n += 4; \ \ if (!((0x3 << n) & t)) \ n += 2; \ \ if (!((0x1 << n) & t)) \ n += 1; \ \ n; \ })