Publié · en amélioration
Algorithm
La manipulation de bits traite les entiers comme des chiffres binaires et utilise AND, OR, XOR et décalages pour gérer ensembles, drapeaux et DP par masques.
La manipulation de bits consiste à voir un entier comme une suite de 0 et de 1 et à utiliser AND, OR, XOR, NOT et les décalages pour lire, activer, effacer ou inverser des bits précis. Les ordinateurs stockent les entiers en binaire et les négatifs en complément à deux : chacune de ces opérations correspond donc en général à une seule instruction du processeur. Une expression courte comme x & -x (le bit à 1 le plus faible) ou x & (x - 1) (ce bit effacé) remplace souvent une boucle entière.
Le sujet compte parce qu'un seul entier peut représenter un ensemble d'une vingtaine d'éléments, ce qui permet de parcourir tous ses sous-ensembles et d'utiliser des ensembles comme états en programmation dynamique par masques. Les entretiens techniques proposent souvent l'énumération de sous-ensembles, les propriétés de XOR et le popcount, et en production les bits servent aux droits de fichiers, aux feature flags, au calcul de sous-réseaux, aux tables de hachage et aux index bitmap. Les règles varient selon le langage : les entiers Python sont illimités, JavaScript convertit en 32 bits et propose >>>, Java a aussi >>>, et en C++ on préfère les types non signés pour les masques.
Commencez par convertir des nombres en binaire et en complément à deux à la main. Entraînez-vous ensuite aux quatre opérations sur un bit (activer, effacer, inverser, tester) et affichez tous les sous-ensembles en faisant varier un masque de 0 à 2^n - 1. Passez ensuite à l'énumération des sous-masques et aux problèmes de DP par masques, comme l'affectation de tâches ou le voyageur de commerce, puis vérifiez la largeur des entiers et les règles de décalage de vos langages.
Un nombre négatif s'obtient en inversant tous les bits puis en ajoutant 1. Le décalage à gauche multiplie par 2, le décalage à droite divise par 2, et les langages distinguent décalage arithmétique et logique.
Avec le masque 1 << i, OR active le bit i, AND NOT l'efface et XOR l'inverse. x & -x isole le bit à 1 le plus faible et x & (x - 1) le supprime.
Les sous-ensembles de n éléments correspondent un à un aux entiers de 0 à 2^n - 1 ; union, intersection et différence ne coûtent qu'une opération bit à bit.
On compte les bits à 1 en répétant x &= x - 1 ou avec une fonction intégrée. Comme a ^ a = 0, XOR retrouve la valeur sans paire et donne distances de Hamming et codes de Gray.
popcount compte les bits à 1 en effaçant le plus faible avec x &= x - 1 jusqu'à ce qu'il n'en reste aucun. subsets fait varier un masque de 0 à 2^n - 1 et retient les éléments dont le bit est à 1, ce qui produit tous les sous-ensembles. La dernière ligne montre 12 & -12 = 4 (le bit à 1 le plus faible), 12 & 11 = 8 (ce bit effacé) et x ^ x = 0. Lancez-le avec python bit_manipulation.py.
bit_manipulation.py
def popcount(x: int) -> int:
count = 0
while x:
x &= x - 1 # clear the lowest set bit
count += 1
return count
def subsets(items):
n = len(items)
for mask in range(1 << n):
yield mask, [items[i] for i in range(n) if (mask >> i) & 1]
for mask, chosen in subsets(["a", "b", "c"]):
print(format(mask, "03b"), popcount(mask), chosen)
x = 12
print(x & -x, x & (x - 1), x ^ x) # 4 8 0
python bit_manipulation.pySix chapitres pour aller de l'installation aux notions essentielles de Manipulation de bits.
Posez vos questions, partagez votre expérience et échangez vos avis sur Manipulation de bits.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.