Dans les ordinateurs, toutes les données sont stockées sous forme binaire. Les opérations sur les bits consistent à manipuler directement les données binaires en mémoire, ce qui permet un traitement très rapide des données. En programmation, une utilisation habile des opérations sur les bits peut produire des résultats spectaculaires avec un effort minimal. C'est pourquoi ces opérations sont fréquemment abordées lors des entretiens techniques dans les entreprises de technologie.
Opérations de Base sur les Bits
Les opérateurs de base sur les bits sont au nombre de six : ET, OU, OU exclusif (XOR), NON, décalage à gauche et décalage à droite. Voici leurs règles d'opération :
- ET (&) : Effectue une opération logique ET entre les bits correspondants des opérandes.
- OU (|) : Effectue une opération logique OU entre les bits correspondants des opérandes.
- OU exclusif (^) : Effectue une opération logique OU exclusif entre les bits correspondants des opérandes.
- NON (~) : Inverse tous les bits de l'opérande.
- Décalage à gauche («) : Décale les bits vers la gauche, en ajoutant des zéros à droite.
- Décalage à droite (») : Décale les bits vers la droite, en conservant le signe pour les nombres signés.
Points importants à noter :
- Parmi ces six opérateurs, seul ~ (NON) est un opérateur unaire, les cinq autres sont binaires.
- Les opérations sur les bits ne peuvent être appliquées qu'aux types de données entières. Les opérations sur les types float et double provoquent une erreur de compilation.
- La priorité des opérateurs sur les bits est relativement faible, il est donc recommandé d'utiliser des parenthèses pour garantir l'ordre des opérations.
- Il existe égallement des opérateurs de composition pour les opérations sur les bits, comme &=, |=, ^=, «=, »=.
Astuces Courantes avec les Opérations sur les Bits
Voici un résumé des applications courantes des opérations sur les bits : vérification de parité, échange de deux nombres, changement de signe et calcul de valeur absolue. Ces techniques sont faciles à mémoriser et devraient être maîtrisées.
Vérification de Parité
La parité d'un nombre peut être déterminée en examinant son bit le plus à droite. Si ce bit est 0, le nombre est pair ; s'il est 1, le nombre est impair. Ainsi, on peut remplacer if ((a & 1) == 0) par if (a % 2 == 0) pour vérifier si a est pair. Le programme suivant affiche tous les nombres pairs entre 0 et 100 :
for (int compteur = 0; compteur < 100; compteur++) {
if ((compteur & 1) == 0) { // pair
System.out.println(compteur);
}
}
Échange de Deux Nombres
int premier = 1, second = 2;
premier ^= second;
second ^= premier;
premier ^= second;
System.out.println("premier=" + premier);
System.out.println("second=" + second);
Cette technique peut être comprise comme suit :
Étape 1 : premier ^= second, soit premier = (premier ^ second)
Étape 2 : second ^= premier, soit second = second ^ (premier ^ second). Grâce à la commutativité de l'opération XOR, second ^ (premier ^ second) = second ^ second ^ premier. Puisqu'un nombre XOR avec lui-même donne 0 et que tout nombre XOR avec 0 reste inchangé, second se voit assigner la valeur de premier.
Étape 3 : premier ^= second, soit premier = premier ^ second. D'après les étapes précédentes, premier = (premier ^ second) et second = premier, donc premier = premier ^ second = (premier ^ second) ^ second. Ainsi, premier se voit assigner la valeur de second.
Changement de Signe
Changer le signe d'un nombre consiste à transformer un nombre positif en négatif et vice versa. Par exemple, pour -11 et 11, on peut transformer -11 en 11 comme suit :
1111 0101 (binaire) – NON –> 0000 1010 (binaire) – ajouter 1 –> 0000 1011 (binaire)
De même, on peut transformer 11 en -11 comme suit :
0000 1011 (binaire) – NON –> 0000 0100 (binaire) – ajouter 1 –> 1111 0101 (binaire)
Par conséquent, pour changer le signe, il suffit d'appliquer l'opération NON puis d'ajouter 1. Le code complet est le suivant :
int negatif = -15, positif = 15;
System.out.println("Changement de signe pour " + negatif + ": " + (~negatif + 1));
System.out.println("Changement de signe pour " + positif + ": " + (~positif + 1));
Calcul de Valeur Absolue
Les opérations sur les bits peuvent également être utilisées pour calculer la valeur absolue. Pour un nombre négatif, on peut obtenir sa valeur positive en appliquant l'opération NON puis en ajoutant 1. Pour -6, procédons comme suit :
1111 1010 (binaire) – NON –> 0000 0101 (binaire) – ajouter 1 –> 0000 0110 (binaire)
On obtient ainsi 6.
On peut donc d'abord déplacer les bits pour obtenir le bit de signe, int decalage = valeur >> 31 ;. Si valeur est positif, decalage est égal à 0 ; si valeur est négatif, decalage est égal à -1. On vérifie ensuite la valeur de decalage – si elle est 0, on retourne directement valeur ; sinon, on retourne ~valeur + 1. Le code complet est le suivant :
int decalage = valeur >> 31;
System.out.println(decalage == 0 ? valeur : (~valeur + 1));
Analysons maintenant une autre approche. Pour tout nombre, le XOR avec 0 conserve sa valeur, tandis que le XOR avec -1 (c'est-à-dire 0xFFFFFFFF) équivaut à l'opération NON. Ainsi, valeur XOR decalage puis soustraire decalage (puisque decalage est soit 0 soit -1, soustraire decalage revient soit à ajouter 0 soit à ajouter 1) permet également d'obtenir la valeur absolue. On peut donc optimiser le code précédent comme suit :
int decalageOptimise = nombre >> 31;
System.out.println((nombre ^ decalageOptimise) - decalageOptimise);
Notez que cette méthode n'utilise aucune expression conditionnelle, et certains entretiesn techniques exigent précisément cette approche. Il est donc recommandé de se souvenir de cette technique.
Opérations sur les Bits et Compression d'Espace
La méthode du crible d'Ératosthène n'est pas détaillée ici, nous nous concentrerons plutôt sur l'optimisation de la table des nombres premiers utilisée par cette méthode pour réduire son occupation en espace. Pour compresser l'espace occupé par la table des nombres premiers, on peut utiliser les opérations sur les bits. Voici un exemple de code utilisant le crible d'Ératosthène pour calculer les nombres premiers inférieurs à 100 :
int maximum = 100;
boolean[] marqueurs = new boolean[maximum];
int [] nombresPremiers = new int[maximum / 3 + 1];
int index = 0;
for (int courant = 2; courant < maximum ; courant++) {
if (!marqueurs[courant]) {
nombresPremiers[index++] = courant;
for(int multiple = courant; multiple < maximum; multiple += courant) {
marqueurs[multiple] = true;
}
}
}
Dans ce programme, un tableau de booléens est utilisé pour marquer les nombres. Un type booléen occupe 1 octet (8 bits), donc l'utilisation d'opérations sur les bits pour compresser l'espace réduira l'occupation de l'espace de sept huitièmes.
Considérons maintenant comment définir un bit spécifique à 1 dans un tableau. Tout d'abord, examinons comment définir un bit spécifique à 1 dans un entier. Pour un entier, on peut obtenir l'effet de définir un bit spécifique à 1 en décalant 1 vers la gauche puis en l'associant par un OU à l'entier d'origine. Le code correspondant est le suivant :
// Définir un bit spécifique à 1 dans un nombre
int e = 0;
e |= 1 << 10;
System.out.println(e);
De même, on peut décaler 1 vers la gauche puis l'associer par un ET avec l'entier d'original pour vérifier si un bit spécifique est à 1 ou à 0 (on peut également décaler l'entier d'original vers la droite de plusieurs positions puis l'associer par un ET avec 1).
// Vérifier si un bit spécifique est à 1 ou à 0
if ((e & (1 << 10)) != 0)
System.out.println("Le bit spécifique est à 1");
else
System.out.println("Le bit spécifique est à 0");
Étendu à un tableau, nous pouvons utiliser cette méthode, car un tableau est également un espace contigu alloué en mémoire, que l'on peut considérer comme un très long entier. Écrivons d'abord un code de test pour voir comment utiliser les opérations sur les bits dans un tableau :
int[] bits = new int[40];
for (int m = 0; m < 40; m += 3) {
bits[m / 32] |= (1 << (m % 32));
}
// Afficher tous les bits
for (int m = 0; m < 40; m++) {
if (((bits[m / 32] >> (m % 32)) & 1) != 0)
System.out.print('1');
else
System.out.print('0');
}
Le résultat d'exécution est le suivant :
1001001001001001001001001001001001001001
Cela montre que chaque troisième bit du tableau est défini à 1, ce qui prouve que notre méthode d'utilisation des opérations sur les bits dans un tableau est correcte. Par conséquent, nous pouvons modifier la méthode du crible d'Ératosthène pour utiliser une version compressée avec les opérations sur les bits :
int[] marqueursBits = new int[maximum / 32 + 1];
index = 0;
for (int courant = 2; courant < maximum ; courant++) {
if ((((marqueursBits[courant / 32] >> (courant % 32)) & 1) == 0)) {
nombresPremiers[index++] = courant;
for(int multiple = courant; multiple < maximum; multiple += courant) {
marqueursBits[multiple / 32] |= (1 << (multiple % 32));
}
}
}
Le résultat d'exécution est le suivant :
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Classe d'Utilitaires pour les Opérations sur les Bits
package fr.example.utilitairesbits;
public class OutilsBits {
/**
* Obtenir la valeur d'un bit spécifique dans un nombre
* Par exemple : 0000 1011 obtenir la valeur du bit 0 qui est 1, la valeur du bit 2 qui est 0
* @param source Le nombre à opérer
* @param position La position spécifiée (0<=position<=7)
* @return La valeur du bit spécifié (0 ou 1)
*/
public static byte obtenirValeurBit(byte source, int position) {
return (byte) ((source >> position) & 1);
}
/**
* Définir la valeur d'un bit spécifique dans un nombre
* Exemple : 0000 1011 doit être mis à jour en 0000 1111, c'est-à-dire que le bit 2 doit être mis à 1
* @param source Le nombre à opérer
* @param position La position spécifiée (0<=position<=7)
* @param valeur Ne peut prendre que les valeurs 0 ou 1, toutes les valeurs >0 sont traitées comme 1, toutes les valeurs <0 sont traitées comme 0
* @return Le résultat de l'opération
*/
public static byte definirValeurBit(byte source, int position, byte valeur) {
byte masque = (byte) (1 << position);
if (valeur > 0) {
source |= masque;
} else {
source &= (~masque);
}
return source;
}
/**
* Inverser la valeur d'un bit spécifique dans un nombre
* Exemple : 0000 1011 inverser le bit 3, le résultat est 0000 0011 ; inverser le bit 2, le résultat est 0000 1111
* @param source Le nombre à opérer
* @param position La position spécifiée (0<=position<=7)
* @return Le résultat de l'opération
*/
public static byte inverserValeurBit(byte source, int position) {
byte masque = (byte) (1 << position);
return (byte) (source ^ masque);
}
/**
* Vérifier si un bit spécifique dans un nombre est à 1
* @param source Le nombre à opérer
* @param position La position spécifiée (0<=position<=7)
* @return true si le bit spécifié est à 1, false si le bit spécifié est à 0
*/
public static boolean verifierValeurBit(byte source, int position) {
source = (byte) (source >>> position);
return (source & 1) == 1;
}
/**
* Fonction principale pour les tests
* @param args Arguments de la ligne de commande
*/
public static void main(String[] args) {
// Prendre 11 (décimal) (binaire 0000 1011) comme exemple
byte source = 11;
// Obtenir la valeur du bit 2 et l'afficher, le résultat devrait être 0000 1011
for (byte i = 7; i >= 0; i--) {
System.out.printf("%d ", obtenirValeurBit(source, i));
}
// Définir le bit 6 à 1 et l'afficher, le résultat devrait être 75 (0100 1011)
System.out.println("\n" + definirValeurBit(source, 6, (byte) 1));
// Inverser le bit 6 et l'afficher, le résultat devrait être 75(0100 1011)
System.out.println(inverserValeurBit(source, 6));
// Vérifier si le bit 6 est à 1, le résultat devrait être false
System.out.println(verifierValeurBit(source, 6));
// Afficher les bits à 1, le résultat devrait être 0 1 3
for (byte i = 0; i < 8; i++) {
if (verifierValeurBit(source, i)) {
System.out.printf("%d ", i);
}
}
}
}
Classe BitSet
La classe BitSet : une collection de bits dont la taille peut changer dynamiquement, avec des valeurs true ou false. Elle est utilisée pour représenter un ensemble de drapeaux booléens. Cette classe implémente un vecteur de bits qui grandit selon les besoins. Chaque composant d'un BitSet a une valeur booléenne. Les indices non négatifs sont utilisés pour indexer les bits d'un BitSet. Chaque bit indexé peut être testé, défini ou effacé. Le contenu d'un BitSet peut être modifié en utilisant les opérations logiques ET, OU et OU exclusif avec un autre BitSet. Par défaut, tous les bits d'un BitSet initialisé ont la valeur false.
Chaque BitSet a une taille actuelle, qui correspond au nombre de bits actuellement utilisés par ce BitSet. Notez que cette taille est liée à l'implémentation du BitSet, donc elle peut varier selon les implémentations. La longueur d'un BitSet est liée à sa longueur logique et est définie de manière indépendante de l'implémentation.
Sauf indication contraire, passer un paramètre null à n'importe quelle méthode de BitSet provoquera une NullPointerException. Sans synchronisation externe, l'utilisation d'un BitSet par plusieurs threads n'est pas sûre.
Constructeurs : BitSet() ou BitSet(int nbits), la taille initiale par défaut est 64.
public void set(int pos) : Définit le bit à la position pos à true.
public void set(int bitIndex, boolean value) : Définit le bit à l'index spécifié à la valeur spécifiée.
public void clear(int pos) : Définit le bit à la position pos à false.
public void clear() : Définit tous les bits de ce BitSet à false.
public int cardinality() : Renvoie le nombre de bits définis à true dans ce BitSet.
public boolean get(int pos) : Renvoie la valeur du bit à la position pos.
public void and(BitSet other) : Effectue une opération ET entre ce BitSet et other, le résultat devient la nouvelle valeur de ce BitSet.
public void or(BitSet other) : Effectue une opération OU entre ce BitSet et other, le résultat devient la nouvelle valeur de ce BitSet.
public void xor(BitSet other) : Effectue une opération OU exclusif entre ce BitSet et other, le résultat devient la nouvelle valeur de ce BitSet.
public void andNot(BitSet set) : Efface tous les bits de ce BitSet qui sont dans set.
public int size() : Renvoie le nombre de bits réellement utilisés pour représenter les valeurs de ce BitSet.
public int length() : Renvoie la "longueur logique" de ce BitSet : l'index du bit le plus élevé défini + 1.
public int hashCode() : Renvoie le code de hachage de cet ensemble, qui dépend des valeurs des bits de l'ensemble.
public boolean equals(Object other) : Renvoie true si les bits de other sont identiques à ceux de l'ensemble.
public Object clone() : Clone ce BitSet, créant un nouveau BitSet égal à celui-ci.
public String toString() : Renvoie la représentation en chaîne de caractères de ce BitSet.
Exemple 1 : Identifier les caractères utilisés dans une chaîne
package fr.example.bitset;
import java.util.BitSet;
public class QuelsCaracteres {
private BitSet caracteresUtilises = new BitSet();
public QuelsCaracteres(String texte) {
for (int i = 0; i < texte.length(); i++)
caracteresUtilises.set(texte.charAt(i));
}
public String toString() {
String description = "[";
int taille = caracteresUtilises.size();
for (int i = 0; i < taille; i++) {
if (caracteresUtilises.get(i))
description += (char) i;
}
return description + "]";
}
public static void main(String args[]) {
QuelsCaracteres q = new QuelsCaracteres("Comment allez-vous");
System.out.println(q);
}
}
Exemple 2
package fr.example.bitset;
import java.util.BitSet;
public class TestTrois {
public static void main(String[] args) {
BitSet ensembleBits = new BitSet();
System.out.println("Vide: " + ensembleBits.isEmpty() + " -- Taille: " + ensembleBits.size());
ensembleBits.set(0);
System.out.println("Vide: " + ensembleBits.isEmpty() + " -- Taille: " + ensembleBits.size());
ensembleBits.set(1);
System.out.println("Vide: " + ensembleBits.isEmpty() + " -- Taille: " + ensembleBits.size());
System.out.println("Position 65: " + ensembleBits.get(65));
System.out.println("Vide: " + ensembleBits.isEmpty() + " -- Taille: " + ensembleBits.size());
ensembleBits.set(65);
System.out.println("Vide: " + ensembleBits.isEmpty() + " -- Taille: " + ensembleBits.size());
}
}
Exemple 3
package fr.example.bitset;
import java.util.BitSet;
public class TestQuatre {
public static void main(String[] args) {
BitSet bits1 = new BitSet(7);
System.out.println("Vide: " + bits1.isEmpty() + " -- Taille: " + bits1.size());
BitSet bits2 = new BitSet(63);
System.out.println("Vide: " + bits2.isEmpty() + " -- Taille: " + bits2.size());
BitSet bits3 = new BitSet(65);
System.out.println("Vide: " + bits3.isEmpty() + " -- Taille: " + bits3.size());
BitSet bits4 = new BitSet(111);
System.out.println("Vide: " + bits4.isEmpty() + " -- Taille: " + bits4.size());
}
}
Techniques d'Opération sur les Bits
// 1. Obtenir la valeur maximale d'un int
System.out.println((1 << 31) - 1);
System.out.println(~(1 << 31));
// 2. Obtenir la valeur minimale d'un int
System.out.println(1 << 31);
System.out.println(1 << -1);
// 3. Obtenir la valeur maximale d'un long
System.out.println(((long)1 << 127) - 1);
// 4. Multiplier par 2
System.out.println(10<<1);
// 5. Diviser par 2 (pas pour les nombres impairs négatifs)
System.out.println(10>>1);
// 6. Multiplier par 2^m
System.out.println(10<<2);
// 7. Diviser par 2^m
System.out.println(16>>2);
// 8. Vérifier si un nombre est pair ou impair
System.out.println((10 & 1) == 1);
System.out.println((9 & 1) == 1);
// 9. Échanger deux nombres sans variable temporaire
premier ^= second;
second ^= premier;
premier ^= second;
// 10. Obtenir la valeur absolue
int nombre = -1;
System.out.println((nombre ^ (nombre >> 31)) - (nombre >> 31));
// 11. Obtenir le maximum de deux nombres
System.out.println(second&((premier-second)>>31) | premier&(~(premier-second)>>31));
// 12. Obtenir le minimum de deux nombres
System.out.println(premier&((premier-second)>>31) | second&(~(premier-second)>>31));
// 13. Vérifier si les signes sont les mêmes
System.out.println((premier ^ second) > 0);
// 14. Calculer 2^n
System.out.println(2<<(nombre-1));
// 15. Vérifier si n est une puissance de 2
System.out.println((nombre & (nombre - 1)) == 0);
// 16. Obtenir la moyenne de deux entiers
System.out.println((premier+second) >> 1);
// 17. Obtenir le m-ième bit de n
int position = 2;
System.out.println((nombre >> (position-1)) & 1);
// 18. Définir le m-ième bit de n à 1
System.out.println(nombre | (1<<(position-1)));
// 19. Définir le m-ième bit de n à 0
System.out.println(nombre & ~(0<<(position-1)));