Quel est le moyen le plus rapide / le plus efficace de trouver le bit le plus élevé (msb) dans un entier en C?

Si j'ai un entier n et que je veux connaître la position du bit le plus significatif (c'est-à-dire que si le bit le moins significatif est à droite, je veux connaître la position du bit le plus à gauche qui est un 1), Quelle est la méthode la plus rapide / la plus efficace pour le découvrir?

Je sais que POSIX prend en charge une ffs()méthode dans strings.h pour trouver le premier bit défini, mais il ne semble pas y avoir de fls()méthode correspondante .

Y a-t-il un moyen vraiment évident de faire cela qui me manque?

Qu'en est-il des cas où vous ne pouvez pas utiliser les fonctions POSIX pour la portabilité?

Edit: Qu'en est-il d'une solution qui fonctionne à la fois sur les architectures 32 et 64 bits (la plupart des listes de codes semblent ne fonctionner que sur les entiers 32 bits).

GCC a :

 - Fonction intégrée: int __builtin_clz (unsigned int x)
     Renvoie le nombre de 0 bits de début dans X, en commençant au plus
     position de bit significative. Si X vaut 0, le résultat n'est pas défini.

 - Fonction intégrée: int __builtin_clzl (unsigned long)
     Similaire à `__builtin_clz ', sauf que le type d'argument est` unsigned
     longue'.

 - Fonction intégrée: int __builtin_clzll (unsigned long long)
     Similaire à `__builtin_clz ', sauf que le type d'argument est` unsigned
     long long ».

Je m'attendrais à ce qu'ils soient traduits en quelque chose d'assez efficace pour votre plate-forme actuelle, que ce soit l'un de ces algorithmes sophistiqués de twiddling ou une seule instruction.

Une astuce utile si votre entrée peut être égale à zéro est __builtin_clz(x | 1): le réglage inconditionnel du bit bas sans en modifier les autres fait la sortie 31pour x=0, sans changer la sortie pour une autre entrée.

Pour éviter d'avoir à faire cela, votre autre option est les intrinsèques spécifiques à la plate-forme comme ARM GCC __clz(aucun en-tête nécessaire), ou x86 _lzcnt_u32sur les processeurs qui prennent en charge l' lzcntinstruction. (Attention au lzcntdécodage comme bsrsur les processeurs plus anciens au lieu de défaut, ce qui donne 31-lzcnt pour les entrées non nulles.)

Il n'y a malheureusement aucun moyen de tirer parti des différentes instructions CLZ sur les plates-formes non x86 qui définissent le résultat pour input = 0 comme 32 ou 64 (selon la largeur de l'opérande). x86 le lzcntfait aussi, tandis que bsrproduit un index de bits que le compilateur doit retourner à moins que vous n'utilisiez 31-__builtin_clz(x).

(Le "résultat non défini" n'est pas C Undefined Behavior, juste une valeur qui n'est pas définie. Il s'agit en fait de ce qui se trouvait dans le registre de destination lorsque l'instruction a été exécutée. AMD le documente, Intel ne le fait pas, mais les processeurs Intel implémentent ce comportement . Mais ce n'est pas ce qui était auparavant dans la variable C que vous assignez, ce n'est généralement pas ainsi que les choses fonctionnent lorsque gcc transforme C en asm. Voir aussi Pourquoi la rupture de la "dépendance de sortie" de LZCNT est-elle importante? )

En supposant que vous êtes sur x86 et jeu pour un peu d'assembleur en ligne, Intel fournit une BSRinstruction ("bit scan reverse"). C'est rapide sur certains x86 (microcodés sur d'autres). À partir du manuel:

Recherche l'opérande source pour le bit défini le plus significatif (1 bit). Si le bit 1 le plus significatif est trouvé, son index de bits est stocké dans l'opérande de destination. L'opérande source peut être un registre ou un emplacement mémoire; l'opérande de destination est un registre. L'indice de bits est un décalage non signé par rapport au bit 0 de l'opérande source. Si l'opérande de source de contenu est 0, le contenu de l'opérande de destination n'est pas défini.

(Si vous êtes sur PowerPC, il existe une cntlzinstruction similaire ("compter les zéros non significatifs").)

Exemple de code pour 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;
}

Voir aussi ce tutoriel d'assembleur en ligne , qui montre (section 9.4) qu'il est considérablement plus rapide que le code en boucle.

Puisque 2 ^ N est un entier avec uniquement le Nième bit défini (1 << N), la recherche de la position (N) du bit le plus élevé correspond à l'entier log de base 2 de cet entier.

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

unsigned int v;
unsigned r = 0;

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

Cet algorithme "évident" peut ne pas être transparent pour tout le monde, mais lorsque vous réalisez que le code se décale d'un bit vers la droite à plusieurs reprises jusqu'à ce que le bit le plus à gauche ait été décalé (notez que C traite toute valeur non nulle comme vraie) et renvoie le nombre des quarts de travail, c'est parfaitement logique. Cela signifie également qu'il fonctionne même lorsque plus d'un bit est défini - le résultat est toujours pour le bit le plus significatif.

Si vous faites défiler cette page vers le bas, il existe des variantes plus rapides et plus complexes. Cependant, si vous savez que vous avez affaire à des nombres avec beaucoup de zéros non significatifs, l'approche naïve peut fournir une vitesse acceptable, car le décalage de bits est plutôt rapide en C, et l'algorithme simple ne nécessite pas d'indexer un tableau.

REMARQUE: lorsque vous utilisez des valeurs 64 bits, soyez extrêmement prudent lorsque vous utilisez des algorithmes très intelligents; beaucoup d'entre eux ne fonctionnent correctement que pour les valeurs 32 bits.

Cela devrait être rapide comme l'éclair:

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

C'est un peu comme trouver une sorte de journal d'entiers. Il y a des trucs à faire, mais j'ai créé mon propre outil pour cela. Le but est bien sûr la vitesse.

Ma réalisation est que le CPU a déjà un détecteur de bits automatique, utilisé pour la conversion d'entiers en flottants! Alors utilisez ça.

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

Cette version convertit la valeur en un double, puis lit l'exposant, qui vous indique où se trouvait le bit. Le décalage et la soustraction fantaisie consistent à extraire les parties appropriées de la valeur IEEE.

Il est légèrement plus rapide d'utiliser des flotteurs, mais un flotteur ne peut vous donner que les 24 premières positions de bits en raison de sa plus petite précision.

Pour ce faire en toute sécurité, sans comportement indéfini en C ++ ou C, utilisez memcpyplutôt que le cast de pointeur pour le poinçonnage de type. Les compilateurs savent comment l'intégrer efficacement.

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

Ou dans C99 et versions ultérieures, utilisez un fichier union {double d; uint32_t u[2];};. Mais notez qu'en C ++, la punition de type union n'est prise en charge que sur certains compilateurs en tant qu'extension, pas dans ISO C ++.

Cela sera généralement plus lent qu'un intrinsèque spécifique à la plate-forme pour une instruction de comptage de zéros en tête, mais l'ISO C portable n'a pas une telle fonction. Certains processeurs ne disposent pas non plus d'une instruction de comptage de début de zéro, mais certains d'entre eux peuvent convertir efficacement des entiers en double. Cependant, le poinçonnage d'un motif de bits FP en entier peut être lent (par exemple, sur PowerPC, il nécessite un stockage / rechargement et provoque généralement un blocage du magasin de chargement).

Cet algorithme pourrait être utile pour les implémentations SIMD, car moins de processeurs ont SIMD lzcnt. x86 n'a reçu une telle instruction qu'avec AVX512CD

Kaz Kylheku ici

J'ai comparé deux approches pour ce nombre de plus de 63 bits (le type long long sur gcc x86_64), en évitant le bit de signe.

(Il se trouve que j'ai besoin de ce "trouver le bit le plus élevé" pour quelque chose, vous voyez.)

J'ai implémenté la recherche binaire basée sur les données (étroitement basée sur l'une des réponses ci-dessus). J'ai également implémenté à la main un arbre de décision complètement déroulé, qui n'est que du code avec des opérandes immédiats. Pas de boucles, pas de tables.

L'arbre de décision (most_bit_unrolled) est évalué à 69% plus rapide, sauf pour le cas n = 0 pour lequel la recherche binaire a un test explicite.

Le test spécial de la recherche binaire pour le cas 0 n'est que 48% plus rapide que l'arbre de décision, qui n'a pas de test spécial.

Compilateur, machine: (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;
}

Programme de test rapide et sale:

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

En utilisant uniquement -O2, la différence devient plus grande. L'arbre de décision est presque quatre fois plus rapide.

J'ai également comparé le code de changement de bits naïf:

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

Ce n'est rapide que pour de petits nombres, comme on pouvait s'y attendre. En déterminant que le bit le plus élevé est 1 pour n == 1, il a évalué plus de 80% plus rapidement. Cependant, la moitié des nombres choisis au hasard dans l'espace de 63 bits ont le 63e bit défini!

Sur l'entrée 0x3FFFFFFFFFFFFFFF, la version de l'arbre de décision est un peu plus rapide qu'elle ne l'est sur 1 et se révèle être 1120% plus rapide (12,2 fois) que le décaleur de bits.

Je vais également comparer l'arbre de décision aux fonctions intégrées de GCC, et essayer également un mélange d'entrées plutôt que de répéter avec le même nombre. Il peut y avoir une prédiction de branche bloquée et peut-être des scénarios de mise en cache irréalistes qui le rendent artificiellement plus rapide sur les répétitions.

Qu'en est-il de

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 registre, 13 instructions. Croyez-le ou non, c'est généralement plus rapide que l'instruction BSR mentionnée ci-dessus, qui fonctionne en temps linéaire. C'est le temps logarithmique.

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

Voici quelques (simples) benchmarks, des algorithmes actuellement donnés sur cette page ...

Les algorithmes n'ont pas été testés sur toutes les entrées de unsigned int; alors vérifiez d'abord cela, avant d'utiliser aveuglément quelque chose;)

Sur ma machine, clz (__builtin_clz) et asm fonctionnent le mieux. asm semble encore plus rapide que clz ... mais cela pourrait être dû au simple benchmark ...

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

Bien que je n'utiliserais probablement cette méthode que si j'avais absolument besoin des meilleures performances possibles (par exemple pour écrire une sorte d'IA de jeu de société impliquant des bitboards), la solution la plus efficace est d'utiliser l'ASM en ligne. Consultez la section Optimisations de cet article de blog pour le code avec une explication.

[...], l' bsrlinstruction d'assemblage calcule la position du bit le plus significatif. Ainsi, nous pourrions utiliser cette asmdéclaration:

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

J'avais besoin d'une routine pour faire cela et avant de chercher sur le Web (et de trouver cette page), j'ai proposé ma propre solution basée sur une recherche binaire. Même si je suis sûr que quelqu'un a déjà fait ça! Il fonctionne en temps constant et peut être plus rapide que la solution "évidente" publiée, bien que je ne fasse pas de grandes déclarations, je la publie simplement par intérêt.

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

c'est une sorte de recherche binaire, cela fonctionne avec toutes sortes de types d'entiers (non signés!)

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

pour faire complet:

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

Quelques réponses trop complexes ici. La technique Debruin ne doit être utilisée que lorsque l'entrée est déjà une puissance de deux, sinon il existe un meilleur moyen. Pour une puissance de 2 entrées, Debruin est le plus rapide absolu, encore plus rapide que _BitScanReversesur n'importe quel processeur que j'ai testé. Cependant, dans le cas général, _BitScanReverse(ou quel que soit le nom intrinsèque de votre compilateur) est le plus rapide (sur certains processeurs, il peut cependant être microcodé).

Si la fonction intrinsèque n'est pas une option, voici une solution logicielle optimale pour le traitement des entrées générales.

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

Notez que cette version ne nécessite pas de recherche Debruin à la fin, contrairement à la plupart des autres réponses. Il calcule la position en place.

Les tables peuvent être préférables cependant, si vous les appelez à plusieurs reprises, le risque de manque de cache est éclipsé par l'accélération d'une table.

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

Cela devrait produire le débit le plus élevé de toutes les réponses logicielles données ici, mais si vous ne l'appelez qu'occasionnellement, préférez une solution sans table comme mon premier extrait de code.

Comme le soulignent les réponses ci-dessus, il existe plusieurs façons de déterminer le bit le plus significatif. Cependant, comme cela a également été souligné, les méthodes sont susceptibles d'être uniques aux registres 32 bits ou 64 bits. La page bithacks de stanford.edu fournit des solutions qui fonctionnent à la fois pour l'informatique 32 bits et 64 bits. Avec un peu de travail, ils peuvent être combinés pour fournir une solide approche cross-architecture pour obtenir le MSB. La solution à laquelle je suis arrivé et qui a été compilé / travaillé sur des ordinateurs 64 et 32 ​​bits était:

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

Une version en C utilisant des approximations successives:

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

Avantage: le temps de fonctionnement est constant quel que soit le nombre fourni, car le nombre de boucles est toujours le même. (4 boucles lors de l'utilisation de "unsigned int")

Je sais que cette question est très ancienne, mais juste après avoir implémenté une fonction msb () moi-même, j'ai trouvé que la plupart des solutions présentées ici et sur d'autres sites Web ne sont pas nécessairement les plus efficaces - du moins pour ma définition personnelle de l'efficacité (voir aussi Mise à jour ci-dessous ). Voici pourquoi:

La plupart des solutions (en particulier celles qui utilisent une sorte de schéma de recherche binaire ou l'approche naïve qui effectue un balayage linéaire de droite à gauche) semblent négliger le fait que pour les nombres binaires arbitraires, il n'y en a pas beaucoup qui commencent par une très longue séquence de des zéros. En fait, pour toute largeur de bit, la moitié de tous les entiers commencent par 1 et un quart d'entre eux commencent par 01 . Voyez où j'en suis? Mon argument est qu'un balayage linéaire commençant de la position de bit la plus significative à la moins significative (de gauche à droite) n'est pas si "linéaire" qu'il pourrait le paraître à première vue.

On peut montrer ¹ , que pour toute largeur de bit, le nombre moyen de bits à tester est d'au plus 2. Cela se traduit par une complexité en temps amorti de O (1) par rapport au nombre de bits (!) .

Bien sûr, le pire des cas est toujours O (n) , pire que le O (log (n)) que vous obtenez avec les approches de type recherche binaire, mais comme il y a si peu de pires cas, ils sont négligeables pour la plupart des applications ( Mise à jour : pas tout à fait: il peut y en avoir peu, mais ils peuvent se produire avec une probabilité élevée - voir Mise à jour ci-dessous).

Voici l'approche «naïve» que j'ai proposée, qui au moins sur ma machine bat la plupart des autres approches (les schémas de recherche binaire pour les entiers 32 bits nécessitent toujours log ₂ (32) = 5 étapes, alors que cet algorithme stupide nécessite moins que 2 en moyenne) - désolé pour cela étant du C ++ et non du C pur:

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

Mise à jour : Bien que ce que j'ai écrit ici soit parfaitement vrai pour les entiers arbitraires , où chaque combinaison de bits est également probable (mon test de vitesse mesurait simplement le temps qu'il fallait pour déterminer le MSB pour tous les entiers 32 bits), des entiers réels, pour laquelle une telle fonction sera appelée, suivent généralement un modèle différent: dans mon code, par exemple, cette fonction est utilisée pour déterminer si une taille d'objet est une puissance de 2, ou pour trouver la prochaine puissance de 2 supérieure ou égale à un taille de l'objet . Je suppose que la plupart des applications utilisant le MSB impliquent des nombres beaucoup plus petits que le nombre maximum qu'un entier peut représenter (les tailles d'objet utilisent rarement tous les bits d'un size_t). Dans ce cas, ma solution sera en fait pire qu'une approche de recherche binaire - donc cette dernière devrait probablement être préférée, même si ma solution sera plus rapide en boucle sur tous les entiers.
TL; DR: Les entiers réels auront probablement un biais vers le pire des cas de cet algorithme simple, ce qui le rendra pire à la fin - malgré le fait qu'il est amorti O (1) pour des entiers vraiment arbitraires.

¹ L'argument est le suivant (brouillon): Soit n le nombre de bits (largeur en bits). Il y a un total de 2 ⁿ entiers qui peuvent être représentés avec n bits. Il y a 2 ^{n - 1} entiers commençant par 1 (le premier 1 est fixe, les n - 1 bits restants peuvent être n'importe quoi). Ces entiers ne nécessitent qu'une seule interation de la boucle pour déterminer le MSB. De plus, il y a 2 ^{n - 2} entiers commençant par 01 , nécessitant 2 itérations, 2 ^{n - 3} entiers commençant par 001 , nécessitant 3 itérations, et ainsi de suite.

Si nous additionnons toutes les itérations requises pour tous les entiers possibles et les divisons par 2 ⁿ , le nombre total d'entiers, nous obtenons le nombre moyen d'itérations nécessaires pour déterminer le MSB pour les entiers à n bits:

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

Cette série d'itérations moyennes est en fait convergente et a une limite de 2 pour n vers l'infini

Ainsi, l'algorithme naïf de gauche à droite a en fait une complexité temporelle constante amortie de O (1) pour n'importe quel nombre de bits.

c99nous a donné log2. Cela supprime le besoin de toutes les log2implémentations spéciales de sauce que vous voyez sur cette page. Vous pouvez utiliser l' log2implémentation de la norme comme ceci:

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

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

Un nde 0ULdoit également être protégé, car:

-∞ est retourné et FE_DIVBYZERO est levé

Je l' ai écrit un exemple de ce contrôle que les ensembles arbitrairement Indexà ULONG_MAXici: https://ideone.com/u26vsi

le Visual Studiocorollaire à la seule réponse gcc d' Ephemient est:

const auto n = 13UL;
unsigned long Index;

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

La documentation pour les_BitScanReverse états qui Indexest:

Chargé avec la position de bit du premier bit défini (1) trouvé

Dans la pratique , j'ai trouvé que si nest 0ULque Indexest réglé0UL , tout comme il serait un ndes 1UL. Mais la seule chose garantie dans la documentation dans le cas d'un nde 0ULest que le retour est:

0 si aucun bit défini n'a été trouvé

Ainsi, de manière similaire à l' log2implémentation préférable ci-dessus, le retour doit être vérifié en définissant Indexune valeur marquée dans ce cas. J'ai à nouveau écrit un exemple d'utilisation ULONG_MAXde cette valeur d'indicateur ici: http://rextester.com/GCU61409

Pensez aux opérateurs au niveau du bit.

J'ai mal compris la question la première fois. Vous devriez produire un int avec le bit le plus à gauche (les autres à zéro). En supposant que cmp est défini sur cette valeur:

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

En se développant sur la référence de Josh ... on peut améliorer le clz comme suit

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

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

Concernant l'asm: notez qu'il existe bsr et bsrl (c'est la version "longue"). la normale pourrait être un peu plus rapide.

Notez que ce que vous essayez de faire est de calculer le log2 entier d'un entier,

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

Notez que vous pouvez essayer de rechercher plus d'un bit à la fois.

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

Cette approche utilise une recherche binaire

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

Une autre méthode de recherche binaire, peut-être plus lisible,

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

Et parce que vous voudrez les tester,

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

Mettre cela en place étant donné que c'est «encore une autre» approche, semble être différent des autres déjà donnés.

renvoie -1si x==0, sinonfloor( log2(x)) (résultat max 31)

Réduisez le problème de 32 à 4 bits, puis utilisez une table. Peut-être inélégant, mais pragmatique.

C'est ce que j'utilise quand je ne veux pas utiliser __builtin_clz raison de problèmes de portabilité.

Pour le rendre plus compact, on pourrait à la place utiliser une boucle pour réduire, en ajoutant 4 à r à chaque fois, max 7 itérations. Ou certains hybrides, comme (pour 64 bits): boucle pour réduire à 8, test pour réduire à 4.

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, c'était beaucoup de réponses. Je ne suis pas désolé d'avoir répondu à une vieille question.

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

Cette réponse est assez similaire à une autre réponse ... eh bien.

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

Ou obtenez la partie entière de l'instruction FPU FYL2X (Y * Log2 X) en définissant Y = 1

Une autre affiche a fourni une table de consultation utilisant une recherche octet-large . Au cas où vous voudriez gagner un peu plus de performances (au prix de 32 Ko de mémoire au lieu de seulement 256 entrées de recherche), voici une solution utilisant une table de recherche de 15 bits , en C # 7 pour .NET .

La partie intéressante est l'initialisation de la table. Comme il s'agit d'un bloc relativement petit que nous voulons pour la durée de vie du processus, j'alloue de la mémoire non gérée à cet effet en utilisant Marshal.AllocHGlobal. Comme vous pouvez le voir, pour des performances maximales, l'ensemble de l'exemple est écrit en natif:

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

Le tableau nécessite une initialisation unique via le code ci-dessus. Il est en lecture seule, donc une seule copie globale peut être partagée pour un accès simultané. Avec ce tableau, vous pouvez rechercher rapidement le journal des nombres entiers ₂ , ce que nous recherchons ici, pour toutes les différentes largeurs d'entiers (8, 16, 32 et 64 bits).

Notez que l'entrée de table pour 0, le seul entier pour lequel la notion de 'bit le plus élevé' n'est pas définie, reçoit la valeur-1 . Cette distinction est nécessaire pour une gestion correcte des mots supérieurs de valeur 0 dans le code ci-dessous. Sans plus tarder, voici le code de chacune des différentes primitives entières:

Version ulong (64 bits)

/// <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)];
}

Version uint (32 bits)

/// <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)];
}

Diverses surcharges pour ce qui précède

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

Il s'agit d'une solution complète et fonctionnelle qui représente les meilleures performances sur .NET 4.7.2 pour de nombreuses alternatives que j'ai comparées à un harnais de test de performances spécialisé. Certains d'entre eux sont mentionnés ci-dessous. Les paramètres de test étaient une densité uniforme de toutes les positions de 65 bits, c'est-à-dire 0 ... 31/63 plus la valeur 0(qui produit le résultat -1). Les bits sous la position d'index cible ont été remplis de manière aléatoire. Les tests étaient uniquement x64 , en mode version, avec les optimisations JIT activées.

C'est la fin de ma réponse formelle ici; ce qui suit sont quelques notes occasionnelles et des liens vers le code source pour les candidats aux tests alternatifs associés aux tests que j'ai exécutés pour valider les performances et l'exactitude du code ci-dessus.

La version fournie ci-dessus, codée Tab16A, a été un gagnant constant sur de nombreuses courses. Ces différents candidats, sous forme de travail actif / scratch, peuvent être trouvés ici , ici et ici .

 1 candidats.HighestOne_Tab16A 622496
 2 candidats.HighestOne_Tab16C 628234
 3 candidats.HighestOne_Tab8A 649146
 4 candidats.HighestOne_Tab8B 656847
 5 candidats.HighestOne_Tab16B 657,147
 6 candidats.HighestOne_Tab16D 659,650
 7 _highest_one_bit_UNMANAGED.HighestOne_U 702 900
 8 de_Bruijn.IndexOfMSB 709 672
 9 _old_2.HighestOne_Old2 715810
10 _test_A.HighestOne8 757.188
11 _old_1.HighestOne_Old1 757,925
12 _test_A.HighestOne5 (dangereux) 760387
13 _test_B.HighestOne8 (dangereux) 763,904
14 _test_A.HighestOne3 (non sécurisé) 766433
15 _test_A.HighestOne1 (dangereux) 767,321
16 _test_A.HighestOne4 (dangereux) 771,702
17 _test_B.HighestOne2 (dangereux) 772,136
18 _test_B.HighestOne1 (dangereux) 772,527
19 _test_B.HighestOne3 (dangereux) 774,140
20 _test_A.HighestOne7 (non sécurisé) 774,581
21 _test_B.HighestOne7 (dangereux) 775 463
22 _test_A.HighestOne2 (non sécurisé) 776865
23 candidats.HighestOne_NoTab 777698
24 _test_B.HighestOne6 (dangereux) 779481
25 _test_A.HighestOne6 (non sécurisé) 781,553
26 _test_B.HighestOne4 (dangereux) 785 504
27 _test_B.HighestOne5 (dangereux) 789 797
28 _test_A.HighestOne0 (non sécurisé) 809,566
29 _test_B.HighestOne0 (dangereux) 814 990
30 _highest_one_bit.HighestOne 824345
30 _bitarray_ext.RtlFindMostSignificantBit 894 069
31 candidats.HighestOne_Naive 898865

Il est à noter que les terribles performances de ntdll.dll!RtlFindMostSignificantBitvia P / Invoke:

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

C'est vraiment dommage, car voici toute la fonction réelle:

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

Je ne peux pas imaginer les mauvaises performances provenant de ces cinq lignes, donc les pénalités de transition gérée / native doivent être à blâmer. J'ai également été surpris que les tests aient vraiment favorisé les shorttables de recherche directe de 32 Ko (et 64 Ko) (16 bits) par rapport aux tables de recherche de 128 octets (et 256 octets) byte(8 bits). Je pensais que ce qui suit serait plus compétitif avec les recherches 16 bits, mais ces dernières ont toujours surpassé ceci:

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

La dernière chose que je ferai remarquer est que j'ai été assez choqué que ma méthode deBruijn n'ait pas mieux fonctionné. C'est la méthode que j'avais précédemment utilisée de manière généralisée:

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