Poids de marteau - Hamming weight

Le poids de Hamming d'une chaîne est le nombre de symboles qui sont différents du symbole zéro de l' alphabet utilisé. Elle est donc équivalente à la distance de Hamming à partir de la chaîne entièrement nulle de même longueur. Pour le cas le plus typique, une chaîne de bits , c'est le nombre de 1 dans la chaîne, ou la somme des chiffres de la représentation binaire d'un nombre donné et de la norme ℓ ₁ d'un vecteur de bits. Dans ce cas binaire, il est également appelé population count , popcount , sideways sum ou bit summation .

Historique et utilisation

Le poids de Hamming est nommé d'après Richard Hamming bien qu'il n'ait pas été à l'origine de la notion. Le poids de Hamming des nombres binaires était déjà utilisé en 1899 par James WL Glaisher pour donner une formule pour le nombre de coefficients binomiaux impairs dans une seule rangée du triangle de Pascal . Irving S. Reed a introduit un concept, équivalent au poids de Hamming dans le cas binaire, en 1954.

Poids Hamming est utilisé dans plusieurs disciplines , y compris la théorie de l' information , la théorie du codage et la cryptographie . Exemples d'applications du poids Hamming :

• Dans l' exponentiation modulaire par élévation au carré , le nombre de multiplications modulaires requises pour un exposant e est log ₂ e + poids( e ). C'est la raison pour laquelle la valeur de clé publique e utilisée dans RSA est généralement choisie pour être un nombre de faible poids de Hamming.
• Le poids de Hamming détermine les longueurs de chemin entre les nœuds dans les tables de hachage distribuées Chord .
• Les recherches IrisCode dans les bases de données biométriques sont généralement implémentées en calculant la distance de Hamming à chaque enregistrement stocké.
• Dans les programmes d' échecs informatiques utilisant une représentation bitboard , le poids de Hamming d'un bitboard donne le nombre de pièces d'un type donné restant dans le jeu, ou le nombre de cases de l'échiquier contrôlées par les pièces d'un joueur, et est donc un terme important. à la valeur d'un poste.
• Le poids de Hamming peut être utilisé pour calculer efficacement le premier ensemble trouvé en utilisant l'identité ffs(x) = pop(x ^ (x - 1)). Ceci est utile sur les plates-formes telles que SPARC qui ont des instructions matérielles de poids Hamming mais aucun matériel ne trouve les premières instructions définies.
• L'opération de poids de Hamming peut être interprétée comme une conversion du système de numération unaire en nombres binaires .
• Dans la mise en œuvre de certaines structures de données succinctes comme les vecteurs de bits et les arbres d'ondelettes .

Mise en œuvre efficace

Le nombre de population d'une chaîne de bits est souvent nécessaire dans la cryptographie et d'autres applications. La distance de Hamming de deux mots A et B peut être calculée comme le poids de Hamming de A x ou B .

Le problème de sa mise en œuvre efficace a été largement étudié. Une seule opération pour le calcul, ou des opérations parallèles sur des vecteurs de bits sont disponibles sur certains processeurs . Pour les processeurs dépourvus de ces fonctionnalités, les meilleures solutions connues sont basées sur l'ajout de comptes dans un modèle d'arbre. Par exemple, pour compter le nombre de 1 bits dans le nombre binaire de 16 bits a = 0110 1100 1011 1010, ces opérations peuvent être effectuées :

Ici, les opérations sont comme dans le langage de programmation C , donc cela X >> Ysignifie décaler X vers la droite de Y bits, X & Y signifie le ET au niveau du bit de X et Y, et + est une addition ordinaire. Les meilleurs algorithmes connus pour ce problème sont basés sur le concept illustré ci-dessus et sont donnés ici :

//types and constants used in the functions below
//uint64_t is an unsigned 64-bit integer variable type (defined in C99 version of C language)
const uint64_t m1  = 0x5555555555555555; //binary: 0101...
const uint64_t m2  = 0x3333333333333333; //binary: 00110011..
const uint64_t m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64_t m8  = 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
const uint64_t m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64_t m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...

//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//This algorithm uses 24 arithmetic operations (shift, add, and).
int popcount64a(uint64_t x)
{
    x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits 
    x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits 
    x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits 
    x = (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits 
    x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits 
    x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits 
    return x;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with slow multiplication.
//This algorithm uses 17 arithmetic operations.
int popcount64b(uint64_t x)
{
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    x += x >>  8;  //put count of each 16 bits into their lowest 8 bits
    x += x >> 16;  //put count of each 32 bits into their lowest 8 bits
    x += x >> 32;  //put count of each 64 bits into their lowest 8 bits
    return x & 0x7f;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with fast multiplication.
//This algorithm uses 12 arithmetic operations, one of which is a multiply.
int popcount64c(uint64_t x)
{
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    return (x * h01) >> 56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}

Les implémentations ci-dessus ont le meilleur comportement dans le pire des cas de tous les algorithmes connus. Cependant, lorsqu'une valeur est censée avoir quelques bits différents de zéro, il peut être plus efficace d'utiliser des algorithmes qui comptent ces bits un par un. Comme Wegner l'a décrit en 1960, l' ET au niveau du bit de x avec x  − 1 ne diffère de x que par la mise à zéro du bit non nul le moins significatif : la soustraction de 1 change la chaîne la plus à droite de 0 à 1 et le 1 le plus à droite à 0. Si x avait à l'origine n bits qui étaient 1, puis après seulement n itérations de cette opération, x sera réduit à zéro. L'implémentation suivante est basée sur ce principe.

//This is better when most bits in x are 0
//This algorithm works the same for all data sizes.
//This algorithm uses 3 arithmetic operations and 1 comparison/branch per "1" bit in x.
int popcount64d(uint64_t x)
{
    int count;
    for (count=0; x; count++)
        x &= x - 1;
    return count;
}

Si une plus grande utilisation de la mémoire est autorisée, nous pouvons calculer le poids de Hamming plus rapidement que les méthodes ci-dessus. Avec une mémoire illimitée, nous pourrions simplement créer une grande table de recherche du poids de Hamming de chaque entier de 64 bits. Si nous pouvons stocker une table de recherche de la fonction de Hamming de chaque entier de 16 bits, nous pouvons procéder comme suit pour calculer le poids de Hamming de chaque entier de 32 bits.

static uint8_t wordbits[65536] = { /* bitcounts of integers 0 through 65535, inclusive */ };
//This algorithm uses 3 arithmetic operations and 2 memory reads.
int popcount32e(uint32_t x)
{
    return wordbits[x & 0xFFFF] + wordbits[x >> 16];
}

//Optionally, the wordbits[] table could be filled using this function
int popcount32e_init(void)
{
    uint32_t i;
    uint16_t x;
    int count;
    for (i=0; i <= 0xFFFF; i++)
    {
        x = i;
        for (count=0; x; count++) // borrowed from popcount64d() above
            x &= x - 1;
        wordbits[i] = count;
    }
}

Muła et al. ont montré qu'une version vectorisée de popcount64b peut s'exécuter plus rapidement que des instructions dédiées (par exemple, popcnt sur les processeurs x64).

Poids minimum

Dans le codage correcteur d'erreurs , le poids de Hamming minimum, communément appelé poids minimum w _min d'un code, est le poids du mot de code non nul de poids le plus faible. Le poids w d'un mot de code est le nombre de 1 dans le mot. Par exemple, le mot 11001010 a un poids de 4.

Dans un code de bloc linéaire, le poids minimum est également la distance de Hamming minimum ( d _min ) et définit la capacité de correction d'erreur du code. Si w _min  =  n , alors d _min  =  n et le code corrigera jusqu'à d _min /2 erreurs.

Support linguistique

Certains compilateurs C fournissent des fonctions intrinsèques qui fournissent des fonctionnalités de comptage de bits. Par exemple, GCC (depuis la version 3.4 en avril 2004) inclut une fonction intégrée __builtin_popcountqui utilisera une instruction de processeur si disponible ou une implémentation de bibliothèque efficace dans le cas contraire. LLVM-GCC a inclus cette fonction depuis la version 1.5 en juin 2005.

Dans C++ STL , la structure de données de tableau de bits bitseta une count()méthode qui compte le nombre de bits définis. En C++20 , un nouvel en-tête a <bit>été ajouté, contenant des fonctions std::popcountet std::has_single_bit, prenant des arguments de types entiers non signés.

En Java, la structure de données de tableau de bits extensible BitSeta une BitSet.cardinality()méthode qui compte le nombre de bits définis. De plus, il existe des fonctions Integer.bitCount(int)et Long.bitCount(long)pour compter les bits dans les entiers primitifs 32 bits et 64 bits, respectivement. En outre, la BigIntegerclasse d'entiers de précision arbitraire possède également une BigInteger.bitCount()méthode qui compte les bits.

En Python , le inttype a une bit_count()méthode pour compter le nombre de bits définis. Cette fonctionnalité est nouvelle dans Python 3.10, dont la sortie est prévue en 2021.

En Common Lisp , la fonction logcount, étant donné un entier non négatif, renvoie le nombre de 1 bits. (Pour les entiers négatifs, il renvoie le nombre de 0 bits en notation complémentaire à 2.) Dans les deux cas, l'entier peut être un BIGNUM.

À partir de GHC 7.4, le package de base Haskell a une popCountfonction disponible sur tous les types qui sont des instances de la Bitsclasse (disponible à partir du Data.Bitsmodule).

La version MySQL du langage SQL fournit BIT_COUNT()une fonction standard.

Fortran 2008 a la fonction élémentaire intrinsèque standard popcntrenvoyant le nombre de bits non nuls dans un entier (ou un tableau d'entiers).

Certaines calculatrices de poche scientifiques programmables disposent de commandes spéciales pour calculer le nombre de bits définis, par exemple #Bsur le HP-16C et le WP 43S , #BITSou BITSUMsur les émulateurs HP-16C, et nBITSsur le WP 34S .

FreePascal implémente popcnt depuis la version 3.0.

Prise en charge du processeur

• L' ordinateur IBM STRETCH dans les années 1960 a calculé le nombre de bits définis ainsi que le nombre de zéros non significatifs en tant que sous-produit de toutes les opérations logiques.
• Les superordinateurs Cray comportaient très tôt une instruction machine de comptage de population , qui aurait été spécifiquement demandée par l' Agence de sécurité nationale du gouvernement américain pour les applications de cryptanalyse .
• Les machines des séries 6000 et Cyber ​​70/170 de Control Data Corporation (CDC) comprenaient une instruction de comptage de population ; dans COMPASS , cette instruction était codée comme CXi.
• L'architecture SPARC version 9 64 bits définit une POPCinstruction, mais la plupart des implémentations ne l'implémentent pas, ce qui nécessite qu'elle soit émulée par le système d'exploitation.
• L'ordinateur modèle MMIX de Donald Knuth qui va remplacer MIX dans son livre The Art of Computer Programming a une SADDinstruction depuis 1999. SADD a,b,ccompte tous les bits qui sont 1 dans b et 0 dans c et écrit le résultat dans a.
• Compaq s » Alpha 21264A , sorti en 1999, a été la première conception du processeur série Alpha qui avait l'extension de comptage ( CIX).
• Analog Devices de Blackfin processeurs disposent l' ONESinstruction d'effectuer un comptage de la population de 32 bits.
• L' architecture de Barcelone d' AMD a introduit l' ISA de manipulation de bits avancée (ABM) en introduisant l' POPCNTinstruction dans le cadre des extensions SSE4a en 2007.
• Les processeurs Intel Core ont introduit une POPCNTinstruction avec l' extension du jeu d'instructions SSE4.2 , d'abord disponible dans un processeur Core i7 basé sur Nehalem , sorti en novembre 2008.
• L' architecture ARM a introduit l' VCNTinstruction dans le cadre des extensions Advanced SIMD ( NEON ).
• L' architecture RISC-V a introduit l' PCNTinstruction dans le cadre de l'extension Bit Manipulation (B).

Voir également

• Complément à deux
• Caractères k les plus fréquents
• Déployez-vous

Les références

Lectures complémentaires

• Schroeppel, Richard C. ; Orman, Hilarie K. (1972-02-29). "compilation". HAKMEM . Par Beeler, Michael ; Gosper, Ralph William ; Schroeppel, Richard C. (rapport). Laboratoire d'intelligence artificielle , Massachusetts Institute of Technology , Cambridge, Massachusetts, États-Unis. MIT AI Mémo 239.( Article 169 : Code d'assemblage de comptage de population pour le PDP/6-10.)

Liens externes

• Algorithmes magiques agrégés . Décompte de population optimisé et autres algorithmes expliqués avec un exemple de code.
• Bit Twiddling Hacks Plusieurs algorithmes avec code pour le comptage de bits.
• Nécessaire et suffisant - par Damien Wintour - Possède du code en C# pour diverses implémentations de Hamming Weight.
• Meilleur algorithme pour compter le nombre de bits définis dans un entier de 32 bits ? - Stackoverflow