Mis à part que les pionniers de l’informatique auraient dut se préoccuper du français quand ils ont nommée leurs unités logique voici le problème que je me posais initialement:
Un booléen est habituellement stocké dans un octet (soit un unsigned char) alors qu'il ne peut prendre que deux états. Pour un seul booléen ou des milliers des booléens ça reste un gaspillage acceptable sur les ordinateurs modernes, où la mémoire ne manque pas. Mais pour certaines applications (par exemples de larges
filtres de Bloom) il est souhaitable de compacter la place occupées par les milliers de booléens que l'on veut instancier. En d'autre thermes, peut-on instancier un tableau de bits?
Réponse, pas de base, il faut quitter sa zone de confort avec les jolis opérateur qu'on nous a appris en primaire ( + - ÷ × ) et s'attaquer à ces inquiétant opérateur dit bit à bit
(et il est interdit de penser à une partouze) ( & | ^ << >> ).
Heureusement ce tutoriel est là pour vous aider, on va même réaliser ensemble un jolis objet c++ qui va gérer tout ça pour nous! Voyons d'abords ces fameux opérateurs qu'on va utiliser:
&
AND, "et" logique, renvoie un bit à 1 si et seulement si les deux bits de même poids valent 1 sur les deux paramètres passés:
unsigned int a = 4 & 7; //a = 4
unsigned int b = 7 & 9; //b = 1
unsigned int c = 4 & 9; //c = 0
unsigned int oct = 0203 & 0205; //oct = 0201
unsigned int hex = 0x000F02 & 0x00420F; //hex = 0x000202; |
Vous l'aurez remarqué la clé du problème c'est la décomposition des nombre en puissance de deux. Pour accéder au nième bit d'un entier il suffit donc de réaliser nombre & (2 à la puissance n).
|
OR, "ou" simple fonctionne de la même manière mais il lui suffit qu'il seul des deux bits de même poids soient à 1 pour renvoyer 1:
unsigned int a = 4 | 7; //a = 7
unsigned int b = 7 | 9; //b = 15
unsigned int c = 4 | 9; //c = 13
unsigned int oct = 0203 | 0205; //oct = 0207
unsigned int hex = 0x000F02 | 0x00420F; //hex = 0x004F0F; |
^
XOR, "ou" exclusif, renvoie 1 si et seulement si un seul des bits de même poids vaut 1:
unsigned int a = 4 ^ 7; //a = 3
unsigned int b = 7 ^ 9; //b = 14
unsigned int c = 4 ^ 9; //c = 13
unsigned int oct = 0203 ^ 0205; //oct = 0006
unsigned int hex = 0x000F02 ^ 0x00420F; //hex = 0x004C0C; |
<< et >>
représentent un décalage à gauche ou à droite ce qui revient à multiplier ou diviser par deux autant de fois que spécifié ( et dans la limite de la taille du type utilisé).
unsigned int a = 2 << 2; //a = 8
unsigned int b = 1 << 3; //b = 8
unsigned int c = 2 >> 1; //c = 1 |
Leur principale utilité, combinés aux opérateurs précédents, est d'accéder à un bit donné.
unsigned int a = 1 << 0; //a permet d'inspecter le bit 0
unsigned int b = 1 << 5; //b permet d'inspecter le bit 5 |
Il fut un temps les processeurs ne pouvaient pas réaliser directement les opérations arithmétiques de base, il fallait les implémenter grâce à ces opérateurs bits à bits. Par exemple le bon vieil algorithme d'addition en colonne devenait (la représentation assumée est celle dite complément à deux, la charge de détecter les dépassements n'est pas assumée par la fonction):
int additionner (int pN1, int pN2){
int n1 = pN1;
int n2 = pN2;
int r1 = n1 ^ n2; //addition directe
int r2 = (n1 & n2) << 1; //retenue
if(!r1)
return r2;
else if (!r2)
return r1;
else
return additionner (r1, r2);
} |
Donc on peut s'offrir un tableau de booléen compressé, voici en c++:
Définition:
class BinaryKeeper{
public:
/** Default constructor */
BinaryKeeper(unsigned int pSize);
/** Default destructor */
virtual ~BinaryKeeper();
/** Copy constructor
* \param other Object to copy from
*/
BinaryKeeper(const BinaryKeeper& other);
/** Access size
* \return The current value of size
*/
unsigned int Getsize() const{ return size; }
bool InIndex(unsigned int index) const;
char CharInIndex(unsigned int index) const;
void SetIndex(unsigned int index, bool pState);
private:
unsigned int size; //!< Member variable "size"
unsigned char* datas; //!< Member variable "datas"
}; |
Premièrement le constructeur, il va essentiellement instancier un tableau d'unsigned char et le remplir de 0. Ce type offre l'avantage d'être de taille constantes selon les systèmes:
/** Default constructor */
BinaryKeeper::BinaryKeeper(unsigned int pSize){
//ctor
size = pSize;
unsigned int cSize = size/8 + 1;
try{
datas = new unsigned char [cSize];
for(unsigned int k = 0; k < cSize; k++){
datas[k] = 0;
}
}catch ( const std::bad_alloc & ) { // erreur d'allocatation.
delete [] datas;
size = 0;
}
} |
Ce code n'est pas très compliqué. Notez bien que pour être certain d'avoir assez de place pour inscrire le nombre de bits demandé qui n'est pas forcément un multiple de 8 vous devez ajouter un octet à la taille de votre tableau. Si ce dépassement anecdotique vous ennuie vous pouvez corriger size, personnellement j'alloue quelques bit de plus mais je tiens à ce que mon objet encapsule la taille demandée.
Le destructeur lui, va juste libérer les allocations dynamiques:
/** Default constructor */
BinaryKeeper::~BinaryKeeper(){
//dtor
delete [] datas;
} |
Viennent ensuite les accesseurs, si accéder à une char donnée se fait de manière simple (libre à vous de définir un comportement quand vous dépasser la taille du tableau, personellement dans ce cas je renvoie le plus haut indice disponible). Pour accéder à l'état (true | false) d'un bit donné ça se corse un peu.
char BinaryKeeper::CharInIndex(unsigned int index) const{
if (index <= size/8)
return datas[index];
else
return datas[size];
}
bool BinaryKeeper::InIndex(unsigned int index) const{
unsigned int i = index;
if( i >= size)
i = size-1;
unsigned int cIndex = i >> 3 ;
unsigned int cInside = i & 7 ;
unsigned char v = datas[cIndex];
unsigned char c = 1 << cInside;
return (bool) (v & c);
} |
Les index de notre tableau de bits fonctionnent comment ceux d'un tableau classique. Le premier bit est le bit de poids 0 (2^0) du char 0. Le dernier est donc le size-1 ème bits. On corrige donc l'index s'il est trop haut (on pourrait aussi lancer une exception, renvoyer faux ou vrai par défaut ... ).
Ensuite viennent ces deux lignes assez mystérieuses (je vous aide un peu et vous donne les équivalents classiques):
unsigned int cIndex = i >> 3 ;
unsigned int cInside = i & 7 ;
//équivalent:
unsigned int cIndex = i / 8 ;
unsigned int cInside = i % 8 ; |
cIndex est le char que l'on va inspecter, cInside le poids du bit à inspecter à l'intérieur. On les obtient le plus logiquement du monde en divisant par 8 et en prenant le modulo par 8 de l'indice demandé. Mais comme 8 est une puissance de 2 il y a plus "simple" (du moins en temps de calcul pour l'ordinateur). Diviser par 8 revient à diviser par 2^3 soit de décaler 3 fois à droite. Prendre le modulo revient à effacer tout les bits sauf ceux de poids 0, 1 et 2 ce qui se fait grâce à l'opérateur & 7.
| unsigned char c = 1 << cInside; |
c servira à accéder au bit souhaité. Ce que l'on fait à la ligne suivante grâce à &:
Enfin détaillons la fonction de changement d'état d'un bit donné, j'ai choisi volontairement de créer une fonction qui change le bit vers un état spécifié mais il serait possible d'en créer une qui inverse simplement l'ancien état:
void BinaryKeeper::SetIndex(unsigned int index, bool pState) {
unsigned int i = index;
if( i >= size)
i = size-1;
unsigned int cIndex = i >> 3 ;
unsigned int cInside = i & 7 ;
unsigned char c = 1 << cInside;
if (pState){ // si on veut mettre l'état à true
datas[cIndex] |= c; //alors on le met à 1
} else { // si on veut mettre l'état à false;
c ^= 255; //on place un zéro sur le bit du poids qui nous intéresse.
datas[cIndex] &= c; //on le met à 0.
}
} |
Bien sûr cet objet reste relativement simple dans sa conception, il ne gère pas d'exceptions, ne permet pas d'utiliser d'itérateurs, etc... Néanmoins il réalise son travail correctement (du moins de ce que j'ai put tester) quand il s'agit de gérer un filtre de bloom ou un très grands tableau de booléens tout en économisant la mémoire. Il sera par contre légèrement plus lent qu'un simple bool*.
Libre à vous de l'améliorer, perso je ne le ferai que si j'en ai l'utilité. Puisque pour l'instant il me convient ainsi!
