Bit twiddling: quel bit est défini?

Question

J'ai un 64 bits entier non signé avec exactement 1 ensemble de bits. Je tiens à attribuer une valeur à chacun des 64 valeurs possibles (dans ce cas, les nombres premiers impairs, donc 0 x 1 correspond à 3, 0x2 correspond à 5, ..., 0x8000000000000000 correspond à 313).

Il semble que le meilleur moyen serait de convertir 1 -> 0, 2 -> 1, 4 -> 2, 8 -> 3, ..., 2^63 -> 63 et recherche les valeurs dans un tableau. Mais même si c'est le cas, je ne suis pas sûr de ce que le moyen le plus rapide pour obtenir le binaire de l'exposant est. Et il y a peut être plus rapide/de meilleures façons encore.

Cette opération sera utilisé 10¹⁴ 10¹⁶ fois, de sorte que la performance est un problème sérieux.

Answer 1

Enfin une solution optimale. Voir la fin de cette section pour quoi faire lorsque l'entrée est la garantie d'avoir exactement un non-bit zéro: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn

Voici le code:

static const int MultiplyDeBruijnBitPosition2[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 = MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27];

Vous pourriez être en mesure de s'adapter à un direct de multiplication de base de l'algorithme pour la version 64 bits d'entrée; sinon, il suffit d'ajouter un conditionnel pour voir si le bit est en haut à 32 positions ou inférieure à 32 positions, puis utiliser la version 32 bits de l'algorithme ici.

Mise à jour: Voici au moins une version 64 bits je viens de me mis au point, mais il utilise la division (en fait modulo).

r = Table[v%67];

Pour chaque puissance de 2, v%67 a une valeur distincte, donc il suffit de mettre votre impair de nombres premiers (ou peu indices si vous ne voulez pas l'impair de la premier chose) à la bonne position dans le tableau. 3 positions (0, 17 et 34) ne sont pas utilisés, ce qui peut être pratique si vous aussi vous voulez accepter tous les bits à zéro en entrée.

Mise à jour 2: version 64 bits.

r = Table[(uint64_t)(val * 0x022fdd63cc95386dull) >> 58];

C'est mon travail, mais j'ai eu l' B(2,6) De Bruijn séquence à partir de ce jeu d'échecs site donc je ne peux pas prendre le crédit pour quoi que ce soit mais de déterminer ce qu'est une séquence De Bruijn est et à l'aide de Google. ;-)

Quelques remarques supplémentaires sur la façon dont cela fonctionne:

Le nombre magique est un B(2,6) séquence De Bruijn. Il a la propriété que, si vous regardez un 6-consécutifs-bit fenêtre, vous pouvez obtenir toutes les six bits de la valeur dans la fenêtre en tournant le nombre de façon appropriée, et que chaque six bits de valeur est obtenue par exactement une rotation.

Nous avons corrigé la fenêtre en question doit être dans le top 6 positions de bits, et de choisir une séquence De Bruijn avec des 0 dans le top 6 bits. De ce fait, il n'est donc jamais avoir à traiter avec peu de rotations, ne fait que se déplacer, depuis 0 viendra dans le fond bits naturellement (et nous pourrions ne jamais regarder plus de 5 bits à partir du bas dans le top-6-bits de la fenêtre).

Maintenant, l'entrée de la valeur de cette fonction est une puissance de 2. Donc en multipliant la séquence De Bruijn par la valeur d'entrée effectue une bitshift en log2(value) bits. Nous avons maintenant dans la partie supérieure de 6 bits d'un nombre unique, qui détermine le nombre de bits que nous décalée, et pouvez l'utiliser comme un index dans une table pour obtenir la longueur réelle de la maj.

Cette même approche peut être utilisée pour arbitrairement large ou arbitrairement petits entiers, aussi longtemps que vous êtes prêt à mettre en œuvre la multiplication. Il vous suffit de trouver un B(2,k) De Bruijn séquence où k est le nombre de bits. Le jeu d'échecs wiki lien que j'ai fourni ci-dessus a De Bruijn séquences pour les valeurs de k allant de 1 à 6, et certains rapide recherche sur Google montre qu'il existe quelques articles sur l'optimisation des algorithmes de génération dans le cas général.

Answer 2

Si la performance est un problème sérieux, alors vous devriez utiliser intrinsèques/objets internes à l'utilisation du PROCESSEUR des instructions spécifiques telles que celles que l'on trouve ici pour gcc:

http://gcc.gnu.org/onlinedocs/gcc-4.5.0/gcc/Other-Builtins.html

- Built-in Fonction: int __builtin_ffs (unsigned int x) Retourne un et l'index de la moins importante 1 bit de x, si x est nul, retourne zéro.

- Built-in Fonction: int __builtin_clz (unsigned int x) Renvoie le nombre de 0 bits en x, en commençant à le bit le plus significatif de la position. Si x est égal à 0, le résultat est indéfini.

- Built-in Fonction: int __builtin_ctz (unsigned int x) Renvoie le nombre de fuite 0 bits en x, en commençant par le bit le moins significatif de la position. Si x est égal à 0, le résultat est indéfini.

Des choses comme cela sont la base de beaucoup de O(1) des algorithmes tels que le noyau de planificateurs qui ont besoin de trouver le premier non-vide la file d'attente signifiée par un tableau de bits.

NOTE: j'ai listé l' unsigned int versions, mais gcc a unsigned long long de versions que de bien.

Answer 3

Vous pouvez utiliser une technique de recherche binaire:

 int pos = 0;
if ((value & 0xffffffff) == 0) {
    pos += 32;
    value >>= 32;
}
if ((value & 0xffff) == 0) {
    pos += 16;
    value >>= 16;
}
if ((value & 0xff) == 0) {
    pos += 8;
    value >>= 8;
}
if ((value & 0xf) == 0) {
    pos += 4;
    value >>= 4;
}
if ((value & 0x3) == 0) {
    pos += 2;
    value >>= 2;
}
if ((value & 0x1) == 0) {
    pos += 1;
}
 

Cela a l'avantage sur les boucles que la boucle est déjà déroulée. Cependant, si cela est vraiment critique pour les performances, vous voudrez tester et mesurer chaque solution proposée.

Answer 4

Certaines architectures (un nombre surprenant, en fait) ont une seule instruction qui peut faire le calcul que vous voulez. Sur ARM, ce serait l'instruction CLZ (compter les zéros non significatifs). Pour Intel, l'instruction BSF (bit-scan forward) ou BSR (bit-scan reverse) vous aiderait.

Je suppose que ce n'est pas vraiment une réponse C , mais cela vous donnera la vitesse dont vous avez besoin!

Answer 5

• précalculer 1 << i (pour i = 0..63) et de les stocker dans un tableau
• utiliser un binaire de recherche pour trouver l'index dans le tableau d'une valeur donnée
• regardez le premier numéro dans un autre tableau à l'aide de cet indice

Par rapport à l'autre réponse que j'ai posté ici, cela ne devrait prendre que 6 étapes pour trouver l'index (par opposition à un maximum de 64). Mais il n'est pas clair pour moi qu'une étape de cette réponse n'est pas plus de temps que juste le décalage de bits et l'incrémentation d'un compteur. Vous pouvez essayer les deux bien que.