Les opérations bit à bit/Le poids de Hamming

Il arrive qu'on ait besoin de compter les bits d'un certain nombre. Par exemple, certaines application en cryptographie ont besoin de savoir combien de bits sont à 1 dans un nombre. Même chose pour la détection ou correction d'erreurs de transmission entre deux composants électroniques. Certaines de ces opérations, comme le poids de Hamming, se calculent fort bien avec des opérations bit à bit. Le poids de Hamming d'un nombre est le nombre de ses bits qui sont à 1. Ce calcul est souvent effectué quand on cherche à vérifier l'intégrité de données transmises ou stockées sur un support peu fiable et il est à la base d'un grand nombre de code de détection ou de correction d'erreurs usuels. Ce calcul est tellement fréquent que certains processeur disposent d'une instruction dédiée pour le calcul du poids de Hamming. Alors certes, ces architectures sont surtout des architectures anciennes, comme les SPARC, les CDC ou autres processeurs Cray. Mais à l'heure actuelle, les processeurs x86 possèdent une telle instruction, dans leurs extension SSE 4.1. Même chose pour les architectures ARM et Power PC. Ce calcul, s'il n'est pas effectué par le matériel, est pris en charge par un bout de code souvent rudimentaire. Si quelques compilateurs fournissent ainsi des opérateurs spécialisés pour faire ce calcul, le poids de Hamming n'est pas implémenté par la plupart des langages de programmation. Il faut dire que son utilisation essentiellement bas-niveau fait que la majorité des langages de haut-niveau actuel n'en a pas l'utilité.

Méthode itérative

Pour faire ce calcul, on pourrait penser naïvement à utiliser une simple boucle pour additionner les bits un par un. Le nombre d'itération est alors égal au nombre de bits du nombre, peu importe le nombre de 1. Le code, écrit en C, devrait être le suivant, pour un entier 32 bits :

unsigned HammingWeight (unsigned x)
{
    unsigned HammingWeight = 0 ;
    while (x > 0)
    {
        HammingWeight += x & 1 ;
        x = x >> 1 ;
    }
    return HammingWeight ;
}

Une autre version, un peu plus rapide, se base sur une boucle similaire. Elle consiste à mettre à 0 le 1 de poids faible (celui le plus à droite) à chaque tour de boucle. Pour cela, il suffit d'appliquer l'expression $x.(x-1)$, dont on expliquera le fonctionnement dans quelques chapitres. En faisant cela, à chaque itération, le poids de Hamming diminue donc de 1. Il suffit de compter le nombre d'itération avant d'arriver à 0 pour déterminer le poids de Hamming. Le nombre d'itération est alors plus faible qu'avec le code précédent : le nombre d'itération passe du nombre de bits total au nombre de bits à 1. Le nombre d’itérations dans le pire des cas est alors le même qu'avec le code précédent, mais le nombre moyen ou dans le meilleur des cas diminue fortement. Le code obtenu est alors le suivant :

unsigned HammingWeight (unsigned x)
{
    unsigned HammingWeight = 0 ;
    while (x > 0)
    {
        x = x & (x - 1) ;
        HammingWeight += 1 ;
    }
    return HammingWeight ;
}

Méthode par pré-calcul

On peut aussi faire le calcul octet par octet. Pour cela, il suffit d'utiliser un tableau où la case d'indice i contient le poids de Hamming de i. Il suffit ensuite d'utiliser ce tableau dans une boucle pour faire l'addition octet par octet. On peut même dérouler totalement la boucle, si l'on connait exactement le nombre d'octets de l'entier à traiter. Cette technique a cependant le défaut d'effectuer des accès à la mémoire, qui sont des opérations assez lentes.

unsigned HammingWeight (unsigned x)
{ 
    static char table[256] = { 0, 1, 1, 2, 1, 2, 2, ... , 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 } ; // Tableau qui contient les poids de Hamming de chaque octet

    FirstByte = x & 0xFF ;
    SecondByte = (x >> 8) & 0xFF ;
    ThirdByte = (x >> 16) & 0xFF
    ForthByte = (x >> 24) & 0xFF

    return table[FirstByte] + table[SecondByte] + table[ThirdByte] + table[ForthByte] ;
}

Méthode récursive (diviser pour régner)

Calcul récursif du poids de Hamming.

Une autre solution effectue ce calcul avec une fonction récursive, avec une approche par dichotomie. En découpant un nombre en deux morceaux, on sait que son poids de Hamming est égal à la somme des poids de Hamming des deux morceaux. Et le même raisonnement s'applique sur chaque morceau. Au final, les morceaux sont de plus en plus petits, jusqu'à obtenir des morceaux de 1 bit. Dans ce cas, je sais que la population count d'un morceau de 1 bit vaut 1 si le bit est à 1, et zéro s'il vaut zéro. En clair : la population count de 1 bit vaut… le bit en question. Cela signifie qu'il suffit d'additionner tous les bits du nombre pour obtenir le nombre de uns. Dans les deux cas, le code devrait donc faire le calcul en N cycles, N étant le nombre de bits du nombre. Mais il y a moyen de faire beaucoup plus rapide, avec un calcul en log(N) opérations ! Pour cela, il faut utiliser une méthode qui s'inspire de la méthode récursive, mais utilise des opérations bit à bit pour faire certains calculs en parallèle. La méthode en question est, à mon avis, le plus beau algorithme utilisant des opérations bit à bit au monde.

L’algorithme

Pour illustrer l'algorithme, nous allons prendre l'exemple d'un nombre sur 8 bits que nous noterons N. L'algorithme commence par grouper les bits du nombre par groupes de deux et les additionne dans deux variables. La première variable va stocker tous les bits à une position paire, les autres bits étant mis à zéro (...0x0x0x0x0x). L'autre variable va faire la même chose avec les bits en position impaire, mais décalé d'un rang vers la droite, histoire que les bits des deux variables soient sur la même colonne (...0x0x0x0x0x également). Les deux variables sont alors additionnées : variable 1 + variable2 >> 1.

La première étape effectue donc le calcul suivant :

• variable1 = N . 01010101
• variable2 = (N . 10101010) >> 1
• variable 1 + variable 2.

Au niveau de chaque paire de bits (00 ou 01) l'addition de la paire en position paire avec celle en position impaire donne le nombre de bits à 1 sans report de retenue au delà de la paire de bits.

Regardons en détail ce qui se passe sur les bits de N.

Variable	groupe de deux bits	groupe de deux bits	groupe de deux bits	groupe de deux bits
Nombre N	a7 a6	a5 a4	a3 a2	a1 a0
Variable1 0 a6 0 a4 0 a2 0 a0	0 a6	0 a4	0 a2	0 a0
Variable 2 >> 1	0 a7	0 a5	0 a3	0 a1
Variable 1 + Variable 2 >> 1	(a7 + a6)	(a5 + a4)	(a3 + a2)	(a1 + a0)

La seconde étape est similaire, si ce n'est qu'elle isole les groupes de deux bits créés à l'étape précédente deux à deux, et les additionne.

Variable	groupe de quatre bits	groupe de quatre bits
Opérande	(a7 + a6) (a5 + a4)	(a3 + a2) (a1 + a0)
Variable1	(a7 + a6) 00	(a3 + a2) 00
Variable 2 >> 2	00 (a5 + a4)	00 (a1 + a0)
Variable 1 + Variable 2 >> 2	(a7 + a6 + a5 + a4)	(a3 + a2 + a1 + a0)

Et on, poursuit ainsi de suite, jusqu'à obtenir la population count de notre nombre. Dans notre exemple, une troisième étape suffit pour obtenir le résultat.

Variable	groupe de huit bits
Opérande	(a7 + a6 + a5 + a4) (a3 + a2 + a1 + a0)
Variable1	0000 (a7 + a6 + a5 + a4)
Variable 2 >> 4	0000 (a3 + a2 + a1 + a0)
Variable 1 + Variable 2 >> 4	(a7 + a6 + a5 + a4 + a3 + a2 + a1 + a0)

Détermination des masques

L'algorithme commence par calculer des variables avec des groupes de bits en position paire et impaire, le reste des bits étant mis à 0. Il est évident que cela demande d'utiliser des masques pour mettre les bits inutiles à zéro. Dans le cas de la seconde variable, les bits doivent être décalés histoire d'être mis sur la même colonne que l'autre variable. On peut penser qu'il est naturel d'appliquer les masques avant des décalages, ce qui donne : variable1 = N . 01010101 et variable2 = N . 10101010. Dans ce cas, le calcul de variable2 et de variable1 ne s'effectuent pas avec les mêmes constantes. Ceci dit, il est aussi possible de faire le décalage de la seconde variable avant d'appliquer le masque. Dans ce cas, les masques des deux variables deviennent identiques. Pour le montrer, partons des calculs où le masque est appliqué avant le décalage :

• variable2 = (N . 10101010) >> 1
• variable2 = (N . 11001100) >> 2
• variable2 = (N . 11110000) >> 4

Vu que les décalages sont distributifs par rapport au AND, (a . b) >> n = (a >> n) . (b >> n), on obtient :

• variable2 = (N >> 1) . (10101010 >>1) = (N >> 1) . 01010101
• variable2 = (N >> 2) . (11001100 >>2) = (N >> 2) . 00110011
• variable2 = (N >> 3) . (11110000 >>4) = (N >> 3) . 00001111

Les constantes utilisées sont exactement les mêmes que celles utilisée dans le calcul de la première variable.

Cela a un avantage sur certaines architectures RISC où les constantes immédiates ont une taille limitée. En conséquence, si une constante dépasse cette taille, elle ne peut pas utiliser le mode d'adressage immédiat. À la place, la constante est placée dans la mémoire, et est chargée dans un registre à chaque utilisation. Le fait de réutiliser la même constante pour le calcul de variable1 et de variable2 permet ainsi de charger cette constante une seule fois, et la réutiliser depuis le registre lors du calcul de variable2. En utilisant deux constantes différentes, on aurait deux accès mémoire, ce qui aurait été bien plus lent.

Le code en C

Fort de ce qui a été dit précédemment, on trouve que le code de calcul du poids de Hamming est le suivant pour un entier de 32 bits :

unsigned HammingWeight (unsigned x)
{
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
    x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
    x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);

    return x ;
}

Il est possible de simplifier encore plus ce code, en supprimant quelques ET.

unsigned HammingWeight (unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}