Manipulation des bits - Bit manipulation

Pour d'autres utilisations, voir Manipulation .

À ne pas confondre avec Bit cogner .

La manipulation de bits est l'acte de manipuler algorithmiquement des bits ou d'autres éléments de données plus courts qu'un mot . Les tâches de programmation informatique qui nécessitent une manipulation de bits incluent le contrôle de périphérique de bas niveau, les algorithmes de détection et de correction d'erreurs , la compression de données , les algorithmes de cryptage et l' optimisation . Pour la plupart des autres tâches, les langages de programmation modernes permettent au programmeur de travailler directement avec des abstractions au lieu de bits qui représentent ces abstractions. Le code source qui manipule les bits utilise les opérations au niveau du bit : AND, OR, XOR, NOT, et éventuellement d'autres opérations analogues aux opérateurs booléens ; il y a aussi des décalages de bits et des opérations pour compter des uns et des zéros, trouver un ou zéro haut et bas, définir, réinitialiser et tester des bits, extraire et insérer des champs, masquer et des champs zéro, rassembler et disperser des bits vers et depuis des positions de bits ou des champs spécifiés . Les opérateurs arithmétiques entiers peuvent également effectuer des opérations sur les bits en conjonction avec les autres opérateurs.

La manipulation de bits, dans certains cas, peut éviter ou réduire le besoin de boucler sur une structure de données et peut donner des accélérations de plusieurs fois, car les manipulations de bits sont traitées en parallèle.

Terminologie

Le twiddling et le bit bashing sont souvent utilisés de manière interchangeable avec la manipulation de bits, mais se réfèrent parfois exclusivement à des manières ou à des utilisations intelligentes ou non évidentes de manipulation de bits, ou à des tâches fastidieuses ou difficiles de manipulation de données de contrôle de périphérique de bas niveau .

Le terme bit twiddling date des premiers matériels informatiques , où les opérateurs informatiques effectuaient des ajustements en peaufinant ou en manipulant les commandes informatiques. Au fur et à mesure que les langages de programmation informatique évoluaient, les programmeurs ont adopté le terme pour désigner toute manipulation de données impliquant un calcul au niveau du bit .

Fonctionnement au niveau du bit

Article principal: opération au niveau du bit

Une opération au niveau du bit opère sur un ou plusieurs modèles de bits ou nombres binaires au niveau de leurs bits individuels . Il s'agit d'une action primitive et rapide directement prise en charge par l' unité centrale de traitement (CPU) et est utilisée pour manipuler des valeurs pour des comparaisons et des calculs.

Sur la plupart des processeurs, la majorité des opérations au niveau du bit sont à cycle unique - sensiblement plus rapides que la division, la multiplication et les branches. Alors que les processeurs modernes effectuent généralement certaines opérations arithmétiques et logiques aussi rapidement que les opérations au niveau du bit en raison de leurs pipelines d'instructions plus longs et d'autres choix de conception architecturale , les opérations au niveau du bit utilisent généralement moins d'énergie en raison de l'utilisation réduite des ressources.

Exemple de manipulation de bits

Pour déterminer si un nombre est une puissance de deux, conceptuellement, nous pouvons effectuer à plusieurs reprises une division entière par deux jusqu'à ce que le nombre ne se divise pas par 2 de manière égale ; si le seul facteur restant est 1, le nombre d'origine était une puissance de 2. En utilisant des opérateurs binaires et logiques, il existe une expression simple qui renverra vrai (1) ou faux (0) : 

 bool isPowerOfTwo = (x != 0) && ((x & (x - 1)) == 0);

La deuxième méthode utilise le fait que les puissances de deux ont un et un seul bit défini dans leur représentation binaire : 

x         == 0...010...0
x-1       == 0...001...1
x & (x-1) == 0...000...0

Si le nombre n'est ni zéro ni une puissance de deux, il aura « 1 » à plusieurs endroits : 

x         == 0...1...010...0
x-1       == 0...1...001...1
x & (x-1) == 0...1...000...0

Si du code en langage assembleur en ligne est utilisé, une instruction qui compte le nombre de 1 ou de 0 dans l'opérande peut être disponible ; un opérande avec exactement un bit '1' est une puissance de 2. Cependant, une telle instruction peut avoir une latence plus importante que la méthode au niveau du bit ci-dessus.

Opérations de manipulation de bits

Voir aussi : Jeux d'instructions de manipulation de bits

Les processeurs ne fournissent généralement qu'un sous-ensemble des opérateurs binaires utiles. Les langages de programmation ne prennent pas directement en charge la plupart des opérations sur les bits, il faut donc utiliser des idiomes pour les coder. Le langage de programmation 'C', par exemple, ne fournit que des bits AND(&), OR(|), XOR(^) et NOT(~). Fortran fournit AND(.and.), OR (.or.), XOR (.neqv.) et EQV(.eqv.). Algol fournit un extrait et une insertion syntaxiques de champ de bits. Lorsque les langages fournissent des opérations sur les bits qui ne correspondent pas directement aux instructions matérielles, les compilateurs doivent synthétiser l'opération à partir des opérateurs disponibles.

Une opération sur les bits particulièrement utile consiste à compter les zéros non significatifs utilisés pour trouver le bit de poids fort d'un mot machine, bien qu'il puisse avoir des noms différents selon les architectures. Il n'y a pas d'idiome de langage de programmation simple, il doit donc être fourni par une routine de bibliothèque système ou intrinsèque du compilateur. Sans cet opérateur, il est très coûteux (voir Find first set#CLZ ) d'effectuer des opérations concernant le bit de poids fort d'un mot, en raison de la propagation asymétrique des opérations arithmétiques. Heureusement, la plupart des architectures de processeurs le proposent depuis le milieu des années 1980. Une opération d'accompagnement count ones , également appelée POPCOUNT, qui compte le nombre de bits définis dans un mot machine, est également généralement fournie en tant qu'opérateur matériel. Des opérations de bits plus simples telles que la définition de bits, la réinitialisation, le test et la bascule sont souvent fournies en tant qu'opérateurs matériels, mais sont facilement simulées si elles ne le sont pas - par exemple (SET R0, 1 ; LSHFT R0, i ; OR x, R0) définit le bit i dans l'opérande x.

Certaines des opérations binaires les plus utiles et les plus complexes qui doivent être codées comme des idiomes dans le langage de programmation et synthétisées par les compilateurs incluent :

  • effacer à partir de la position de bit spécifiée vers le haut (laisser la partie inférieure du mot)
  • effacer à partir de la position de bit spécifiée vers le bas (laisser la partie supérieure du mot)
  • masquer du bit bas vers le bas (effacer le mot inférieur)
  • masque du bit haut vers le haut (effacer le mot inférieur)
  • extrait de champ de bits
  • insertion de champ de bits
  • opérations de dispersion/regroupement de champs de bits qui distribuent des parties contiguës d'un champ de bits sur un mot machine, ou rassemblent des champs de bits disparates dans le mot dans une partie contiguë d'un champ de bits (voir les opérateurs Intel PEXT/PDEP récents). Utilisé par la cryptographie et l'encodage vidéo.
  • inversion de matrice

Certaines opérations arithmétiques peuvent être réduites à des opérations plus simples et à des opérations sur les bits :

  • réduire multiplier par constante à la séquence de décalage-ajouter

Multiplier par 9 par exemple, c'est copier l'opérande, décaler par 3 (multiplier par 8) et ajouter à l'opérande d'origine.

  • réduire la division par constante à la séquence de décalage-soustraction

Masquage

Article détaillé : masque (informatique)

Un masque est une donnée utilisée pour les opérations au niveau du bit , en particulier dans un champ de bits .

À l'aide d'un masque, plusieurs bits dans un Byte , un quartet , un mot (etc.) peuvent être activés, désactivés ou inversés de activé à désactivé (ou vice versa) en une seule opération au niveau du bit. Des applications plus complètes de masquage, lorsqu'elles sont appliquées de manière conditionnelle aux opérations, sont appelées prédication .

Voir également

Les références

Lectures complémentaires

  • Warren, Henry S. (2013). Hacker's Delight (2e éd.). Addison–Wesley Professionnel. p. 512. ISBN 978-0321842688.
  • Knuth, Donald E. (2009). L'art de la programmation informatique Volume 4, Fascicule 1 : Astuces et techniques au niveau des bits ; Diagrammes de décision binaire (1ère éd.). Addison–Wesley Professionnel. p. 272. ISBN 978-0321580504.( Brouillon du Fascicule 1a disponible en téléchargement)

Liens externes