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

Question

Si j'ai un certain entier n, et je veux savoir la position du bit le plus significatif (qui est, si le bit le moins significatif est sur la droite, je veux savoir la position la plus à gauche bit à 1), ce qui est le plus rapide/la plus efficace méthode de recherche?

Je sais que POSIX prend en charge un ffs() méthode dans les chaînes.h pour trouver le premier ensemble de bits, mais il ne semble pas être une correspondante fls() méthode.

Est-il vraiment un moyen évident de faire ce que je suis absent?

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

Edit: à propos d'une solution qui fonctionne sur les versions 32 bits et 64 bits des architectures (beaucoup d'exemples de code semble comme s'ils avaient seulement le travail sur 32 bits ints).

Answer 1

GCC a:

 -- Intégrés dans la Fonction: int __builtin_clozapine (unsigned int x)
 Renvoie le nombre de 0 bits en X, en commençant par le plus
 significative de la position du bit. Si X est égal à 0, le résultat est indéfini.

 -- Intégrés dans la Fonction: int __builtin_clzl (unsigned long)
 Similaires à "__builtin_clozapine', à l'exception de l'argument est de type `unsigned
".

 -- Intégrés dans la Fonction: int __builtin_clzll (unsigned long long)
 Similaires à "__builtin_clozapine', à l'exception de l'argument est de type `unsigned
 long long".

Je m'attends à être traduit en quelque chose de raisonnablement efficace pour votre plate-forme actuelle, que ce soit l'un de ceux de fantaisie peu-se tourner les algorithmes, ou une seule instruction.

Answer 2

En supposant que vous êtes sur x86 et jeu pour un peu d'assembleur en ligne, Intel fournit un BSR instruction ("bit de balayage inverse"). Il est rapide sur certains x86s (microcoded sur d'autres). Dans le manuel:

Les recherches de l'opérande source pour le plus significatif bits (1 bit). Si l'un des plus importants 1 bits est trouvé, son index du bit est stocké dans l'opérande de destination. La source de l'opérande peut être une registre ou un emplacement de la mémoire; la l'opérande de destination est un registre. L' l'index du bit est un type unsigned décalage à partir de la le bit 0 de l'opérande source. Si l' contenu de l'opérande source est 0, le le contenu de l'opérande de destination est undefined.

(Si vous êtes sur PowerPC, il y a un similaire cntlz ("nombre de zéros") l'instruction.)

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 cet assembleur en ligne tutoriel, ce qui montre (section 9.4) étant beaucoup plus vite que le code de boucle.

Answer 3

Depuis le 2^N est un nombre entier avec seulement le n-ième bit est activé (1 << N), la recherche de la position (N) de la plus haute bit est l'entier log en base 2 de cet entier.

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

unsigned int v;
unsigned r = 0;

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

Cette "évidence", l'algorithme peut ne pas être transparent pour tout le monde, mais quand vous vous rendez compte que le code des quarts de droit par un bit à plusieurs reprises jusqu'à ce que le bit plus à gauche a été décalés (à noter que C traite toute valeur non nulle, comme vrai) et retourne le nombre de quarts de travail, il est parfaitement logique. Cela signifie aussi 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 vers le bas de la page, il y a de plus rapide, de plus en plus complexe de variations. Toutefois, si vous savez que vous avez affaire avec des nombres avec beaucoup de zéros, l'approche naïve peut fournir la vitesse acceptable, étant donné le décalage de bits est plutôt rapide en C, et l'algorithme simple et ne nécessite pas l'indexation d'un tableau.

REMARQUE: Lors de l'utilisation de valeurs de 64 bits, être extrêmement prudent au sujet en utilisant des algorithmes intelligents; beaucoup d'entre eux ne fonctionnera correctement que pour des valeurs de 32 bits.

Answer 4

Voir " Nombre d'algorithmes de zéros non significatifs " dans Le délice de Hacker .

Answer 5

C'est un peu comme trouver une sorte de journal entier. Il y a peu-se tourner les trucs, mais j'ai fait mon propre outil pour cela. L'objectif est bien sûr de la vitesse.

Ma réalisation est que le PROCESSEUR dispose d'un dispositif de bit-détecteur déjà, utilisé pour l'entier de flotteur de conversion! Ainsi l'utilisation que.

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

Cette version jette la valeur d'un double, lit ensuite hors de l'exposant, qui vous indique où l'été. La fantaisie de changement et de soustraction est d'extraire les pièces requises à partir de l'IEEE.

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