Position du bit le moins significatif qui est activé

Question

Je cherche un moyen efficace de déterminer la position du bit le moins significatif qui est activé dans un nombre entier, par exemple pour 0x0FF0, ce serait 4.

Une mise en œuvre triviale est la suivante :

unsigned GetLowestBitPos(unsigned value)
{
   assert(value != 0); // handled separately

   unsigned pos = 0;
   while (!(value & 1))
   {
      value >>= 1;
      ++pos;
   }
   return pos;
}

Des idées pour en tirer quelques cycles ?

(Note : cette question s'adresse aux personnes qui aiment ce genre de choses, et non aux personnes qui me disent que la xyzoptimisation est un mal).

[modifier] Merci à tous pour les idées ! J'ai aussi appris d'autres choses. C'est cool !

Answer 1

Astuces pour la manipulation des bits propose une excellente collection d'astuces pour manipuler les bits, accompagnée d'une discussion sur les performances et l'optimisation. Ma solution préférée pour votre problème (de ce site) est "multiplier et rechercher" :

unsigned int v;  // find the number of trailing zeros in 32-bit v 
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[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
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

Références utiles :

• " Utilisation des séquences de de Bruijn pour indexer un 1 dans un mot informatique "Explication de la raison pour laquelle le code ci-dessus fonctionne.
• " Représentation au conseil d'administration > Bitboards > BitScan " - Analyse détaillée de ce problème, avec un accent particulier sur la programmation d'échecs

Answer 2

Pourquoi ne pas utiliser la fonction intégrée ffs ? (J'ai récupéré une page de manuel de Linux, mais c'est plus largement disponible que cela).

ffs(3) - Page de manuel Linux

Nom

ffs - trouver le premier bit activé dans un mot

Synopsis

#include <strings.h>
int ffs(int i);
#define _GNU_SOURCE
#include <string.h>
int ffsl(long int i);
int ffsll(long long int i);

Description

La fonction ffs() renvoie la position du premier bit (le moins significatif) défini dans le mot i. Le bit le moins significatif est la position 1 et la position la plus significative, par exemple 32 ou 64. Les fonctions ffsll() et ffsl() font la même chose mais prennent des arguments de taille éventuellement différente.

Valeur de retour

Ces fonctions renvoient la position du premier bit activé, ou 0 si aucun bit n'est activé dans i.

Conforme à

4.3BSD, POSIX.1-2001.

Notas

Les systèmes BSD ont un prototype dans <string.h> .

Answer 3

Il existe une instruction d'assemblage x86 ( bsf ) cela fera l'affaire :)

Plus optimisé ? !

Note complémentaire :

L'optimisation à ce niveau est intrinsèquement dépendante de l'architecture. Les processeurs d'aujourd'hui sont trop complexe (en termes de prédiction de branchement, de manque de cache, de pipelining) qu'il est si difficile de prédire quel code est exécuté plus rapidement sur quelle architecture. Diminuer les opérations de 32 à 9 ou des choses comme ça pourrait même diminuer les performances sur certaines architectures. Un code optimisé sur une seule architecture peut entraîner un code plus mauvais sur l'autre. Je pense que vous devriez soit optimiser ceci pour un CPU spécifique, soit le laisser tel quel et laisser le compilateur choisir ce qu'il pense être le meilleur.

Answer 4

La plupart des architectures modernes disposent d'une instruction permettant de trouver la position du bit le plus bas ou du bit le plus haut, ou de compter le nombre de zéros de tête, etc.

Si vous avez une seule instruction de cette classe, vous pouvez émuler les autres à peu de frais.

Prenez un moment pour travailler sur le papier et réalisez que x & (x-1) efface le bit le plus bas dans x, et ( x & ~(x-1) ) retournera uniquement le bit le plus bas, indépendamment de l'architecture, de la longueur du mot, etc. Sachant cela, il est trivial d'utiliser le matériel count-leading-zeroes / highest-set-bit pour trouver le bit le plus bas s'il n'y a pas d'instruction explicite pour le faire.

S'il n'y a pas de support matériel pertinent, l'implémentation de la multiplication et de la consultation des zéros en tête de liste, donnée par aquí ou l'un de ceux qui se trouvent sur le Astuces pour la manipulation des bits La page peut trivialement être convertie pour donner le bit le plus bas en utilisant les identités ci-dessus et a l'avantage d'être sans branche.

Answer 5

La solution la plus rapide (non-intrinsèque/non-assembleur) consiste à trouver l'octet le plus bas et à l'utiliser dans une table de consultation de 256 entrées. Cela vous donne une performance de quatre instructions conditionnelles dans le pire des cas et de 1 dans le meilleur des cas. Non seulement c'est le plus petit nombre d'instructions, mais aussi le plus petit nombre de branches, ce qui est très important sur le matériel moderne.

Votre tableau (256 entrées de 8 bits) doit contenir l'indice du LSB pour chaque nombre compris entre 0 et 255. Vous vérifiez chaque octet de votre valeur et trouvez l'octet non nul le plus bas, puis utilisez cette valeur pour rechercher l'indice réel.

Cela nécessite 256 octets de mémoire, mais si la vitesse de cette fonction est si importante, ces 256 octets en valent la peine,

Par exemple

byte lowestBitTable[256] = {
.... // left as an exercise for the reader to generate
};

unsigned GetLowestBitPos(unsigned value)
{
  // note that order to check indices will depend whether you are on a big 
  // or little endian machine. This is for little-endian
  byte* bytes = (byte*)value;
  if (bytes[0])
    return lowestBitTable[bytes[0]];
  else if (bytes[1])
      return lowestBitTable[bytes[1]] + 8;
  else if (bytes[2])
      return lowestBitTable[bytes[2]] + 16;
  else
      return lowestBitTable[bytes[3]] + 24;  
}