wake-up-neo.com

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 ich möchte die Position des höchstwertigen Bits kennen (dh, wenn das niedrigstwertige Bit rechts ist, möchte ich die Position des am weitesten links liegenden Bits, das eine 1 ist) kennen. 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 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?

Edit: Was ist mit einer Lösung, die sowohl für 32- als auch für 64-Bit-Architekturen funktioniert?.

102
Zxaos

GCC hat :

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

 - Built-in-Funktion: int __builtin_clzl (ohne Vorzeichen lang) 
 Ä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 effizientes für Ihre aktuelle Plattform übersetzt werden, ob es sich dabei um einen dieser ausgefallenen Bit-Twiddling-Algorithmen oder um eine einzelne Anweisung handelt.


Ein nützlicher Trick, wenn Ihre Eingabe kann Null sein kann, ist __builtin_clz(x | 1): Das unbedingte Setzen des Low-Bits ohne Ändern anderer Werte führt zu der Ausgabe von 0 für x=0, ohne die Ausgabe für andere Eingaben zu ändern.

Um dies zu vermeiden, sind andere plattformspezifische Intrinsics wie ARM GCCs __clz (kein Header erforderlich) oder x86s _lzcnt_u32 auf CPUs erforderlich, die die Anweisung lzcnt unterstützen. (Beachten Sie, dass lzcnt auf älteren CPUs als bsr dekodiert wird, anstatt zu stören, was 31-lzcnt für Nicht-Null-Eingänge ergibt.)

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

(Das "undefinierte Ergebnis" ist nicht C Undefined Behavior, sondern ein Wert, der nicht definiert ist. Es ist tatsächlich das, was sich im Zielregister befand, als der Befehl ausgeführt wurde. AMD dokumentiert dies, Intel tut dies nicht, aber Intel CPUs implementieren dieses Verhalten Aber es ist nicht was auch immer in der C-Variablen war, die Sie zuweisen, normalerweise funktionieren die Dinge nicht, wenn gcc C in asm verwandelt. Siehe auch Warum ist es wichtig, die "Ausgabeabhängigkeit" von LZCNT zu ändern? )

53
ephemient

Angenommen, Sie sind auf x86 und spielen für einen kleinen Inline-Assembler. Intel bietet eine BSR -Anweisung ("bit scan reverse"). Es ist fast auf einige x86s (auf anderen Mikrocodes). Aus dem Handbuch:

Durchsucht den Quelloperanden nach der höchstwertigen Menge Bit (1 Bit). Wenn eine höchst signifikante 1 Bit gefunden wird, wird sein Bitindex gespeichert im Zieloperanden. Der Quelloperand kann ein .__ sein. Register oder einen Speicherplatz; das Zieloperand ist ein Register. Das Bitindex ist ein vorzeichenloser Versatz von Bit 0 des Quelloperanden. Wenn der Inhaltsquellenoperand ist 0, die Inhalt des Zieloperanden ist nicht definiert.

(Wenn Sie PowerPC verwenden, gibt es eine ähnliche cntlz-Anweisung ("count führende Nullen").)

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 (Abschnitt 9.4) zeigt, dass es wesentlich schneller ist als das Schleifen von Code.

40
timday

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, wenn Sie jedoch feststellen, dass der Code wiederholt um ein Bit nach rechts verschoben wird, bis das Bit ganz links verschoben wurde (beachten Sie, dass C jeden Wert ungleich Null als "True" behandelt) und die Zahl zurückgibt von Schichten macht es vollkommen Sinn. Das bedeutet auch, dass es 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, komplexere Variationen. Wenn Sie jedoch wissen, dass Sie mit Zahlen mit vielen führenden Nullen zu tun haben, kann der naive Ansatz eine akzeptable Geschwindigkeit bieten, da die Bitverschiebung in C ziemlich schnell ist und der einfache Algorithmus kein Array indizieren muss.

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.

35
Quinn Taylor

Das 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];
}
15
Protagonist

Das ist so, als würde man eine Art Ganzzahlprotokoll finden. Es gibt kleine Tricks, aber ich habe mein eigenes Werkzeug dafür gemacht. Das Ziel ist natürlich Geschwindigkeit. 

Meine Erkenntnis ist, dass die CPU bereits einen automatischen Bit-Detektor hat, der für die Umwandlung von Ganzzahl in Float verwendet wird! Verwenden Sie das also.

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 aus, der Ihnen sagt, wo sich das Bit befand. Die fantastische Verschiebung und Subtraktion dient dazu, die richtigen Teile aus dem IEEE-Wert zu extrahieren.

Die Verwendung von Schwimmern ist etwas schneller, aber ein Schwimmkörper kann aufgrund der geringeren Genauigkeit nur die ersten 24-Bit-Positionen angeben.


Um dies sicher und ohne undefiniertes Verhalten in C++ oder C durchzuführen, verwenden Sie memcpy anstelle von Zeigerumwandlung für das Type-Punning. Compiler wissen, wie man sie effizient einfügt.

// 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 ab C99 einen union {double d; uint32_t u[2];};. Beachten Sie jedoch, dass Union-Punning in C++ nur von einigen Compilern als Erweiterung unterstützt wird, nicht in ISO C++.


Dies ist normalerweise langsamer als ein plattformspezifischer Befehl für einen Zählbefehl für führende Nullen, aber der tragbare ISO-C hat keine solche Funktion. Einige CPUs verfügen auch nicht über einen Null-Zählbefehl, aber einige von ihnen können Ganzzahlen effizient in double konvertieren. Das Zurückschieben eines FP - Bitmusters auf Integer kann jedoch langsam sein (z. B. erfordert es bei PowerPC ein Laden/Neuladen und verursacht in der Regel ein Stoppen des Ladetreffers).

Dieser Algorithmus kann möglicherweise für SIMD-Implementierungen nützlich sein, da weniger CPUs SIMD lzcnt haben. x86 bekam nur eine solche Anweisung mit AVX512CD

12
SPWorley

Kaz Kylheku hier 

Ich habe zwei Ansätze für mehr als 63 Bit-Nummern (den langen langen Typ auf gcc x86_64) getestet, wobei ich mich vom Zeichenbit entfernte.

(Ich brauche dieses "oberste 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 entrollten Entscheidungsbaum von Hand implementiert, der nur Code mit unmittelbaren Operanden ist. Keine Schleifen, keine Tische.

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

Der spezielle Test der binären Suche für den Fall 0 ist nur 48% schneller als der Entscheidungsbaum, für den kein spezieller Test vorhanden ist.

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;
}

Bei Verwendung von nur -O2 wird der Unterschied größer. Der Entscheidungsbaum ist fast viermal schneller.

Ich habe auch mit dem naiven Bit-Shifting-Code verglichen:

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

Dies ist, wie zu erwarten, nur für kleine Zahlen schnell. Bei der Feststellung, dass das höchste Bit 1 für n == 1 ist, wurde das Benchmarking um mehr als 80% schneller. Die Hälfte der zufällig ausgewählten Zahlen im 63-Bit-Bereich hat jedoch das 63. Bit gesetzt!

Auf dem Eingang 0x3FFFFFFFFFFFFFF ist die Version des Entscheidungsbaums um einiges schneller als auf 1 und zeigt sich, dass sie 1120% schneller (12,2-fach) als der Bitschieber ist.

Ich werde auch den Entscheidungsbaum mit den GCC-eingebauten vergleichen und auch eine Mischung aus Eingaben versuchen, anstatt die gleiche Anzahl zu wiederholen. Es kann eine gewisse Verzweigungsvoraussage und möglicherweise unrealistische Zwischenspeicherungsszenarien geben, die es bei Wiederholungen künstlich schneller machen.

9
Kaz

Wie wäre es mit

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

?

7
Marco Amagliani
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 eine logarithmische Zeit.

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

6
rlbond

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

Die Algorithmen wurden nicht für alle Eingänge von unsigned int getestet. also zuerst das überprüfen, bevor blind etwas benutzt wird;)

Auf meinem Rechner funktionieren clz (__builtin_clz) und asm am besten. asm scheint noch schneller als clz ... aber es könnte am 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;
}
5
Josh

Obwohl ich diese Methode wahrscheinlich nur dann verwenden würde, wenn absolut die bestmögliche Leistung erforderlich wäre (z. B. zum Schreiben einer Art Brettspiel-KI mit Bitboards), ist die effizienteste Lösung die Verwendung von Inline-ASM. Siehe den Abschnitt Optimierungen in diesem Blogbeitrag für Code mit einer Erläuterung.

[...] berechnet die Assembly-Anweisung bsrl die Position des höchstwertigen Bits. Daher könnten wir diese asm-Anweisung verwenden:

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

Ich brauchte eine Routine, um dies zu tun, und bevor ich das Web durchsuchte (und diese Seite gefunden hatte), fand ich meine eigene Lösung basierend auf einer binären Suche. Ich bin mir sicher, dass das schon mal jemand gemacht hat! Es läuft in gleichbleibender Zeit und kann schneller sein als die "offensichtliche" Lösung, obwohl es keine großen Ansprüche gibt.

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;
}
4
dangermouse

Einige zu komplexe Antworten hier. Die Debruin-Technik sollte nur verwendet werden, wenn die Eingabe bereits eine Zweierpotenz ist, ansonsten gibt es einen besseren Weg. Bei einer Eingabe von 2 ist Debruin der absolut schnellste, sogar schneller als _BitScanReverse auf jedem getesteten Prozessor. Im allgemeinen Fall ist _BitScanReverse (oder was auch immer das Intrinsic in Ihrem Compiler genannt wird) am schnellsten (bei bestimmten CPUs kann es jedoch auch Mikrocode sein).

Wenn die intrinsische Funktion keine Option ist, gibt es 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 keine Debruin-Suche am Ende erfordert. Es berechnet die Position an Ort und Stelle.

Tabellen können jedoch vorzuziehen sein. Wenn Sie sie mehrmals wiederholt aufrufen, wird die Gefahr eines Cache-Fehlschlags durch die Beschleunigung einer Tabelle unterdrückt.

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 Software-Antworten erzeugen. Wenn Sie es jedoch nur gelegentlich aufrufen, ziehen Sie eine tabellarische Lösung wie mein erster Snippet vor.

4
VoidStar

das ist eine Art binäre Suche, sie funktioniert mit allen Arten von (vorzeichenlosen!) Integer-Typen

#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;
}

komplett machen:

#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;
}
3

Wie die obigen Antworten zeigen, gibt es mehrere Möglichkeiten, das höchstwertige Bit zu bestimmen. Wie auch ausgeführt wurde, sind die Methoden wahrscheinlich eindeutig für 32-Bit- oder 64-Bit-Register. Die stanford.edu-Seite für Bithacks bietet Lösungen, die sowohl für 32-Bit- als auch für 64-Bit-Computing geeignet sind. Mit ein wenig Arbeit können sie kombiniert werden, um einen soliden, architekturübergreifenden Ansatz zur Erlangung des MSB zu bieten. Die Lösung, auf der ich auf 64- und 32-Bit-Computern kompiliert/gearbeitet 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;
}
3
David C. Rankin

Eine Version in C mit sukzessiver Annäherung:

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.

3
user3177100

c99 hat uns gegeben log2 . Dadurch entfällt die Notwendigkeit aller speziellen log2-Implementierungen, die Sie auf dieser Seite sehen. Sie können die log2-Implementierung 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)

Eine n von 0UL muss ebenfalls geschützt werden, weil:

-∞ wird zurückgegeben und FE_DIVBYZERO wird angehoben

Ich habe ein Beispiel mit dieser Prüfung geschrieben, das willkürlich Index auf ULONG_MAX hier setzt: https://ideone.com/u26vsi


Das visual-studio die Folge von gccs Antwort auf ephemient ist:

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 besagt, dass Index Folgendes ist:

Geladen mit der Bitposition des ersten gefundenen gesetzten Bits (1)

In der Praxis habe ich herausgefunden, dass wenn n0UL ist, dass Index AUF 0UL gesetzt ist, genau wie bei einer n von 1UL. Das einzige, was in der Dokumentation im Fall einer n von 0UL garantiert ist, ist, dass die Rückgabe lautet:

0 wenn keine gesetzten Bits gefunden wurden

Ähnlich wie bei der bevorzugten log2-Implementierung über dem Return sollte also geprüft werden, ob in diesem Fall Index auf einen markierten Wert gesetzt wird. Ich habe hier noch einmal ein Beispiel für die Verwendung von ULONG_MAX für diesen Flag-Wert geschrieben: http://rextester.com/GCU61409

3
Jonathan Mee

Denken Sie bitweise Operatoren.

Ich habe die Frage beim ersten Mal falsch verstanden. Sie sollten ein Int mit dem ganz linken Bit (die anderen Null) erstellen. Angenommen, cmp ist auf diesen Wert gesetzt:

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

Wenn man Josh's Benchmark erweitert, kann man die Clz wie folgt verbessern

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

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

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

2
JonesD

Wenn man dies in Betracht zieht, da es sich um einen weiteren Ansatz handelt, scheint es anders zu sein als andere.

gibt -1 zurück, falls x==0, sonst floor( log2(x)) (max. Ergebnis 31)

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

Dies ist, was ich verwende, wenn ich __builtin_clz wegen Portabilitätsproblemen nicht verwenden möchte.

Um es kompakter zu gestalten, könnte man stattdessen eine Schleife zum Reduzieren verwenden, wobei jedes Mal 4 zu r addiert wird, und zwar maximal 7 Iterationen. Oder ein Hybrid, wie (für 64 Bits): Schleife auf 8 reduzieren, Test auf 4 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];
}
1
greggo

Meine bescheidene Methode ist sehr einfach:

MSB (x) = INT [Log (x)/Log (2)]

Übersetzung: Das MSB von x ist der ganzzahlige Wert von (Log von Basis x geteilt durch das Log von Basis 2).

Dies kann einfach und schnell an jede Programmiersprache angepasst werden. Probieren Sie es auf Ihrem Taschenrechner aus, um zu sehen, ob es funktioniert.

1
SpartanWar

Woaw, das waren viele Antworten. Es tut mir nicht leid, auf eine alte Frage geantwortet 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. 

1
Harry Svensson

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 lesbarer,

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 wollen,

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);
}
1
ChuckCottrill

Ich nehme an, Ihre Frage bezieht sich auf eine ganze Zahl (V genannt) und keine vorzeichenlose ganze Zahl.

int v = 612635685; // whatever value you wish

unsigned int get_msb(int v)
{
    int r = 31;                         // maximum number of iteration until integer has been totally left shifted out, considering that first bit is index 0. Also we could use (sizeof(int)) << 3 - 1 instead of 31 to make it work on any platform.

    while (!(v & 0x8000000) && r--) {   // mask of the highest bit
        v <<= 1;                        // multiply integer by 2.
    }
    return r;                           // will even return -1 if no bit was set, allowing error catch
}

Wenn Sie möchten, dass es funktioniert, ohne das Zeichen zu berücksichtigen, können Sie ein zusätzliches 'v << = 1;' vor der Schleife (und ändern Sie den r-Wert entsprechend auf 30) ..__ Bitte lassen Sie mich wissen, wenn ich etwas vergessen habe Ich habe es nicht getestet, aber es sollte gut funktionieren.

0
Antonin GAVREL

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

Der interessante Teil ist das Initialisieren der Tabelle. Da es sich um einen relativ kleinen Block handelt, den wir für die gesamte Lebensdauer des Prozesses benötigen, reserviere ich dafür nicht verwalteten Speicher mit Marshal.AllocHGlobal. Wie Sie sehen können, ist das gesamte Beispiel für maximale Leistung 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. Sie ist schreibgeschützt, sodass eine einzelne globale Kopie für den gleichzeitigen Zugriff freigegeben werden kann. Mit dieser Tabelle können Sie schnell das ganzzahlige Protokoll nachschlagen2, wonach wir hier suchen, für alle verschiedenen Integer-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' nicht definiert ist, den Wert -1 Erhält. Diese Unterscheidung ist für den richtigen Umgang mit 0-wertigen Oberwörtern im folgenden Code erforderlich. Hier ist ohne weiteres der Code für jedes der verschiedenen ganzzahligen Primitive:

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 Leistungstestgurt verglichen habe. Einige davon werden im Folgenden erwähnt. Die Testparameter waren eine einheitliche Dichte aller 65 Bitpositionen, d. H. 0 ... 31/63 plus Wert 0 (Was das Ergebnis -1 ergibt). Die Bits below 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 beiläufige Hinweise und Links zum Quellcode für alternative Testkandidaten im Zusammenhang mit den Tests, die ich durchgeführt habe, um die Leistung und Richtigkeit des obigen Codes zu überprüfen.


Die oben bereitgestellte, als Tab16A codierte Version war in vielen Läufen ein konstanter Gewinner. Diese verschiedenen Kandidaten, in aktiver Arbeits-/Scratch-Form, können gefunden werden hier , hier und hier .

 1 Bewerber.Höchster_Tab16A 622.496 
 2 Bewerber.Höchster_Tab16C 628.234 
 3 Bewerber.Höchster_Tab8A 649.146 
 4 Bewerber.Höchster_Tab8B 656.847 
 5 Bewerber_Tab8B 656.847 [.____. 6 Kandidaten.Höchster_Tab16D 659.650 
 7_Höchster_Ein_Bit_UNMANAGED.Höchster_U 702.900 
 8 de_Bruijn.IndexOfMSB 709.672 
 9_Höchster_2. 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 [ _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

Bemerkenswert ist, dass die schreckliche Leistung von ntdll.dll!RtlFindMostSignificantBit Über 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 aus diesen fünf Zeilen resultiert, daher müssen die verwalteten/nativen Übergangsstrafen schuld sein. Ich war auch überrascht, dass das Testen die 32-KB nd 64-KB-) short (16-Bit-) Direktsuche-Tabellen gegenüber den 128-Byte- (und 256-Byte-) byte (8- Bit) Nachschlagetabellen. Ich dachte, das Folgende wäre konkurrenzfähiger mit den 16-Bit-Lookups, 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 möchte, ist, dass ich ziemlich geschockt war, dass meine deBruijn-Methode nicht besser abgeschnitten hat. Dies ist die Methode, die ich vorher überall 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];
}

Es wird viel darüber diskutiert, wie überlegen und großartig deBruijn-Methoden sind --- (in dieser SO frage , und ich war eher einverstanden Tabellenmethoden (die ich als am schnellsten befunden habe) müssen beide eine Tabellensuche durchführen, und beide haben eine sehr minimale Verzweigung, nur deBruijn hat eine 64-Bit-Multiplikationsoperation. Ich habe hier nur die IndexOfMSB -Funktionen getestet. nicht das deBruijn IndexOfLSB--, aber ich erwarte, dass letzteres eine viel bessere Chance bietet, da es so viel weniger Operationen hat (siehe oben), und ich werde es wahrscheinlich weiterhin für LSB verwenden.

0
Glenn Slayden

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 erhalten Sie den ganzzahligen Teil des FPU-Befehls FYL2X (Y * Log2 X), indem Sie Y = 1 setzen

0
jemin