Comment trouver le nombre de 1 dans un nombre binary en temps O (1)?

Je sais que cela a déjà été demandé, mais je regarde cette solution particulière énumérée ici :

int BitCount(unsigned int u) { unsigned int uCount; uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111); return ((uCount + (uCount >> 3)) & 030707070707) % 63; } 

Comment ça marche?

Y at-il des mises en garde impliquées ici?

Théoriquement, est-il possible de trouver la réponse en temps constant? Je veux dire, ne devons-nous pas réellement parcourir les bits pour compter?

Compter les bits

Un entier non signé 32 bits u peut être écrit comme ceci:

u = a 31 * 2 31 + a 30 * 2 30 + ... + a 0 * 2 0

Nous voulons la valeur d’ a 31 + a 30 + ... + a 0 .

Comparons les valeurs de u >> k :

 u >> 0 = a 31 * 2 31 + a 30 * 2 30 + ... + a 1 * 2 1 + a 0 * 2 0
 u >> 1 = a 31 * 2 30 + a 30 * 2 29 + ... + a 1 * 2 0
 u >> 2 = a 31 * 2 29 + a 30 * 2 28 + ...
 ...
 u >> 29 = a 31 * 2 2 + a 29 * 2 1 + ...
 u >> 30 = a 31 * 2 1 + a 30 * 2 0
 u >> 31 = a 31 * 2 0

Nous allons calculer la population de bits par cette formule:

 u >> 0 - u >> 1 - u >> 2 - ... - u >> 31 = p 

Voyons pourquoi cela fonctionne:

  u >> 0 - u >> 1 - u >> 2 - ... - u >> 31 = u >> 0 - (u >> 1 + u >> 2 + ... + u >> 31) = u - q 

Quelle est la valeur de q ? Calculons-le petit à petit en regardant les valeurs de u >> k ci-dessus. Pour a 31 , c’est:

   un 31 * 2 30 + un 31 * 2 29 + ...
 = un 31 * (2 30 + 2 29 + ...)
 = un 31 * (2 31 - 1)

Ou pour a 30 :

   un 30 * 2 29 + un 30 * 2 28 + ...
 = un 30 * (2 29 + 2 28 + ...)
 = un 30 * (2 30 - 1)

On trouve: q = a 31 * (2 31 - 1) + a 30 * (2 30 - 1) + ...

Et ainsi

 u - q = a 31 * 2 31 - a 31 * (2 31 - 1) + ...
       = un 31 + un 30 + ... + un 0 

Comptage de bits en blocs de 3 bits

Cet algorithme commence par faire la même chose, mais en blocs de 3 bits:

 u >> 0 = AaBbbCccDddEeeFffGggHhhIiiJjjKkk (each letter is a bit) u >> 1 & 033333333333 = A Bb Cc Dd Ee Ff Gg Hh Ii Jj Kk (blank = zero) u >> 2 & 011111111111 = BCDEFGHIJK 

En prenant la différence, par l’algorithme ci-dessus, chaque octet dans uCount contient le nombre de bits définis dans l’octet correspondant dans u .

 uCount = αβγδεζηθικλ (each greek letter is an octet) uCount >> 3 = αβγδεζηθικ 

Donc, uCount + (uCount >> 3) est (λ+κ) * 2 0 + (κ+ι) * 2 3 + (ι+θ) * 2 6 + ...

En utilisant AND avec 0o30707070707 , nous 0o30707070707 tous les octets, de sorte que nous ne comptons qu’une seule fois chaque paire:

  r = (λ + κ) * 2 0 + (ι + θ) * 2 6 + (η + ζ) * 2 12 + ...
   = (λ + κ) * 64 0 + (ι + θ) * 64 1 + (η + ζ) * 64 2 + ... 

C’est un nombre en base 64, et nous voulons résumer les chiffres en base 64 pour obtenir α+β+γ+δ+ε+ζ+η+θ+ι+κ+λ , notre résultat final. Pour ce faire, nous calculons sa racine numérique en base 64: sachant que le résultat ne peut jamais être supérieur à 32, nous modulons simplement le nombre par 63.

La itération des bits est un temps constant car le nombre de bits d’un type est constant.

Ainsi, une solution qui vérifie le masque d’un bit et qui se décale pour chaque bit de la valeur cible est bien O(1) (par exemple, où la constante est 32).

Le moyen le plus rapide de faire cela est l’instruction popcnt. Vous pouvez y accéder via un compilateur insortingnsèque habituellement. Votre solution peut être utile sur les plateformes ne disposant pas de cette instruction.

Le comptage des bits mis en parallèle montre comment cela se fait. Cette méthode peut être utilisée pour les mots de bits de 8, 16, 32, 64, 128, etc., bien que les constantes utilisées dans les calculs changent.

Lorsque nous disons que cette opération est O (1), cela signifie que cela peut être fait en temps constant, quelle que soit la taille du mot. Compter les bits de la manière naïve est O (n) dans le nombre de bits.

Pratiquement, ce n’est que O (1) lorsque le processeur peut utiliser la taille du mot de manière native.

Quant à la façon dont cela fonctionne, il utilise “des nombres magiques”. Voir ce post de groupe de discussion pour une explication.