Apporter un peu de lumière sur le dénombrement de la population de l'algorithme

Question

J'ai regardé les bonnes méthodes pour faire popcount (nombre de bits).J'ai trouvé celui-ci, ici

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

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for(c = 0; v; c++) 
{
    v &= v - 1; // clear the least significant bit set
}

Essayez sur quelques exemples, il est vrai que cela fonctionne.Quelle propriété d'opérations binaires / représentation qui fait que cela fonctionne?

Pourriez-vous suggérer quelques lectures supplémentaires sur popcount et représentation binaire?

Answer 1

Vous commençons avec un premier v qui a d'abord les n bits dans ce jeu.

Le point du jeu est d'avoir 1 peu moins de compter à chaque itération de la boucle.De cette façon, il nous suffit de compter le nombre d'itérations de la boucle qui sont nécessaires avant que nous sommes arrivés au point où n = 0 pour déterminer la valeur initiale de n.

Notez que, si n = 0, alors v = 0, et donc la boucle va s'arrêter à ce point.Mais tant que v > 0, nous allons exécuter le corps de la boucle au moins une fois.À chaque itération, nous nous retrouvons avec un v qui a moins de 1 bit.

Voici pourquoi.La première propriété nous avons besoin, c'est que v && v == v.Maintenant v est une séquence de bits (le nombre exact de bits dépend de votre machine / OS), que vous pouvez commander à partir de la plus importante à la moins importante.Lorsque vous décrémenter v, nous pouvons noter les points suivants:

1. le bit le moins significatif, de l'appeler v[k], qui est définie à 1 sera mis à 0;
2. tous les bits de plus important que de v[k] pas changer lorsque vous décrémenter v.

Par Conséquent, ANDing v avec ses décrémenter permettront de préserver tous les bits les plus significatifs, mais set v[k] à 0.Et par définition, tous les bits qui sont moins importants que v[k], c'est à dire v[k-1] ...v[0], sont déjà 0 car v[k] est "le bit le moins significatif qui est de 1".Donc après ANDing tout le moins de bits significatifs restera à 0.Le résultat est que v && (v - 1) contient moins un ensemble de bits à 1 de v a.

Answer 2

La soustraction d'un 1 bit à partir d'un 0 peu de tours qui peu dans un 1 et provoque l'emprunter à partir de la prochaine peu vers la gauche, résultant en une soustraction 1 il y a ainsi.Cela continue en cascade vers la gauche jusqu'à ce que vous atteignez un 1 bits, où la soustraction 1 à partir de 1 est 0.À ce stade, la soustraction est fini.Vous avez converti tous les 0 en 1 du premier ensemble de bits, et converti que peu de 1 pour 0.

Lorsque vous and le avant et après les valeurs de la before a de zéros à droite du premier bit et l' after a un zéro à peu.Depuis rien anded avec zéro est zéro, vous gardez tous les zéros de la valeur d'origine et de définir le bit à zéro ainsi.