Comment manipuler des bits en programmation pour optimiser le comptage de critères multiples

Cette vidéo explique comment utiliser les bitmaps et les portes logiques pour compter rapidement des éléments satisfaisant plusieurs critères, une technique clé en programmation pour l'optimisation.

Traditionnellement, pour trouver combien de personnes sont à la fois abonnées et aiment la pizza, il faut parcourir toute la liste (N étapes). Avec des bitmaps, chaque critère est représenté par une suite de bits (1 pour vrai, 0 pour faux). En appliquant la porte logique ET entre les deux bitmaps, on obtient une nouvelle suite où seuls les 1 correspondent aux personnes remplissant les deux conditions. Il ne reste plus qu'à compter ces 1.

Pour compter efficacement les 1 sans parcourir chaque bit, on utilise une astuce binaire : on duplique la bitmap, on soustrait 1, puis on applique la porte ET entre l'original et le résultat. Cette opération élimine le 1 le plus à droite. En répétant cette étape jusqu'à obtenir 0, le nombre d'itérations correspond exactement au nombre de 1 initiaux.

Exemple : Si la bitmap combinée est 1011 (3 personnes valides), on compte les 1. Au lieu de vérifier 4 bits, on fait 3 opérations de suppression du dernier 1. Si N est grand (millions de sondés) et K petit (peu de correspondances), cette méthode est bien plus rapide que le parcours linéaire.