Compter les bits, nombre manquant et inversion des bits

Le problème de comptage des bits (LeetCode 338) demande, étant donné n, de renvoyer un tableau ans de taille n+1 dans lequel ans[i] est le nombre de bits à 1 de i. L'approche naïve prend O(n log n) : compter individuellement les bits de chaque nombre. L'approche par DP prend O(n) en exploitant the relation entre i et sa moitié ou son bit positionné de poids faible.

Deux observations clés alimentent the DP : (1) i >> 1 supprime le bit de poids faible, donc bits[i] = bits[i >> 1] + (i & 1). (2) Effacement du bit positionné de poids faible : bits[i] = bits[i & (i-1)] + 1. Les deux méthodes donnent un temps d'exécution de O(n) et un espace de O(n) pour le tableau de sortie.

Pour la récurrence par décalage à droite dp[i] = dp[i >> 1] + (i & 1) : la division par 2, c'est-à-dire le décalage à droite, supprime le dernier bit. Si ce dernier bit valait 1, le compteur augmente de 1 ; s'il valait 0, il ne change pas. Ainsi, bits[i] = bits[i // 2] + (i modulo 2).

Pour la récurrence fondée sur le bit positionné de poids faible dp[i] = dp[i & (i-1)] + 1 : i & (i-1) efface le bit 1 le plus à droite, et possède donc un bit positionné de moins que i. Le compteur est donc égal au compteur de cette valeur réduite, plus 1. Les deux récurrences traitent i dans l'ordre croissant, de sorte que les sous-problèmes plus petits sont toujours résolus en premier.

Le problème du nombre manquant (LeetCode 268) fournit un tableau de n nombres distincts dans [0, n], dont exactly un est manquant. L'approche par XOR consiste à effectuer un XOR entre tous les indices de 0 à n et toutes les valeurs du tableau. Les paires s'annulent et il ne reste que le nombre manquant. L'approche par somme utilise expected = n*(n+1)//2, puis renvoie expected - sum(nums).

Les deux approches prennent O(n) en temps et O(1) en espace. L'approche par XOR est plus robuste dans les langages utilisant des entiers de largeur fixe, car elle évite un éventuel dépassement de capacité. En Python, les deux fonctionnent correctement puisque les entiers ont une précision arbitraire.

Le problème d'inversion des bits (LeetCode 190) vous demande d'inverser la représentation binaire d'un entier non signé de 32 bits. L'approche itérative consiste à traiter chacun des 32 bits de l'entrée de droite à gauche, en les plaçant de gauche à droite dans la sortie. À chaque itération, extrayez le bit le plus à droite avec n & 1, décalez la sortie vers la gauche pour créer de la place, effectuez un OR avec le bit, puis décalez n vers la droite.

Après 32 itérations, l'entier de sortie contient les 32 bits de n dans l'ordre inversé. Cela prend O(32) = O(1) par appel, ou O(1) amorti avec une mise en cache pour les appels répétés sur des blocs de 8 bits.

Une approche plus rapide en O(log 32) = O(1) inverse les bits à l'aide d'un échange par diviser pour régner. Commencez par échanger les bits adjacents, puis les groupes adjacents de 2 bits, puis les groupes de 4 bits, et ainsi de suite. À chaque niveau d'échange, utilisez des masques pour séparer les groupes alternés et des décalages pour les entrelacer. Après 5 échanges, les 32 bits sont inversés.

Cette approche utilise un nombre fixe d'opérations en O(1), quelle que soit l'entrée, et elle est utilisée dans les implémentations matérielles. Les masques sont des constantes : 0x55555555 (motif alterné 01), 0x33333333 (motif alterné 0011), 0x0f0f0f0f (motif alterné 00001111), etc.

Le problème du nombre de bits à 1 (LeetCode 191) demande le poids de Hamming, c'est-à-dire le nombre de bits à 1, d'un entier non signé. Trois approches offrent des compromis différents : la boucle naïve (O(32)), la méthode de Brian Kernighan (O(k), où k est le nombre de bits positionnés) et la méthode intégrée de Python n.bit_count() (3.10 ou version ultérieure).

La méthode de Brian Kernighan est privilégiée lors des entretiens, car elle démontre la compréhension de l'astuce n & (n-1). Chaque itération supprime le bit positionné de poids faible, de sorte que la boucle s'exécute exactement autant de fois qu'il y a de bits à 1 — bien plus rapidement qu'un parcours complet des 32 bits pour les entiers peu denses.

Vous devez parfois compter rapidement les bits à 1 dans une plage [l, r]. Construisez une somme préfixe des bits positionnés pour 0..n : prefix[i] = prefix[i-1] + bin(i).count('1'). Le nombre de bits à 1 dans la plage [l, r] est alors prefix[r] - prefix[l-1]. Cela permet d'effectuer des requêtes sur une plage en O(1) après un prétraitement en O(n).

Cette technique se généralise à tout agrégat fondé sur les bits dans une plage. Par exemple, pour compter les nombres de [l, r] ayant un nombre pair de bits positionnés, utilisez la même technique de préfixes avec une fonction d'accumulation différente.

En Python, les entiers sont signés et leur largeur est arbitraire. Lors de l'inversion des bits pour le problème de LeetCode, nous devons traiter l'entrée comme un entier non signé de 32 bits. Appliquez le masque & 0xFFFFFFFF à l'entrée avant le traitement afin de ne prendre en compte que 32 bits. La sortie doit également être un entier non signé de 32 bits, donc non négatif.

Si l'on vous fournit un entier Python potentiellement négatif, au sens du complément à deux, appliquez d'abord & 0xFFFFFFFF pour obtenir sa représentation non signée sur 32 bits, puis inversez ses bits. Le résultat est toujours un entier non négatif compris entre 0 et 2^32 - 1.

Le problème du comptage des bits révèle un schéma général de la DP sur les bits : si vous connaissez la réponse pour une version plus petite de i, vous pouvez la calculer pour i à l'aide d'une opération sur les bits en temps constant. Ce schéma se généralise à d'autres problèmes de comptage des bits, comme compter les nombres ayant exactement k bits positionnés dans [0, n] à l'aide d'une énumération binaire, ou trouver la plus grande puissance de deux qui divise chaque nombre.

Autre observation utile : le nombre de bits positionnés de i suit un motif répétitif dans chaque intervalle correspondant à une puissance de deux. Le motif pour [2^k, 2^(k+1) - 1] est identique à celui de [0, 2^k - 1], chaque valeur étant augmentée de 1, car le bit k est toujours positionné dans cet intervalle.

De nombreux problèmes d'entretien combinent le comptage des bits, la logique des nombres manquants et l'inversion des bits en une seule question. Par exemple : étant donné un tableau dont les éléments sont des entiers sur n bits et dont l'un est manquant, trouvez la valeur manquante. Autre exemple : étant donné un flux de nombres de bits, reconstituez l'entier manquant. Ces problèmes exigent de reconnaître quelle sous-technique appliquer.

Entraînez-vous à établir une carte mentale : si un problème mentionne la recherche d'éléments manquants, pensez au XOR ou à la somme. S'il demande de « compter efficacement les bits à 1 », pensez à Kernighan ou à la DP. S'il demande d'« inverser les bits », pensez à l'approche itérative ou à celle de diviser pour régner. Ce sont les trois outils fondamentaux de la manipulation des bits lors des entretiens.

Pour les appels répétés à l'inversion des bits, par exemple dans une simulation matérielle, mettez en cache les résultats pour des blocs de 8 bits. Comme chaque octet ne peut prendre que 256 valeurs, précalculez l'octet inversé pour chaque valeur de 0 à 255. Pour inverser un entier de 32 bits, divisez-le en quatre blocs de 8 bits, inversez chacun d'eux, puis réassemblez-les dans l'ordre inverse.

Cela ramène chaque appel à quatre accès à une table et à des opérations sur les bits — bien plus rapide qu'une boucle de 32 itérations pour le traitement en masse. Le cache est construit une seule fois en O(256 × 8), puis réutilisé pour tous les appels suivants en O(1).

Évaluez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation — abordés dans cette leçon.

Dans cette leçon, vous avez appris que le comptage des bits utilise la DP avec dp[i] = dp[i >> 1] + (i & 1) ou dp[i] = dp[i & (i-1)] + 1, pour un temps d'exécution de O(n), que le nombre manquant se résout en O(n)/O(1) en effectuant un XOR entre tous les indices et toutes les valeurs, ou en utilisant la formule de somme arithmétique, et que l'inversion de 32 bits s'effectue de manière itérative en O(32) ou avec la technique de masques par diviser pour régner. Nous allons ensuite étudier les piles monotones, en commençant par l'invariant croissant ou décroissant et les requêtes sur l'élément supérieur suivant.