Aller au contenu

Manipulation de bits

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Manipulation de bit)

La manipulation de bits consiste à agir sur des données au niveau d'un bit ou d'un ensemble de bits à l'aide d'opérations booléennes. En informatique, cette technique est notamment utilisée pour des opérations de bas niveau comme le contrôle des périphériques, ou encore dans certains algorithmes comme la détection et la correction d'erreur ou le chiffrement, ainsi que pour l'optimisation. À l'heure actuelle néanmoins, la plupart des langages de programmation modernes permettent de s'affranchir du travail à ce niveau en offrant au programmeur de travailler directement avec des abstractions plutôt qu'avec les bits qu'elles représentent.

Les opérations permettant la manipulation des bits sont les opérations booléennes ET (AND), OU (OR), OU exclusif (XOR) et NON (NOT), ainsi que les décalages logiques et arithmétiques et les rotations.

Opérations de base

[modifier | modifier le code]

La manipulation de bits pose souvent problème aux programmeurs débutants, l'utilisation d'instructions assembleur pour manipuler les bits est souvent source d'embarras. C'est pourquoi, utiliser des méthodes de plus haut niveau est recommandé, puisque cela améliore la portabilité et la lisibilité du code source, sous réserve, évidemment, que le lecteur connaisse le langage utilisé.

Les exemples de masquage ci-dessous sont écrits en C, mais peuvent être adaptés à tout langage supportant les opérateurs de calcul binaire. Le C comporte les opérateurs suivants pour la manipulation de bits :

Symbole Opérateur
& ET par bit
l OU inclusif par bit
^ OU exclusif (ou XOR) par bit
<< décalage de bits à gauche
>> décalage de bits à droite
~ complémentaire par bit

Dans la suite, n est le rang du bit que l'on considère, a la valeur originale et b la nouvelle valeur ayant son nième bit modifié.

Mettre un bit à 1 : Pour forcer un bit à 1 on utilise le OU binaire car (1 OU x) = 1.

unsigned char b = a | (1 << n);

Mettre un bit à 0 : Pour forcer un bit à 0 on utilise le ET binaire car (0 ET x) = 0 :

unsigned char b = a & ~(1 << n);

Inverser la valeur du bit :

unsigned char b = a ^ (1 << n);

Tester la valeur d'un bit :

unsigned char b = a & (1 << n);

Lors de la manipulation d'une grande quantité de bits constituée de plusieurs octets, on peut utiliser n = (index % 8) pour calculer le bit désiré. L'octet désiré peut également être calculé avec index / 8.

Bit twiddling

[modifier | modifier le code]

Bit twiddling ou bit bashing (manipulation "violente" de bit) est souvent utilisé dans le sens de manipulation de bits, mais quelquefois pour désigner les méthodes audacieuses ou ingénieuses de manipulation de bits. Ce terme est également utilisé de façon moins flatteuse pour désigner des manipulations longues et fastidieuses d'un logiciel lorsque les améliorations obtenues sont négligeables, et ne facilitant pas la lisibilité du code source. Cette expression date des débuts de l'informatique, lorsque les utilisateurs devaient ajuster patiemment les commandes de l'ordinateur. Alors que l'informatique évoluait, les programmeurs adoptèrent ce terme pour désigner les manipulations binaires de données.

Exemple de Bit twiddling

[modifier | modifier le code]

Le code ci-dessous, écrit en C détermine entre 2 entiers (x et y) le plus petit et le place dans r.

// La méthode classique

if (x < y)
    r = x;
else
    r = y;

// Une méthode plus rapide sur certaines machines

r = y ^ ((x ^ y) & -(x < y));

Le symbole & représente le ET binaire en C.

Dans la plupart des cas, le programmeur choisira la première méthode. Cependant, si un tel test doit être effectué des millions de fois par seconde, le programmeur pourra exploiter sa connaissance de la représentation des entiers en binaire et utilisera la seconde méthode: celle-ci n'utilisant aucun renvoi sera plus rapide sur la plupart des processeurs.

Références

[modifier | modifier le code]