Le problème est connu de tous ou presque: nous avons un vecteur de bits, comme un ensemble de fanions, et nous souhaitons pour chacun effectuer une action prévue à l'avance. Alors commençons naïvement.

for
(
    unsigned it = 0;
    it < sizeof (uin32_t) * 8;
    ++it
)
{
    if ((flags >> it) & 1)
        // process flag
}

Inutile de se demander si cette solution est élégante ou efficace, c'est juste naïf. Bien sûr, on peut tenter d'optimiser un peu tout cela tout en restant portable. Voici un autre exemple rapide en jouant entre autres sur la condition d'arrêt.

for (it = flags;it;it >>= 1)
{
    if (it & 1)
        // process flag
}

Enfin, une autre méthode consiste simplement à se plonger dans la documentation de sa machine pour trouver votre bonheur; en effet, les opérations sur les bits étant la base de l'informatique, celles-ci sont bien souvent inclues de base. Ainsi, sur x86, on pourra utiliser par exemple les instructions bsf et btr.

Maintenant, jouons un peu. Tout d'abord, comment trouver le premier bit à 1 dans un nombre. Pour cela, utilisons une propriété magique du complément à deux.

printf ("0x%08x\n", flags & - flags);

Nous effectuons un et logique entre nos fanions et leur représentation en complément à deux calculée grâce à l'opérateur - ici unaire avec la précédence. Pour ceux qui sont fainéant, le résultat est un nombre dont le seul bit à 1 est le bit le plus à droite dans nos fanions.

Maintenant, il reste à trouver ce bit sans parcourir le résultat précédent. C'est là que nous utilisons à nouveau un petit peu de magie avec les séries de De Bruijn, ces mêmes séries qui servent à tester rapidement toutes les combinaisons sur les digicodes mal conçus. Celles-ci servent en effet à construire pour un alphabet donné, par exemple binaire, la plus longue suite où chaque séquence de longueur n apparaît une et une seule fois. La suite est assez simple; la multiplication par une puissance de deux étant en binaire un décalage à gauche, effectuer la multiplication de notre résultat précédent par une suite bien choisi permet de trouver un résultat unique pour chaque position. Il ne reste alors plus qu'à faire correspondre tout cela avec une table de correspondance et nous obtenons notre méthode.

Le programme suivant donne un exemple sur 32 bits à l'aide de la suite B(2,5). En pratique, la table peut être obtenue rapidement à l'aide des outils awk et sort.

const unsigned int decode_debruijn [32] =
{
     0,  1, 10,  2, 11, 14, 22,  3,
    30, 12, 15, 17, 19, 23, 26,  4,
    31,  9, 13, 21, 29, 16, 18, 25,
     8, 20, 28, 24,  7, 27,  6,  5
};
unsigned it;
for (it = 1; it != 0; it <<= 1)
    printf ("%02i %02i\n", (it * 0x07c4acddu) >> 27, decode_debruijn[(it * 0x07c4acddu) >> 27]);

A quoi cette méthode peut bien servir? A priori, celle-ci semble efficace et élégante. En pratique, la recherche d'un bit se fait à temps constant, ce qui la rend toute indiquée pour pouvoir être utilisée par exemple dans des pilotes.

Références

partie I