Was ist der schnellste / effizienteste Weg, um das höchste gesetzte Bit (msb) in einer Ganzzahl in C zu finden?

Wenn ich eine ganze Zahl n habe und die Position des höchstwertigen Bits wissen möchte (dh wenn das niedrigstwertige Bit rechts ist, möchte ich die Position des am weitesten links liegenden Bits wissen, das eine 1 ist). Was ist die schnellste / effizienteste Methode, um dies herauszufinden?

Ich weiß, dass POSIX eine ffs()Methode in strings.h unterstützt, um das erste gesetzte Bit zu finden, aber es scheint keine entsprechende fls()Methode zu geben.

Gibt es einen wirklich offensichtlichen Weg, dies zu tun, den ich vermisse?

Was ist in Fällen, in denen Sie POSIX-Funktionen für die Portabilität nicht verwenden können?

Bearbeiten: Was ist mit einer Lösung, die sowohl auf 32- als auch auf 64-Bit-Architekturen funktioniert (viele der Codelisten scheinen nur auf 32-Bit-Ints zu funktionieren).

GCC hat :

 - Integrierte Funktion: int __builtin_clz (unsigned int x)
     Gibt die Anzahl der führenden 0-Bits in X zurück, beginnend mit höchstens
     signifikante Bitposition. Wenn X 0 ist, ist das Ergebnis undefiniert.

 - Eingebaute Funktion: int __builtin_clzl (unsigned long)
     Ähnlich wie "__builtin_clz", außer dass der Argumenttyp "unsigned" ist
     lange'.

 - Eingebaute Funktion: int __builtin_clzll (unsigned long long)
     Ähnlich wie "__builtin_clz", außer dass der Argumenttyp "unsigned" ist
     lang Lang'.

Ich würde erwarten, dass sie in etwas übersetzt werden, das für Ihre aktuelle Plattform einigermaßen effizient ist, sei es einer dieser ausgefallenen Bit-Twiddling-Algorithmen oder eine einzelne Anweisung.

Ein nützlicher Trick, wenn Ihre Eingabe Null sein kann , ist __builtin_clz(x | 1): Das bedingungslose Setzen des Low-Bits, ohne andere zu ändern, bewirkt die Ausgabe 31fürx=0 , ohne die Ausgabe für einen anderen Eingang zu ändern.

Um dies zu vermeiden, sind plattformspezifische Eigenschaften wie ARM-GCCs __clz(kein Header erforderlich) oder x86- _lzcnt_u32CPUs auf CPUs, die die lzcntAnweisung unterstützen , eine andere Option . (Vorsicht, das lzcntdekodiert alsbsr Beachten bei älteren CPUs erfolgt, anstatt Fehler zu verursachen, was 31-lzcnt für Eingaben ungleich Null ergibt.)

Es gibt leider keine Möglichkeit, die verschiedenen CLZ-Anweisungen auf Nicht-x86-Plattformen, die das Ergebnis für input = 0 als 32 oder 64 definieren (je nach Operandenbreite), portabel zu nutzen. x86 lzcntmacht das auch, während es bsreinen Bitindex erzeugt, den der Compiler umdrehen muss, wenn Sie ihn nicht verwenden 31-__builtin_clz(x).

(Das "undefinierte Ergebnis" ist nicht C Undefiniertes Verhalten, sondern nur ein Wert, der nicht definiert ist. Es ist eigentlich alles, was sich im Zielregister befand, als die Anweisung ausgeführt wurde. AMD dokumentiert dies, Intel nicht, aber Intels CPUs implementieren dieses Verhalten Aber es ist nicht das, was zuvor in der C-Variablen war, der Sie zugewiesen haben. So funktioniert es normalerweise nicht, wenn gcc C in asm umwandelt . Siehe auch Warum ist es wichtig, die "Ausgabeabhängigkeit" von LZCNT zu brechen? )

Angenommen, Sie sind auf x86 und spielen ein bisschen Inline-Assembler. Intel bietet eine BSRAnweisung ("Bit Scan Reverse"). Es ist schnell auf einigen x86s (Mikrocode auf andere). Aus dem Handbuch:

Durchsucht den Quelloperanden nach dem höchstwertigen gesetzten Bit (1 Bit). Wenn ein höchstwertiges 1-Bit gefunden wird, wird sein Bitindex im Zieloperanden gespeichert. Der Quelloperand kann ein Register oder ein Speicherort sein; Der Zieloperand ist ein Register. Der Bitindex ist ein vorzeichenloser Offset von Bit 0 des Quelloperanden. Wenn der Inhaltsquellenoperand 0 ist, ist der Inhalt des Zieloperanden undefiniert.

(Wenn Sie auf PowerPC sind, gibt es eine ähnliche cntlz Anweisung ("führende Nullen zählen").)

Beispielcode für gcc:

#include <iostream>

int main (int,char**)
{
  int n=1;
  for (;;++n) {
    int msb;
    asm("bsrl %1,%0" : "=r"(msb) : "r"(n));
    std::cout << n << " : " << msb << std::endl;
  }
  return 0;
}

Siehe auch dieses Inline-Assembler-Tutorial , das zeigt (Abschnitt 9.4), dass es erheblich schneller ist als das Schleifen von Code.

Da 2 ^ N eine ganze Zahl ist, bei der nur das N-te Bit gesetzt ist (1 << N), ist das Finden der Position (N) des höchsten gesetzten Bits die ganzzahlige Protokollbasis 2 dieser ganzen Zahl.

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

unsigned int v;
unsigned r = 0;

while (v >>= 1) {
    r++;
}

Dieser "offensichtliche" Algorithmus ist möglicherweise nicht für alle transparent, aber wenn Sie feststellen, dass sich der Code wiederholt um ein Bit nach rechts verschiebt, bis das Bit ganz links verschoben wurde (beachten Sie, dass C jeden Wert ungleich Null als wahr behandelt) und die Zahl zurückgibt von Schichten macht es vollkommen Sinn. Dies bedeutet auch, dass es auch dann funktioniert, wenn mehr als ein Bit gesetzt ist - das Ergebnis ist immer für das höchstwertige Bit.

Wenn Sie auf dieser Seite nach unten scrollen, gibt es schnellere und komplexere Variationen. Wenn Sie jedoch wissen, dass Sie mit Zahlen mit vielen führenden Nullen arbeiten, bietet der naive Ansatz möglicherweise eine akzeptable Geschwindigkeit, da die Bitverschiebung in C ziemlich schnell ist und der einfache Algorithmus keine Indizierung eines Arrays erfordert.

HINWEIS: Seien Sie bei der Verwendung von 64-Bit-Werten äußerst vorsichtig, wenn Sie besonders clevere Algorithmen verwenden. Viele von ihnen funktionieren nur für 32-Bit-Werte korrekt.

Dies sollte blitzschnell sein:

int msb(unsigned int v) {
  static const int pos[32] = {0, 1, 28, 2, 29, 14, 24, 3,
    30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
    16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;
  v = (v >> 1) + 1;
  return pos[(v * 0x077CB531UL) >> 27];
}

Dies ist so etwas wie das Finden einer Art Ganzzahlprotokoll. Es gibt ein bisschen Tricks, aber ich habe mein eigenes Werkzeug dafür gemacht. Das Ziel ist natürlich die Geschwindigkeit.

Meine Erkenntnis ist, dass die CPU bereits einen automatischen Bitdetektor hat, der für die Ganzzahl-Float-Konvertierung verwendet wird! Also benutze das.

double ff=(double)(v|1);
return ((*(1+(uint32_t *)&ff))>>20)-1023;  // assumes x86 endianness

Diese Version wandelt den Wert in ein Double um und liest dann den Exponenten ab, der Ihnen sagt, wo sich das Bit befand. Die ausgefallene Verschiebung und Subtraktion besteht darin, die richtigen Teile aus dem IEEE-Wert zu extrahieren.

Die Verwendung von Floats ist etwas schneller, aber ein Float kann Ihnen aufgrund seiner geringeren Genauigkeit nur die ersten 24-Bit-Positionen geben.

Um dies sicher und ohne undefiniertes Verhalten in C ++ oder C zu tun, verwenden Sie memcpyanstelle des Zeiger-Castings das Typ-Punning. Compiler wissen, wie man es effizient einbindet.

// static_assert(sizeof(double) == 2 * sizeof(uint32_t), "double isn't 8-byte IEEE binary64");
// and also static_assert something about FLT_ENDIAN?

double ff=(double)(v|1);

uint32_t tmp;
memcpy(&tmp, ((const char*)&ff)+sizeof(uint32_t), sizeof(uint32_t));
return (tmp>>20)-1023;

Oder verwenden Sie in C99 und höher a union {double d; uint32_t u[2];};. Beachten Sie jedoch, dass in C ++ das Punnen vom Unionstyp nur auf einigen Compilern als Erweiterung unterstützt wird, nicht in ISO C ++.

Dies ist normalerweise langsamer als eine plattformspezifische Eigenschaft für einen Zählbefehl mit führenden Nullen, aber tragbares ISO C hat keine solche Funktion. Einige CPUs haben auch keinen Befehl zum Zählen von führenden Nullen, aber einige von diesen können Ganzzahlen effizient in konvertierendouble . Das Zurückschreiben eines FP-Bitmusters auf eine Ganzzahl kann jedoch langsam sein (z. B. erfordert es auf PowerPC ein Speichern / Neuladen und verursacht normalerweise ein Laden-Hit-Store-Stillstand).

Dieser Algorithmus könnte möglicherweise für SIMD-Implementierungen nützlich sein, da weniger CPUs über SIMD verfügen lzcnt. x86 hat eine solche Anweisung nur mit AVX512CD erhalten

Kaz Kylheku hier

Ich habe zwei Ansätze für diese über 63-Bit-Zahlen (den langen langen Typ auf gcc x86_64) verglichen, wobei ich mich vom Vorzeichenbit fernhielt.

(Ich brauche zufällig dieses "höchste Bit finden" für etwas, verstehen Sie?)

Ich habe die datengesteuerte binäre Suche implementiert (eng basierend auf einer der obigen Antworten). Ich habe auch einen vollständig abgewickelten Entscheidungsbaum von Hand implementiert, der nur Code mit unmittelbaren Operanden ist. Keine Schleifen, keine Tabellen.

Der Entscheidungsbaum (höchstes_bit_unrolled) wurde mit 69% schneller bewertet, mit Ausnahme des Falls n = 0, für den die binäre Suche einen expliziten Test hat.

Der Spezialtest der Binärsuche für den Fall 0 ist nur 48% schneller als der Entscheidungsbaum, für den es keinen Spezialtest gibt.

Compiler, Maschine: (GCC 4.5.2, -O3, x86-64, 2867 MHz Intel Core i5).

int highest_bit_unrolled(long long n)
{
  if (n & 0x7FFFFFFF00000000) {
    if (n & 0x7FFF000000000000) {
      if (n & 0x7F00000000000000) {
        if (n & 0x7000000000000000) {
          if (n & 0x4000000000000000)
            return 63;
          else
            return (n & 0x2000000000000000) ? 62 : 61;
        } else {
          if (n & 0x0C00000000000000)
            return (n & 0x0800000000000000) ? 60 : 59;
          else
            return (n & 0x0200000000000000) ? 58 : 57;
        }
      } else {
        if (n & 0x00F0000000000000) {
          if (n & 0x00C0000000000000)
            return (n & 0x0080000000000000) ? 56 : 55;
          else
            return (n & 0x0020000000000000) ? 54 : 53;
        } else {
          if (n & 0x000C000000000000)
            return (n & 0x0008000000000000) ? 52 : 51;
          else
            return (n & 0x0002000000000000) ? 50 : 49;
        }
      }
    } else {
      if (n & 0x0000FF0000000000) {
        if (n & 0x0000F00000000000) {
          if (n & 0x0000C00000000000)
            return (n & 0x0000800000000000) ? 48 : 47;
          else
            return (n & 0x0000200000000000) ? 46 : 45;
        } else {
          if (n & 0x00000C0000000000)
            return (n & 0x0000080000000000) ? 44 : 43;
          else
            return (n & 0x0000020000000000) ? 42 : 41;
        }
      } else {
        if (n & 0x000000F000000000) {
          if (n & 0x000000C000000000)
            return (n & 0x0000008000000000) ? 40 : 39;
          else
            return (n & 0x0000002000000000) ? 38 : 37;
        } else {
          if (n & 0x0000000C00000000)
            return (n & 0x0000000800000000) ? 36 : 35;
          else
            return (n & 0x0000000200000000) ? 34 : 33;
        }
      }
    }
  } else {
    if (n & 0x00000000FFFF0000) {
      if (n & 0x00000000FF000000) {
        if (n & 0x00000000F0000000) {
          if (n & 0x00000000C0000000)
            return (n & 0x0000000080000000) ? 32 : 31;
          else
            return (n & 0x0000000020000000) ? 30 : 29;
        } else {
          if (n & 0x000000000C000000)
            return (n & 0x0000000008000000) ? 28 : 27;
          else
            return (n & 0x0000000002000000) ? 26 : 25;
        }
      } else {
        if (n & 0x0000000000F00000) {
          if (n & 0x0000000000C00000)
            return (n & 0x0000000000800000) ? 24 : 23;
          else
            return (n & 0x0000000000200000) ? 22 : 21;
        } else {
          if (n & 0x00000000000C0000)
            return (n & 0x0000000000080000) ? 20 : 19;
          else
            return (n & 0x0000000000020000) ? 18 : 17;
        }
      }
    } else {
      if (n & 0x000000000000FF00) {
        if (n & 0x000000000000F000) {
          if (n & 0x000000000000C000)
            return (n & 0x0000000000008000) ? 16 : 15;
          else
            return (n & 0x0000000000002000) ? 14 : 13;
        } else {
          if (n & 0x0000000000000C00)
            return (n & 0x0000000000000800) ? 12 : 11;
          else
            return (n & 0x0000000000000200) ? 10 : 9;
        }
      } else {
        if (n & 0x00000000000000F0) {
          if (n & 0x00000000000000C0)
            return (n & 0x0000000000000080) ? 8 : 7;
          else
            return (n & 0x0000000000000020) ? 6 : 5;
        } else {
          if (n & 0x000000000000000C)
            return (n & 0x0000000000000008) ? 4 : 3;
          else
            return (n & 0x0000000000000002) ? 2 : (n ? 1 : 0);
        }
      }
    }
  }
}

int highest_bit(long long n)
{
  const long long mask[] = {
    0x000000007FFFFFFF,
    0x000000000000FFFF,
    0x00000000000000FF,
    0x000000000000000F,
    0x0000000000000003,
    0x0000000000000001
  };
  int hi = 64;
  int lo = 0;
  int i = 0;

  if (n == 0)
    return 0;

  for (i = 0; i < sizeof mask / sizeof mask[0]; i++) {
    int mi = lo + (hi - lo) / 2;

    if ((n >> mi) != 0)
      lo = mi;
    else if ((n & (mask[i] << lo)) != 0)
      hi = mi;
  }

  return lo + 1;
}

Schnelles und schmutziges Testprogramm:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int highest_bit_unrolled(long long n);
int highest_bit(long long n);

main(int argc, char **argv)
{
  long long n = strtoull(argv[1], NULL, 0);
  int b1, b2;
  long i;
  clock_t start = clock(), mid, end;

  for (i = 0; i < 1000000000; i++)
    b1 = highest_bit_unrolled(n);

  mid = clock();

  for (i = 0; i < 1000000000; i++)
    b2 = highest_bit(n);

  end = clock();

  printf("highest bit of 0x%llx/%lld = %d, %d\n", n, n, b1, b2);

  printf("time1 = %d\n", (int) (mid - start));
  printf("time2 = %d\n", (int) (end - mid));
  return 0;
}

Wenn nur -O2 verwendet wird, wird der Unterschied größer. Der Entscheidungsbaum ist fast viermal schneller.

Ich habe mich auch mit dem naiven Bitverschiebungscode verglichen:

int highest_bit_shift(long long n)
{
  int i = 0;
  for (; n; n >>= 1, i++)
    ; /* empty */
  return i;
}

Dies ist nur für kleine Zahlen schnell, wie man erwarten würde. Bei der Bestimmung, dass das höchste Bit 1 für n == 1 ist, wurde ein Benchmarking von mehr als 80% schneller durchgeführt. Bei der Hälfte der zufällig ausgewählten Zahlen im 63-Bit-Raum ist jedoch das 63. Bit gesetzt!

Bei der Eingabe 0x3FFFFFFFFFFFFFFF ist die Entscheidungsbaumversion ziemlich viel schneller als bei 1 und zeigt sich als 1120% schneller (12,2-mal) als der Bit-Shifter.

Ich werde den Entscheidungsbaum auch mit den GCC-Buildins vergleichen und auch eine Mischung von Eingaben versuchen, anstatt sie mit derselben Zahl zu wiederholen. Möglicherweise gibt es eine Vorhersage für bleibende Zweige und möglicherweise einige unrealistische Caching-Szenarien, die die Wiederholung künstlich beschleunigen.

Wie wäre es mit

int highest_bit(unsigned int a) {
    int count;
    std::frexp(a, &count);
    return count - 1;
}

?

unsigned int
msb32(register unsigned int x)
{
        x |= (x >> 1);
        x |= (x >> 2);
        x |= (x >> 4);
        x |= (x >> 8);
        x |= (x >> 16);
        return(x & ~(x >> 1));
}

1 Register, 13 Anweisungen. Ob Sie es glauben oder nicht, dies ist normalerweise schneller als der oben erwähnte BSR-Befehl, der in linearer Zeit arbeitet. Dies ist die logarithmische Zeit.

Von http://aggregate.org/MAGIC/#Most%20Significant%201%20Bit

Hier sind einige (einfache) Benchmarks der derzeit auf dieser Seite angegebenen Algorithmen ...

Die Algorithmen wurden nicht für alle Eingaben von int ohne Vorzeichen getestet. also überprüfe das zuerst, bevor du blind etwas benutzt;)

Auf meinem Computer funktionieren clz (__builtin_clz) und asm am besten. asm scheint noch schneller als clz ... aber es könnte an dem einfachen Benchmark liegen ...

//////// go.c ///////////////////////////////
// compile with:  gcc go.c -o go -lm
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/***************** math ********************/

#define POS_OF_HIGHESTBITmath(a) /* 0th position is the Least-Signif-Bit */    \
  ((unsigned) log2(a))         /* thus: do not use if a <= 0 */  

#define NUM_OF_HIGHESTBITmath(a) ((a)               \
                  ? (1U << POS_OF_HIGHESTBITmath(a))    \
                  : 0)



/***************** clz ********************/

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)


/***************** i2f ********************/

double FF;
#define POS_OF_HIGHESTBITi2f(a) (FF = (double)(ui|1), ((*(1+(unsigned*)&FF))>>20)-1023)


#define NUM_OF_HIGHESTBITi2f(a) ((a)                    \
                 ? (1U << POS_OF_HIGHESTBITi2f(a))  \
                 : 0)




/***************** asm ********************/

unsigned OUT;
#define POS_OF_HIGHESTBITasm(a) (({asm("bsrl %1,%0" : "=r"(OUT) : "r"(a));}), OUT)

#define NUM_OF_HIGHESTBITasm(a) ((a)                    \
                 ? (1U << POS_OF_HIGHESTBITasm(a))  \
                 : 0)




/***************** bitshift1 ********************/

#define NUM_OF_HIGHESTBITbitshift1(a) (({   \
  OUT = a;                  \
  OUT |= (OUT >> 1);                \
  OUT |= (OUT >> 2);                \
  OUT |= (OUT >> 4);                \
  OUT |= (OUT >> 8);                \
  OUT |= (OUT >> 16);               \
      }), (OUT & ~(OUT >> 1)))          \



/***************** bitshift2 ********************/
int POS[32] = {0, 1, 28, 2, 29, 14, 24, 3,
             30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
             16, 7, 26, 12, 18, 6, 11, 5, 10, 9};

#define POS_OF_HIGHESTBITbitshift2(a) (({   \
  OUT = a;                  \
  OUT |= OUT >> 1;              \
  OUT |= OUT >> 2;              \
  OUT |= OUT >> 4;              \
  OUT |= OUT >> 8;              \
  OUT |= OUT >> 16;             \
  OUT = (OUT >> 1) + 1;             \
      }), POS[(OUT * 0x077CB531UL) >> 27])

#define NUM_OF_HIGHESTBITbitshift2(a) ((a)              \
                       ? (1U << POS_OF_HIGHESTBITbitshift2(a)) \
                       : 0)



#define LOOPS 100000000U

int main()
{
  time_t start, end;
  unsigned ui;
  unsigned n;

  /********* Checking the first few unsigned values (you'll need to check all if you want to use an algorithm here) **************/
  printf("math\n");
  for (ui = 0U; ui < 18; ++ui)
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITmath(ui));

  printf("\n\n");

  printf("clz\n");
  for (ui = 0U; ui < 18U; ++ui)
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITclz(ui));

  printf("\n\n");

  printf("i2f\n");
  for (ui = 0U; ui < 18U; ++ui)
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITi2f(ui));

  printf("\n\n");

  printf("asm\n");
  for (ui = 0U; ui < 18U; ++ui) {
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITasm(ui));
  }

  printf("\n\n");

  printf("bitshift1\n");
  for (ui = 0U; ui < 18U; ++ui) {
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift1(ui));
  }

  printf("\n\n");

  printf("bitshift2\n");
  for (ui = 0U; ui < 18U; ++ui) {
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift2(ui));
  }

  printf("\n\nPlease wait...\n\n");


  /************************* Simple clock() benchmark ******************/
  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITmath(ui);
  end = clock();
  printf("math:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITclz(ui);
  end = clock();
  printf("clz:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITi2f(ui);
  end = clock();
  printf("i2f:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITasm(ui);
  end = clock();
  printf("asm:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITbitshift1(ui);
  end = clock();
  printf("bitshift1:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITbitshift2(ui);
  end = clock();
  printf("bitshift2\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  printf("\nThe lower, the better. Take note that a negative exponent is good! ;)\n");

  return EXIT_SUCCESS;
}

Obwohl ich diese Methode wahrscheinlich nur verwenden würde, wenn ich unbedingt die bestmögliche Leistung benötigen würde (z. B. um eine Art Brettspiel-KI mit Bitboards zu schreiben), ist die effizienteste Lösung die Verwendung von Inline-ASM. Im Abschnitt Optimierungen dieses Blogposts finden Sie Code mit einer Erklärung.

[...] bsrlberechnet die Assemblierungsanweisung die Position des höchstwertigen Bits. Wir könnten also diese asmAussage verwenden:

asm ("bsrl %1, %0" 
     : "=r" (position) 
     : "r" (number));

Ich brauchte eine Routine, um dies zu tun, und bevor ich das Web durchsuchte (und diese Seite fand), fand ich meine eigene Lösung, die auf einer binären Suche basierte. Obwohl ich sicher bin, dass jemand dies schon einmal getan hat! Es läuft in konstanter Zeit und kann schneller sein als die "offensichtliche" Lösung, obwohl ich keine großen Ansprüche stelle, sondern es nur aus Interesse poste.

int highest_bit(unsigned int a) {
  static const unsigned int maskv[] = { 0xffff, 0xff, 0xf, 0x3, 0x1 };
  const unsigned int *mask = maskv;
  int l, h;

  if (a == 0) return -1;

  l = 0;
  h = 32;

  do {
    int m = l + (h - l) / 2;

    if ((a >> m) != 0) l = m;
    else if ((a & (*mask << l)) != 0) h = m;

    mask++;
  } while (l < h - 1);

  return l;
}

Das ist eine Art binäre Suche, die mit allen Arten von (vorzeichenlosen!) Ganzzahltypen funktioniert

#include <climits>
#define UINT (unsigned int)
#define UINT_BIT (CHAR_BIT*sizeof(UINT))

int msb(UINT x)
{
    if(0 == x)
        return -1;

    int c = 0;

    for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
    if(static_cast<UINT>(x >> i))
    {
        x >>= i;
        c |= i;
    }

    return c;
}

zu vervollständigen:

#include <climits>
#define UINT unsigned int
#define UINT_BIT (CHAR_BIT*sizeof(UINT))

int lsb(UINT x)
{
    if(0 == x)
        return -1;

    int c = UINT_BIT-1;

    for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
    if(static_cast<UINT>(x << i))
    {
        x <<= i;
        c ^= i;
    }

    return c;
}

Einige zu komplexe Antworten hier. Die Debruin-Technik sollte nur verwendet werden, wenn der Eingang bereits eine Zweierpotenz ist, andernfalls gibt es einen besseren Weg. Bei einer Leistung von 2 Eingängen ist Debruin der absolut schnellste, sogar schneller als _BitScanReverseauf jedem von mir getesteten Prozessor. Im allgemeinen Fall jedoch_BitScanReverse (oder wie auch immer das Intrinsic in Ihrem Compiler heißt) ist es jedoch am schnellsten (auf bestimmten CPUs kann es jedoch mikrocodiert werden).

Wenn die intrinsische Funktion keine Option ist, finden Sie hier eine optimale Softwarelösung für die Verarbeitung allgemeiner Eingaben.

u8  inline log2 (u32 val)  {
    u8  k = 0;
    if (val > 0x0000FFFFu) { val >>= 16; k  = 16; }
    if (val > 0x000000FFu) { val >>= 8;  k |= 8;  }
    if (val > 0x0000000Fu) { val >>= 4;  k |= 4;  }
    if (val > 0x00000003u) { val >>= 2;  k |= 2;  }
    k |= (val & 2) >> 1;
    return k;
}

Beachten Sie, dass diese Version im Gegensatz zu den meisten anderen Antworten am Ende keine Debruin-Suche erfordert. Es berechnet die Position an Ort und Stelle.

Tabellen können jedoch vorzuziehen sein, wenn Sie sie wiederholt genug aufrufen, wird das Risiko eines Cache-Fehlers durch die Beschleunigung einer Tabelle verdunkelt.

u8 kTableLog2[256] = {
0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};

u8 log2_table(u32 val)  {
    u8  k = 0;
    if (val > 0x0000FFFFuL) { val >>= 16; k  = 16; }
    if (val > 0x000000FFuL) { val >>=  8; k |=  8; }
    k |= kTableLog2[val]; // precompute the Log2 of the low byte

    return k;
}

Dies sollte den höchsten Durchsatz aller hier angegebenen Softwareantworten liefern. Wenn Sie ihn jedoch nur gelegentlich aufrufen, bevorzugen Sie eine tabellenfreie Lösung wie mein erstes Snippet.

Wie die obigen Antworten zeigen, gibt es eine Reihe von Möglichkeiten, das höchstwertige Bit zu bestimmen. Wie bereits erwähnt, sind die Methoden jedoch wahrscheinlich nur für 32-Bit- oder 64-Bit-Register eindeutig. Die Seite stanford.edu bithacks bietet Lösungen, die sowohl für 32- Bit- als auch für 64-Bit-Computer geeignet sind . Mit ein wenig Arbeit können sie kombiniert werden, um einen soliden architekturübergreifenden Ansatz für den Erhalt des MSB bereitzustellen. Die Lösung, die ich bei der Kompilierung / Arbeit auf 64- und 32-Bit-Computern gefunden habe, war:

#if defined(__LP64__) || defined(_LP64)
# define BUILD_64   1
#endif

#include <stdio.h>
#include <stdint.h>  /* for uint32_t */

/* CHAR_BIT  (or include limits.h) */
#ifndef CHAR_BIT
#define CHAR_BIT  8
#endif  /* CHAR_BIT */

/* 
 * Find the log base 2 of an integer with the MSB N set in O(N)
 * operations. (on 64bit & 32bit architectures)
 */
int
getmsb (uint32_t word)
{
    int r = 0;
    if (word < 1)
        return 0;
#ifdef BUILD_64
    union { uint32_t u[2]; double d; } t;  // temp
    t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
    t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = word;
    t.d -= 4503599627370496.0;
    r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;
#else
    while (word >>= 1)
    {
        r++;
    }
#endif  /* BUILD_64 */
    return r;
}

Eine Version in C mit sukzessiver Approximation:

unsigned int getMsb(unsigned int n)
{
  unsigned int msb  = sizeof(n) * 4;
  unsigned int step = msb;
  while (step > 1)
 {
    step /=2;
    if (n>>msb)
     msb += step;
   else
     msb -= step;
 }
  if (n>>msb)
    msb++;
  return (msb - 1);
}

Vorteil: Die Laufzeit ist unabhängig von der angegebenen Anzahl konstant, da die Anzahl der Schleifen immer gleich ist. (4 Schleifen bei Verwendung von "unsigned int")

Ich weiß, dass diese Frage sehr alt ist, aber nachdem ich selbst eine msb () -Funktion implementiert habe, stellte ich fest, dass die meisten hier und auf anderen Websites vorgestellten Lösungen nicht unbedingt die effizientesten sind - zumindest für meine persönliche Definition von Effizienz (siehe auch Update unten) ). Hier ist der Grund:

Die meisten Lösungen (insbesondere diejenigen, die ein binäres Suchschema oder den naiven Ansatz verwenden, bei dem ein linearer Scan von rechts nach links durchgeführt wird) scheinen die Tatsache zu vernachlässigen, dass es für beliebige binäre Zahlen nicht viele gibt, die mit einer sehr langen Folge von beginnen Nullen. Tatsächlich beginnt für jede Bitbreite die Hälfte aller Ganzzahlen mit einer 1 und ein Viertel von ihnen mit 01 . Sehen Sie, wo ich hinkomme? Mein Argument ist, dass ein linearer Scan von der höchstwertigen Bitposition bis zur niedrigstwertigen (von links nach rechts) nicht so "linear" ist, wie es auf den ersten Blick aussehen könnte.

Es kann ¹ gezeigt werden , dass für jede Bitbreite die durchschnittliche Anzahl von Bits, die getestet werden müssen, höchstens 2 beträgt. Dies führt zu einer amortisierten Zeitkomplexität von O (1) in Bezug auf die Anzahl von Bits (!). .

Natürlich ist der schlimmste Fall immer noch O (n) , schlimmer als der O (log (n)), den Sie bei binärsuchähnlichen Ansätzen erhalten, aber da es so wenige schlimmste Fälle gibt, sind sie für die meisten Anwendungen vernachlässigbar ( Update) : nicht ganz: Es mag wenige geben, aber sie können mit hoher Wahrscheinlichkeit auftreten - siehe Update unten).

Hier ist der "naive" Ansatz, den ich mir ausgedacht habe und der zumindest auf meinem Computer die meisten anderen Ansätze übertrifft (binäre Suchschemata für 32-Bit-Ints erfordern immer log ₂ (32) = 5 Schritte, während dieser alberne Algorithmus weniger erfordert als durchschnittlich 2) - Entschuldigung, dass dies C ++ und nicht reines C ist:

template <typename T>
auto msb(T n) -> int
{
    static_assert(std::is_integral<T>::value && !std::is_signed<T>::value,
        "msb<T>(): T must be an unsigned integral type.");

    for (T i = std::numeric_limits<T>::digits - 1, mask = 1 << i; i >= 0; --i, mask >>= 1)
    {
        if ((n & mask) != 0)
            return i;
    }

    return 0;
}

Update : Während das, was ich hier geschrieben habe, für beliebige Ganzzahlenvollkommen zutrifft, bei denen jede Kombination von Bits gleich wahrscheinlich ist (mein Geschwindigkeitstest hat einfach gemessen, wie lange es gedauert hat, das MSB für alle 32-Bit-Ganzzahlenzu bestimmen), für reale Ganzzahlen, z Welche solche Funktion aufgerufen wird, folgt normalerweise einem anderen Muster: In meinem Code wird diese Funktion beispielsweise verwendet, um zu bestimmen, ob eine Objektgröße eine Potenz von 2 ist, oder um die nächste Potenz von 2 größer oder gleich einer zu finden Objektgröße . Ich vermute, dass die meisten Anwendungen, die das MSB verwenden, Zahlen enthalten, die viel kleiner sind als die maximale Zahl, die eine Ganzzahl darstellen kann (Objektgrößen verwenden selten alle Bits in einem size_t). In diesem Fall ist meine Lösung tatsächlich schlechter als ein binärer Suchansatz. Letzterer sollte daher wahrscheinlich bevorzugt werden, obwohl meine Lösung alle Ganzzahlen schneller durchläuft .
TL; DR: Reale Ganzzahlen werden wahrscheinlich eine Tendenz zum schlimmsten Fall dieses einfachen Algorithmus haben, was die Leistung am Ende verschlechtern wird - trotz der Tatsache, dass O (1) für wirklich beliebige Ganzzahlen amortisiert ist .

¹ Das Argument lautet wie folgt (grober Entwurf): Sei n die Anzahl der Bits (Bitbreite). Es gibt insgesamt 2 ⁿ ganze Zahlen, die mit n Bits dargestellt werden können. Es gibt 2 ^{n - 1} Ganzzahlen, die mit einer 1 beginnen (die erste 1 ist fest, die verbleibenden n - 1 Bits können alles sein). Diese ganzen Zahlen erfordern nur eine Interaktion der Schleife, um das MSB zu bestimmen. Ferner gibt es 2 ^{n - 2} Ganzzahlen, die mit 01 beginnen und 2 Iterationen erfordern, 2 ^{n - 3} Ganzzahlen, die mit 001 beginnen , 3 Iterationen erfordern und so weiter.

Wenn wir alle erforderlichen Iterationen für alle möglichen Ganzzahlen zusammenfassen und durch 2 ⁿ , die Gesamtzahl der Ganzzahlen, dividieren , erhalten wir die durchschnittliche Anzahl der Iterationen, die zur Bestimmung des MSB für n- Bit-Ganzzahlen erforderlich sind:

(1 * 2 ^{n - 1} + 2 * 2 ^{n - 2} + 3 * 2 ^{n - 3} + ... + n) / 2 ⁿ

Diese Reihe von durchschnittlichen Iterationen ist tatsächlich konvergent und hat eine Grenze von 2 für n gegen unendlich

Somit hat der naive Links-Rechts-Algorithmus tatsächlich eine amortisierte konstante Zeitkomplexität von O (1) für eine beliebige Anzahl von Bits.

c99hat uns gegeben log2. Dadurch entfallen alle speziellen Saucenimplementierungen, log2die Sie auf dieser Seite sehen. Sie können die log2Implementierung des Standards folgendermaßen verwenden :

const auto n = 13UL;
const auto Index = (unsigned long)log2(n);

printf("MSB is: %u\n", Index); // Prints 3 (zero offset)

Ein nvon 0ULmuss auch geschützt werden, weil:

-∞ wird zurückgegeben und FE_DIVBYZERO wird ausgelöst

Ich habe ein Beispiel mit diesem Scheck geschrieben , dass willkürlich Sätze hier: https://ideone.com/u26vsiIndexULONG_MAX

Das Visual-StudioDie Folge von Ephemients gcc ist die einzige Antwort :

const auto n = 13UL;
unsigned long Index;

_BitScanReverse(&Index, n);
printf("MSB is: %u\n", Index); // Prints 3 (zero offset)

Die Dokumentation für_BitScanReverse Zustände Indexlautet:

Wird mit der Bitposition des ersten gesetzten gesetzten Bits (1) geladen

In der Praxis habe ich festgestellt , dass , wenn nist , 0ULdass Indexfestgelegt ist0UL genauso wie es für eine wäre, nvon 1UL. Aber das einzige in der Dokumentation garantiert , was im Fall eines nvon 0UList , dass die Rückkehr ist:

0, wenn keine gesetzten Bits gefunden wurden

Ähnlich wie bei der oben beschriebenen bevorzugten log2Implementierung sollte daher die Rückgabe überprüft werden, indem Indexin diesem Fall ein markierter Wert festgelegt wird. Ich habe hier noch einmal ein Beispiel für die Verwendung ULONG_MAXdieses Flag-Werts geschrieben: http://rextester.com/GCU61409

Denken Sie an bitweise Operatoren.

Ich habe die Frage beim ersten Mal falsch verstanden. Sie sollten ein int mit dem am weitesten links stehenden Bit erzeugen (die anderen Nullen). Angenommen, cmp ist auf diesen Wert eingestellt:

position = sizeof(int)*8
while(!(n & cmp)){ 
   n <<=1;
   position--;
}

Wenn man Joshs Benchmark erweitert, kann man das clz wie folgt verbessern

/***************** clz2 ********************/

#define NUM_OF_HIGHESTBITclz2(a) ((a)                              \
                  ? (((1U) << (sizeof(unsigned)*8-1)) >> __builtin_clz(a)) \
                  : 0)

Zum asm: Beachten Sie, dass es bsr und bsrl gibt (dies ist die "lange" Version). das normale könnte etwas schneller sein.

Beachten Sie, dass Sie versuchen, die Ganzzahl log2 einer Ganzzahl zu berechnen.

#include <stdio.h>
#include <stdlib.h>

unsigned int
Log2(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1; int k=0;
    for( step = 1; step < bits; ) {
        n |= (n >> step);
        step *= 2; ++k;
    }
    //printf("%ld %ld\n",x, (x - (n >> 1)) );
    return(x - (n >> 1));
}

Beachten Sie, dass Sie versuchen können, mehr als 1 Bit gleichzeitig zu suchen.

unsigned int
Log2_a(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1;
    int step2 = 0;
    //observe that you can move 8 bits at a time, and there is a pattern...
    //if( x>1<<step2+8 ) { step2+=8;
        //if( x>1<<step2+8 ) { step2+=8;
            //if( x>1<<step2+8 ) { step2+=8;
            //}
        //}
    //}
    for( step2=0; x>1L<<step2+8; ) {
        step2+=8;
    }
    //printf("step2 %d\n",step2);
    for( step = 0; x>1L<<(step+step2); ) {
        step+=1;
        //printf("step %d\n",step+step2);
    }
    printf("log2(%ld) %d\n",x,step+step2);
    return(step+step2);
}

Dieser Ansatz verwendet eine binäre Suche

unsigned int
Log2_b(unsigned long x)
{
    unsigned long n = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int hbit = bits-1;
    unsigned int lbit = 0;
    unsigned long guess = bits/2;
    int found = 0;

    while ( hbit-lbit>1 ) {
        //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        //when value between guess..lbit
        if( (x<=(1L<<guess)) ) {
           //printf("%ld < 1<<%d %ld\n",x,guess,1L<<guess);
            hbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
        //when value between hbit..guess
        //else
        if( (x>(1L<<guess)) ) {
            //printf("%ld > 1<<%d %ld\n",x,guess,1L<<guess);
            lbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
    }
    if( (x>(1L<<guess)) ) ++guess;
    printf("log2(x%ld)=r%d\n",x,guess);
    return(guess);
}

Eine andere binäre Suchmethode, vielleicht besser lesbar,

unsigned int
Log2_c(unsigned long x)
{
    unsigned long v = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int step = bits;
    unsigned int res = 0;
    for( step = bits/2; step>0; )
    {
        //printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step);
        while ( v>>step ) {
            v>>=step;
            res+=step;
            //printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v);
        }
        step /= 2;
    }
    if( (x>(1L<<res)) ) ++res;
    printf("log2(x%ld)=r%ld\n",x,res);
    return(res);
}

Und weil Sie diese testen möchten,

int main()
{
    unsigned long int x = 3;
    for( x=2; x<1000000000; x*=2 ) {
        //printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1));
        printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1));
        printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1));
        printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1));
    }
    return(0);
}

Dies einzufügen, da es sich um einen „weiteren“ Ansatz handelt, scheint sich von den bereits gegebenen zu unterscheiden.

Gibt -1if x==0andernfalls zurück floor( log2(x)) (maximales Ergebnis 31)

Reduzieren Sie das 32- auf 4-Bit-Problem und verwenden Sie dann eine Tabelle. Vielleicht unelegant, aber pragmatisch.

Dies ist, was ich verwende, wenn ich es __builtin_clzaufgrund von Portabilitätsproblemen nicht verwenden möchte .

Um es kompakter zu machen, könnte man stattdessen eine Schleife zum Reduzieren verwenden und jedes Mal 4 zu r hinzufügen, maximal 7 Iterationen. Oder ein Hybrid wie (für 64 Bit): Schleife, um auf 8 zu reduzieren, Test, um auf 4 zu reduzieren.

int log2floor( unsigned x ){
   static const signed char wtab[16] = {-1,0,1,1, 2,2,2,2, 3,3,3,3,3,3,3,3};
   int r = 0;
   unsigned xk = x >> 16;
   if( xk != 0 ){
       r = 16;
       x = xk;
   }
   // x is 0 .. 0xFFFF
   xk = x >> 8;
   if( xk != 0){
       r += 8;
       x = xk;
   }
   // x is 0 .. 0xFF
   xk = x >> 4;
   if( xk != 0){
       r += 4;
       x = xk;
   }
   // now x is 0..15; x=0 only if originally zero.
   return r + wtab[x];
}

Woaw, das waren viele Antworten. Es tut mir nicht leid, eine alte Frage beantwortet zu haben.

int result = 0;//could be a char or int8_t instead
if(value){//this assumes the value is 64bit
    if(0xFFFFFFFF00000000&value){  value>>=(1<<5); result|=(1<<5);  }//if it is 32bit then remove this line
    if(0x00000000FFFF0000&value){  value>>=(1<<4); result|=(1<<4);  }//and remove the 32msb
    if(0x000000000000FF00&value){  value>>=(1<<3); result|=(1<<3);  }
    if(0x00000000000000F0&value){  value>>=(1<<2); result|=(1<<2);  }
    if(0x000000000000000C&value){  value>>=(1<<1); result|=(1<<1);  }
    if(0x0000000000000002&value){  result|=(1<<0);  }
}else{
  result=-1;
}

Diese Antwort ist einer anderen Antwort ziemlich ähnlich ... na ja.

Der Code:

    // x>=1;
    unsigned func(unsigned x) {
    double d = x ;
    int p= (*reinterpret_cast<long long*>(&d) >> 52) - 1023;
    printf( "The left-most non zero bit of %d is bit %d\n", x, p);
    }

Oder rufen Sie den ganzzahligen Teil des FPU-Befehls FYL2X (Y * Log2 X) ab, indem Sie Y = 1 setzen

Ein anderes Poster lieferte eine Nachschlagetabelle mit einer byteweiten Nachschlagetabelle. Für den Fall, dass Sie etwas mehr Leistung erzielen möchten (auf Kosten von 32 KB Speicher anstelle von nur 256 Nachschlageinträgen), finden Sie hier eine Lösung mit einer 15-Bit-Nachschlagetabelle in C # 7 für .NET .

Der interessante Teil ist die Initialisierung der Tabelle. Da es sich um einen relativ kleinen Block handelt, den wir für die Lebensdauer des Prozesses benötigen, ordne ich dafür nicht verwalteten Speicher zu Marshal.AllocHGlobal. Wie Sie sehen können, ist das gesamte Beispiel für maximale Leistung als nativ geschrieben:

readonly static byte[] msb_tab_15;

// Initialize a table of 32768 bytes with the bit position (counting from LSB=0)
// of the highest 'set' (non-zero) bit of its corresponding 16-bit index value.
// The table is compressed by half, so use (value >> 1) for indexing.
static MyStaticInit()
{
    var p = new byte[0x8000];

    for (byte n = 0; n < 16; n++)
        for (int c = (1 << n) >> 1, i = 0; i < c; i++)
            p[c + i] = n;

    msb_tab_15 = p;
}

Die Tabelle erfordert eine einmalige Initialisierung über den obigen Code. Es ist schreibgeschützt, sodass eine einzelne globale Kopie für den gleichzeitigen Zugriff freigegeben werden kann. Mit dieser Tabelle können Sie sehen schnell die ganze Zahl log ₂ , das istwas wir hier suchen, für alle die verschiedenen ganzzahligen Breiten (8, 16, 32 und 64 Bit).

Beachten Sie, dass der Tabelleneintrag für 0, die einzige Ganzzahl, für die der Begriff 'höchstes gesetztes Bit' undefiniert ist, den Wert erhält-1 . Diese Unterscheidung ist für die ordnungsgemäße Behandlung von 0-wertigen oberen Wörtern im folgenden Code erforderlich. Hier ist ohne weiteres der Code für jedes der verschiedenen ganzzahligen Grundelemente:

ulong (64-Bit) Version

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(this ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 0x40) - 1;      // handles cases v==0 and MSB==63

    int j = /**/ (int)((0xFFFFFFFFU - v /****/) >> 58) & 0x20;
    j |= /*****/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10;
    return j + msb_tab_15[v >> (j + 1)];
}

uint (32-Bit) Version

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(uint v)
{
    if ((int)v <= 0)
        return (int)((v >> 26) & 0x20) - 1;     // handles cases v==0 and MSB==31

    int j = (int)((0x0000FFFFU - v) >> 27) & 0x10;
    return j + msb_tab_15[v >> (j + 1)];
}

Verschiedene Überladungen für die oben genannten

public static int HighestOne(long v) => HighestOne((ulong)v);
public static int HighestOne(int v) => HighestOne((uint)v);
public static int HighestOne(ushort v) => msb_tab_15[v >> 1];
public static int HighestOne(short v) => msb_tab_15[(ushort)v >> 1];
public static int HighestOne(char ch) => msb_tab_15[ch >> 1];
public static int HighestOne(sbyte v) => msb_tab_15[(byte)v >> 1];
public static int HighestOne(byte v) => msb_tab_15[v >> 1];

Dies ist eine vollständige, funktionierende Lösung, die die beste Leistung unter .NET 4.7.2 für zahlreiche Alternativen darstellt, die ich mit einem speziellen Leistungstest-Kabelbaum verglichen habe. Einige davon sind unten aufgeführt. Die Testparameter waren eine gleichmäßige Dichte aller 65-Bit-Positionen, dh 0 ... 31/63 plus Wert 0(was das Ergebnis -1 ergibt). Die Bits unterhalb der Zielindexposition wurden zufällig gefüllt. Die Tests waren nur x64 , Release-Modus, mit aktivierten JIT-Optimierungen.

Das ist das Ende meiner formellen Antwort hier; Im Folgenden finden Sie einige gelegentliche Hinweise und Links zum Quellcode für alternative Testkandidaten, die mit den von mir durchgeführten Tests verknüpft sind, um die Leistung und Richtigkeit des obigen Codes zu überprüfen.

Die oben bereitgestellte Version, die als Tab16A codiert wurde, war über viele Läufe ein konstanter Gewinner. Diese verschiedenen Kandidaten in aktiver Arbeits- / Arbeitsform finden Sie hier , hier und hier .

 1 Kandidaten.HighestOne_Tab16A 622,496
 2 Kandidaten.HighestOne_Tab16C 628,234
 3 Kandidaten.HighestOne_Tab8A 649,146
 4 Kandidaten.HighestOne_Tab8B 656.847
 5 Kandidaten.HighestOne_Tab16B 657,147
 6 Kandidaten.HighestOne_Tab16D 659.650
 7 _highest_one_bit_UNMANAGED.HighestOne_U 702.900
 8 de_Bruijn.IndexOfMSB 709,672
 9 _old_2.HighestOne_Old2 715.810
10 _test_A.HighestOne8 757,188
11 _old_1.HighestOne_Old1 757,925
12 _test_A.HighestOne5 (unsicher) 760,387
13 _test_B.HighestOne8 (unsicher) 763.904
14 _test_A.HighestOne3 (unsicher) 766.433
15 _test_A.HighestOne1 (unsicher) 767.321
16 _test_A.HighestOne4 (unsicher) 771.702
17 _test_B.HighestOne2 (unsicher) 772,136
18 _test_B.HighestOne1 (unsicher) 772.527
19 _test_B.HighestOne3 (unsicher) 774,140
20 _test_A.HighestOne7 (unsicher) 774.581
21 _test_B.HighestOne7 (unsicher) 775.463
22 _test_A.HighestOne2 (unsicher) 776.865
23 Kandidaten.HighestOne_NoTab 777.698
24 _test_B.HighestOne6 (unsicher) 779.481
25 _test_A.HighestOne6 (unsicher) 781.553
26 _test_B.HighestOne4 (unsicher) 785.504
27 _test_B.HighestOne5 (unsicher) 789.797
28 _test_A.HighestOne0 (unsicher) 809.566
29 _test_B.HighestOne0 (unsicher) 814.990
30 _highest_one_bit.HighestOne 824.345
30 _bitarray_ext.RtlFindMostSignificantBit 894,069
31 Kandidaten.HighestOne_Naive 898.865

Bemerkenswert ist, dass die schreckliche Leistung von ntdll.dll!RtlFindMostSignificantBitvia P / Invoke:

[DllImport("ntdll.dll"), SuppressUnmanagedCodeSecurity, SecuritySafeCritical]
public static extern int RtlFindMostSignificantBit(ulong ul);

Es ist wirklich schade, denn hier ist die gesamte eigentliche Funktion:

    RtlFindMostSignificantBit:
        bsr rdx, rcx  
        mov eax,0FFFFFFFFh  
        movzx ecx, dl  
        cmovne      eax,ecx  
        ret

Ich kann mir nicht vorstellen, dass die schlechte Leistung von diesen fünf Zeilen herrührt, daher müssen die Strafen für den verwalteten / nativen Übergang schuld sein. Ich war auch überrascht, dass die Tests die shortdirekten Nachschlagetabellen mit 32 KB (und 64 KB) (16 Bit) gegenüber den Nachschlagetabellen mit 128 Byte (und 256 Byte) byte(8 Bit) wirklich bevorzugten . Ich dachte, das Folgende wäre mit den 16-Bit-Lookups wettbewerbsfähiger, aber letztere übertrafen dies durchweg:

public static int HighestOne_Tab8A(ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 64) - 1;

    int j;
    j =  /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32;
    j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16;
    j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8;
    return j + msb_tab_8[v >> j];
}

Das Letzte, worauf ich hinweisen werde, ist, dass ich ziemlich schockiert war, dass meine deBruijn-Methode nicht besser abgeschnitten hat. Dies ist die Methode, die ich zuvor allgegenwärtig angewendet hatte:

const ulong N_bsf64 = 0x07EDD5E59A4E28C2,
            N_bsr64 = 0x03F79D71B4CB0A89;

readonly public static sbyte[]
bsf64 =
{
    63,  0, 58,  1, 59, 47, 53,  2, 60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12, 44, 24, 15,  8, 23,  7,  6,  5,
},
bsr64 =
{
     0, 47,  1, 56, 48, 27,  2, 60, 57, 49, 41, 37, 28, 16,  3, 61,
    54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11,  4, 62,
    46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
    25, 39, 14, 33, 19, 30,  9, 24, 13, 18,  8, 12,  7,  6,  5, 63,
};

public static int IndexOfLSB(ulong v) =>
    v != 0 ? bsf64[((v & (ulong)-(long)v) * N_bsf64) >> 58] : -1;

public static int IndexOfMSB(ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 64) - 1;

    v |= v >> 1; v |= v >> 2;  v |= v >> 4;   // does anybody know a better
    v |= v >> 8; v |= v >> 16; v |= v >> 32;  // way than these 12 ops?
    return bsr64[(v * N_bsr64) >> 58];
}