Comment compter les zéros de tête dans un entier non signé de 32 bits

Quelqu’un pourrait-il me dire, s’il vous plaît, quel est un algorithme efficace pour compter le nombre de zéros non significatifs dans un entier non signé 32 bits en programmation C?

Cette discussion suppose que votre compilateur ne prend pas en charge l’opération ou qu’il ne produit pas un assemblage suffisant. Notez que ces deux __builtin_clz sont peu probables de nos jours, donc je vous recommande simplement d’utiliser __builtin_clz pour gcc ou équivalent sur votre compilateur.

Notez que déterminer qui est le “meilleur” clz algo ne peut être fait que par vous. Les processeurs modernes sont des bêtes compliquées et les performances de ces algorithmes dépendent en grande partie de la plate-forme sur laquelle vous les exécutez, des données que vous leur envoyez et du code qui les utilise. Le seul moyen d’en être sûr est de mesurer, mesurer et mesurer davantage. Si vous ne pouvez pas faire la différence, alors vous ne regardez probablement pas votre goulot d’étranglement et votre temps sera mieux dépensé ailleurs.

Maintenant que les désistements ennuyeux sont terminés, jetons un coup d’œil à ce que Hacker’s Delight a à dire sur le problème. Une étude rapide montre que tous les algorithmes reposent sur une recherche binary d’une description. Voici un exemple simple:

 int n = 32; unsigned y; y = x >>16; if (y != 0) { n = n -16; x = y; } y = x >> 8; if (y != 0) { n = n - 8; x = y; } y = x >> 4; if (y != 0) { n = n - 4; x = y; } y = x >> 2; if (y != 0) { n = n - 2; x = y; } y = x >> 1; if (y != 0) return n - 2; return n - x; 

Notez que cela fonctionne sur 32 ints et qu’il peut également être transformé en une version itérative si nécessaire. Malheureusement, cette solution n’a pas beaucoup de parallélisme au niveau de l’instruction et a quelques twigs qui ne font pas un très bon algo. Notez qu’une version sans twig du code ci-dessus existe mais qu’elle est beaucoup plus détaillée, donc je ne vais pas la reproduire ici.

Améliorons donc la solution en utilisant l’instruction pop (compte le nombre de bits):

 x = x | (x >> 1); x = x | (x >> 2); x = x | (x >> 4); x = x | (x >> 8); x = x | (x >>16); return pop(~x); 

Donc comment ça fonctionne? La clé est l’instruction pop(~x) à la fin qui compte le nombre de zéros dans x . Pour que le nombre de zéros soit significatif, nous devons d’abord supprimer tous les 0 qui ne sont pas en tête. Nous faisons cela en propageant correctement les 1 en utilisant un algorithme binary. Bien que nous n’ayons toujours pas beaucoup de parallélisme au niveau instruction, nous nous sums débarrassés de toutes les twigs et le nombre de cycles utilisé est inférieur à celui de la solution précédente. Beaucoup mieux.

Alors, qu’en est-il de cette instruction pop, n’est-ce pas sortingcher? La plupart des architectures ont une instruction pop d’un cycle accessible via les fonctions intégrées du compilateur (par exemple, __builtin_pop de gcc). Sinon, il existe des solutions basées sur des tables, mais vous devez faire attention lorsque vous échangez des cycles pour des access au cache, même si la table est entièrement conservée dans le cache N1.

Enfin, comme d’habitude pour le plaisir des hackers, nous commençons à errer dans des territoires inconnus. Comptons-nous des zéros au début en utilisant des nombres à virgule flottante

 union { unsigned asInt[2]; double asDouble; }; asDouble = (double)k + 0.5; return 1054 - (asInt[LE] >> 20); 

Tout d’abord, un petit avertissement: NE PAS UTILISER CET ALGORITHME . Cela déclenche un comportement indéfini en ce qui concerne la norme. Cela a été reproduit pour le facteur de plaisir plus que toutes les utilisations pratiques. Utilisez à vos risques et périls.

Maintenant que les dénis de responsabilité sont éliminés, comment cela fonctionne-t-il? Il convertit d’abord l’int en un double et extrait ensuite le composant exposant du double. Des choses intéressantes. La constante LE doit être égale à 1 si elle est exécutée sur une machine little-endian et à 0 sur une machine big-endian.

Cela devrait vous donner un bref aperçu de divers algorithmes de twiddling pour résoudre ce problème. Notez que le livre contient plusieurs variantes qui font des compromis, mais je vous laisse découvrir celles-ci par vous-même.

C’est probablement la façon optimale de le faire en C pur:

 int clz(uint32_t x) { static const char debruijn32[32] = { 0, 31, 9, 30, 3, 8, 13, 29, 2, 5, 7, 21, 12, 24, 28, 19, 1, 10, 4, 14, 6, 22, 25, 20, 11, 15, 23, 26, 16, 27, 17, 18 }; x |= x>>1; x |= x>>2; x |= x>>4; x |= x>>8; x |= x>>16; x++; return debruijn32[x*0x076be629>>27]; } 

Une limitation: comme écrit, il ne supporte pas une entrée de zéro (où le résultat devrait être 32). Si toutes vos entrées sont inférieures à 0x80000000 , vous pouvez prendre en charge zéro sans frais supplémentaires en modifiant la première valeur du tableau en 32. Sinon, ajoutez simplement une ligne au début:

  if (!x) return 32; 

Comptons le nombre de chiffres qui ne sont pas des zéros à gauche. Après cela, nous faisons juste (32 – n). Premièrement, si le nombre est zéro, n est zéro. Autrement:

 n = 1 + floor(log2(x)) 

Autrement dit, nous utilisons le logarithme de la base deux pour déterminer dans quelle position est le bit non nul le plus significatif. Nous pouvons le faire efficacement sur x86 en utilisant l’instruction FYL2X, qui calcule log2.

Mais maintenant que nous parlons d’instructions x86, nous pouvons aussi regarder ce qui est vraiment disponible. C’est ici! http://en.wikipedia.org/wiki/Find_first_set – vous pouvez voir qu’il existe de nombreuses instructions qui font directement ce que vous voulez – si vous voulez écrire un assemblage ou au moins confirmer que votre compilateur d’optimisation génère ces instructions pour vous donné un code C soigneusement écrit.

Une solution serait (en Obj-c):

 // Assuming, your 32-bit unsigned integer is in i NSInteger nrLeadingZeroes = 0; while (i >= 0) { i = i << 1; nrLeadingZeroes++; } 

EDIT: (voir commentaire ci-dessous):

 // Assuming, your 32-bit unsigned integer is in j int i = (int)j; int nrLeadingZeroes = 0; while (i >= 0) { i = i << 1; nrLeadingZeroes++; }