Quels sont les astuces courantes de manipulation de bits ?

Question

Accepted Answer

**Bit manipulation** opère directement sur la représentation binaire des entiers en utilisant AND, OR, XOR, NOT et les décalages. Elle permet des opérations compactes, sans branchement et très rapides. ## Opérations principales ```python x & 1 # is x odd? (lowest bit) x << 1 # multiply by 2 x >> 1 # integer divide by 2 x & (1 << k) # is bit k set? x | (1 << k) # set bit k x & ~(1 << k) # clear bit k x ^ (1 << k) # toggle bit k ``` ## Astuces utiles ```python x & (x - 1) # clears the lowest set bit x & (x - 1) == 0 # is x a power of two? (x>0) x & (-x) # isolates the lowest set bit bin(x).count('1') # popcount (number of set bits) ``` ## Exemple : trouver le nombre unique (astuce XOR) ```python def single_number(nums): result = 0 for n in nums: result ^= n # pairs cancel: a ^ a == 0 return result # the lone unpaired value remains single_number([4, 1, 2, 1, 2]) # -> 4 ``` ## Complexité Les opérations bit sont O(1) ; le scan XOR ci-dessus est **O(n) temps, O(1) espace**. ## Quand l'utiliser / pièges Utilisez pour les **bitmasks** (énumération de sous-ensembles, DP sur états), les drapeaux, les mathématiques rapides et le code bas niveau/embarqué. Attention aux bits de signe, au comportement des décalages spécifiques au langage et à la lisibilité — commentez les astuces non évidentes. ## Pourquoi c'est important La manipulation de bits produit des solutions élégantes O(1)-espace (comme l'astuce XOR single-number) qui impressionnent aux entretiens. Le bitmask DP rend traçables de nombreux problèmes d'espace d'états combinatoires. C'est essentiel en systèmes, graphisme, compression et code sensible aux performances où chaque cycle compte.