Ouvrir le menu principal

Les opérations bit à bit/Manipulations sur les bits de poids faible/fort

< Les opérations bit à bit

Vu que nous travaillons sur des nombres codés en binaire, on ne peut pas s'étonner de la présence d'un chapitre spécialement dédié aux puissances de deux. Il parait naturellement que certains calculs les faisant intervenir soient nombreux dans le domaine de la manipulation de bits.

Sections

Manipuler les 1 et 0 de poids faible/fortModifier

Pour débuter cette section, il nous faut faire un rappel de deux faits importants. Premièrement, en binaire,   est un nombre dont le énième bit est à 1 et tous les autres à 0. Par contre,   est un nombre dont ce bit est à 0, de même que ceux à sa gauche : seuls les bits à sa droite sont à 1.

Nombre x Écriture binaire de   sur 8 bits Écriture binaire de   sur 8 bits
1 0000 0001 0000 0000
2 0000 0010 0000 0001
3 0000 0100 0000 0011
4 0000 1000 0000 0111
5 0001 0000 0000 1111
6 0010 0000 0001 1111
7 0100 0000 0011 1111
8 1000 0000 0111 1111

Mettre à 0 le 1 de poids faibleModifier

On peut aussi se demander ce que donne le calcul   quand il est appliqué à un nombre quelconque, pas forcément à une puissance de deux. Si vous faites quelques tests, vous allez remarquer que ce calcul met toujours un bit à 0 dans le nombre initial : pas un de plus, pas un de moins. De plus, ce bit est un bit qui est initialement à 1 : il s'agit même du 1 qui est le plus à droite dans l'écriture binaire, à savoir le 1 de poids faible. C'est pour cela que ce calcul permet de vérifier si un nombre est une puissance de deux : par définition, une puissance de deux n'a qu'un seul bit à 1. Si ce bit est mis à 0, alors on obtient bien un zéro.

   
1111 1111 1111 1110
1111 1110 1111 1100
1111 1000 1111 0000
0010 1000 0010 0000
0010 0000 0000 0000

Pour comprendre pourquoi cela fonctionne, reprenons l'écriture binaire du nombre x. Si celui-ci est non-nul, il y aura un 1 qui sera le plus à droite de tous les autres. Celui-ci codera une puissance de deux, peu importe laquelle. Il aura un ou plusieurs zéros à sa droite, potentiellement zéro. Dit autrement, on peut décomposer ce nombre en deux parties : une partie gauche contenant les bits à gauche du 1 de poids faible et une partie droite de la forme 10000, avec un nombre de zéro variable, potentiellement nul. En clair, le nombre est de la forme XXXXX...XXXX 100000...000.

On remarque que la partie droite est une puissance de deux : sa représentation binaire est celle d'une puissance de deux. Si on soustrait 1, la partie droite sera donc un nombre de la forme  . On obtiendra donc une partie droite de la forme 011111...11111, et donc un nombre de la forme XXXXX...XXXX 011111...11111. On remarque que   et   ont la même partie gauche. Si on fait un ET entre ces deux nombres, la partie la partie gauche sera intouchée. Par contre,   et   n'ont aucun bit en commun, ce qui fait que le ET va donner 0. Si on compare le résultat avec  , on remarque que le résultat est le même que le nombre   de départ, sauf que le 1 de poids faible est mis à 0.

Cette opération permet de vérifier qu'un nombre est une puissance de 2. On remarque que les nombres   et   n’ont pas de bit à 1 en commun. Dit autrement, si on effectue un ET logique entre ces deux nombres, on obtient 0 : les 0 dans un nombre vont annuler les 1 qui sont dans l'autre. Ce qui signifie que si x est une puissance de deux, alors  . Et la réciproque est vraie : si  , alors x est une puissance de deux. Attention toutefois : avec cette technique, zéro est considéré comme une puissance de deux. Faites donc attention.

Mettre à 0 les 1 de poids faibleModifier

Le code précédent peut s'adapter afin de mettre à 0 non pas le 1 de poids faible, mais tous les 1 de poids faibles consécutifs s'ils sont plusieurs. Par exemple, pour le nombre 0101011111, on peut vouloir mettre à 0 les 5 1 de poids faible. Pour cela, il faut utiliser la formule suivante :

 

Mettre à 1 le 0 de poids faibleModifier

On peut aussi vouloir inverser non pas le 1 de poids faible, mais le 0 de poids faible, le mettre à 1. Pour cela, il faut utiliser la formule suivante :

 

Mettre à 1 le ou les 0 de poids faibleModifier

On peut maintenant se demander ce qui se passe quand on effectue non pas un ET, mais un OU entre   et  . Dans ce cas, on remarque que les 0 de poids faibles sont mis à 1. Précisément, si on prend un nombre de la forme XXXXX...XXXX 100000...000, celui-ci devient de la forme XXXXX...XXXX 11111...1111. En clair, tous les bits qui se situe à droite du 1 de poids faible sont mis à 1. Par exemple, le nombre 0110 1010 0011 1000 deviendra 0110 1010 0011 1111. Pour résumer, voici la formule adéquate :

 

Il faut signaler que cette formule ne modifie pas les bits qui ne sont les 0 de poids faible. Mais il est possible d'isoler ceux-ci et de mettre tout autre bit à 0. Par exemple, le nombre 0110 1100 1111 0000 deviendra : 0000 0000 0000 1111. Ou encore, le nombre 0101 1000 deviendra 0000 0111. Pour cela, diverses formules peuvent être utilisées. Les voici :

  •   ;
  •   ;
  •  .

Isoler le 1 de poids faibleModifier

Isoler le 1 de poids faible signifie mettre à 0 tous les autres bits du nombre. Seul le 1 de poids faible restera à 1, les autres bits étant effacés. Cette opération est très simple : il s'agit d'un simple ET entre   et   :

 .

FFS, FFZ, CTO et CLOModifier

Dans cette section, nous allons aborder plusieurs opérations fortement liées entre elles. Dans toutes ces opérations, les bits sont numérotés, leur numéro étant appelé leur position ou leur indice. La première opération, Find First Set, donne la position du 1 de poids faible, celui le plus à droite du nombre. Cette opération est liée à l'opération Count Trailing Zeros, qui donne le nombre de zéros situés à droite de ce bit à 1. L'opération Find First Set est opposée au calcul du logarithme binaire, qui donne la position du 1 le plus à droite, celui de poids fort. Le nombre de zéros situés à gauche de ce bit à 1 est appelé le Count Leading Zeros.

Ces quatre opérations ont leur équivalents inverses. Par exemple, l'opération Find First Zero donne la position du 0 de poids faible (le plus à droite) et l'opération Find Highest Zero donne la position du 0 de poids fort (le plus à gauche). L'opération Count Trailing Ones donnent le nombre de 1 situés à gauche du 0 de poids fort, tandis que l'opération Count Leading Ones donne le nombre de 1 situés à droite du 0 de poids faible. Ceux-ci se calculent à partir des quatre opérations précédentes, en inversant l'opérande, aussi nous n'en parlerons pas plus que cela.

 
Opérations Find First Set ; Find First Zero ; Find Highest Set (le logarithme binaire) ; Find Highest Zero ; Count Leading Zeros ; Count Trailing Zeros ; Count Leading Ones et Count Trailing Ones.

Ces opérations varient selon la méthode utilisée pour numéroter les bits. On peut commencer à compter les bits à partir de 0, le 0 étant le numéro du bit de poids faible. Mais on peut aussi compter à partir de 1, le bit de poids faible étant celui de numéro 1. Ces deux conventions ne sont pas équivalentes. Par exemple, si on choisit la première convention, les opérations Count Trailing Zeros et Find First Set sont strictement équivalentes. Même chose pour les opérations Count Trailing Ones et Find First Zero. Avec l'autre convention, les deux différent de 1 systématiquement. Dans ce qui va suivre, nous allons utiliser la première convention : le bit de poids faible a comme numéro 0. Ce qui fait que nous n'aurons qu'à aborder deux calculs : Find First Set, abréviée FFS, et le calcul du logarithme binaire. Avec cette convention, pour un nombre codé sur   bits, on a :

 

 

Le logarithme binaireModifier

Maintenant, nous allons voir comment déterminer la position du 1 le plus significatif dans l'écriture binaire du nombre. En clair, la position du 1 le plus à gauche. Mine de rien, ce calcul a une interprétation arithmétique : il s'agit du logarithme en base 2 d'un entier non-signé. Dans tout ce qui va suivre, nous allons numéroter les bits à partir de zéro : le bit le plus à droite d'un nombre (son bit de poids faible) sera le 0-ème bit, le suivant le 1er bit, et ainsi de suite.

Nous allons commencer par voir un cas simple : le cas où notre nombre vaut  . Dans ce cas, un seul bit est à 1 dans notre nombre : le n-ième bit. On peut en faire une démonstration par récurrence. Déjà, on remarque que la propriété est vraie pour   : le 0-ème bit du nombre est mis à 1. Supposons maintenant que cette propriété soit vraie pour   et regardons ce qui se passe pour  . Dans ce cas,  . Donc, le bit suivant sera à un si on augmente l'exposant d'une unité : la propriété est respectée !

Maintenant, qu'en est-il pour n'importe quel nombre  , et pas seulement les puissances de deux ? Prenons n'importe quel nombre, écrit en binaire. Si celui-ci n'est pas une puissance de deux, alors il est compris entre deux puissances de deux :  . En prenant le logarithme de l'inégalité précédente, on a :  . Par définition du logarithme en base 2, on a :  . Dit autrement, le logarithme en base 2 d'un nombre est égal à  , qui est la position de son 1 de poids fort, celui le plus à droite. Plus précisément, il s'agit de la partie entière du logarithme.

Méthode itérativeModifier

Mais comment calculer cette position ? Pour cela, on peut utiliser le code suivant Celui-ci est composé d'une boucle qui décale le nombre d'un rang à chaque itération, et compte le nombre de décalage avant d'obtenir 0.

int log_2 (int a)
{
    unsigned int r = 0;
    while (a >>= 1)
    {
        r++;
    }
    return r ;
}

Méthode par dichotomieModifier

Une autre méthode se base sur un algorithme par dichotomie, à savoir qu'il vérifie si le logarithme est compris dans un intervalle qui se réduit progressivement. Pour illustrer le principe de cet algorithme, nous allons prendre un entier de 64 bits. L'algorithme utilise une variable accumulateur pour mémoriser le logarithme, qui est calculé au fil de l'eau. L'algorithme vérifie d'abord si le bit de poids fort est compris dans les 32 bits de poids fort. Si c'est le cas, on sait que le logarithme est d'au moins 32 (> ou = à 32). La variable accumulateur est alors incrémentée de 32 et le nombre est décalé de 32 rangs vers la droite. On poursuit alors l'algorithme, mais en vérifiant si le bit de poids fort est dans les 16 bits de poids fort. Et ainsi de suite avec les 8, 4, et 2 bits de poids fort. Pour vérifier si le bit de poids fort est dans les 32, 16, 8, 4, ou 2 bits de poids fort, une simple comparaison suffit. Il suffit de comparer si le nombre est supérieur respectivement à (1111 1111 1111 1111 1111 1111 1111 1111), (1111 1111 1111 1111), (1111 1111), (1111), (11). Le code est donc le suivant :

int log_2 (int x)
{
    unsigned log = 0 ;

    if (x > 0xFFFFFFFF)
    {
        log += 32 ;
        x = x >> 32 ;
    }
    if (x > 0xFFFF)
    {
        log += 16 ;
        x = x >> 16 ;
    }
    if (x > 0xFF)
    {
        log += 8 ;
        x = x >> 8 ;
    }
    if (x > 0xF)
    {
        log += 4 ;
        x = x >> 4 ;
    }
    if (x > 3)
    {
        log += 1 ;
        x = x >> 2 ;
    }
    log = x >> 1 ;

    return log ;
}


On peut généraliser cet exemple pour n'importe quel nombre de   bits. L'algorithme commence par vérifier si le bit de poids fort est dans les   bits de poids fort ou dans les   bits de poids faible. Si le bit de poids fort est dans les   bits de poids forts, alors on sait que le logarithme est d'au moins   et peut lui être supérieur ou égal. On mémorise donc   bits comme valeur temporaire du logarithme. On décale alors le nombre de   bits vers la droite pour le ramener dans l'autre intervalle. Et on continue, mais en vérifiant les   bits de poids fort, et ainsi de suite.

Méthode basée sur le poids de HammingModifier

Une autre solution se base sur le fait que le bit de poids faible est numéroté 0 ! Pour cela, on peut utiliser le code précédent, qui permet de trouver le nombre de la forme   immédiatement supérieur. Ce nombre, par définition, a tous les bits de rang   à 1 : il suffit de compter ses 1 pour obtenir le rang   ! On verra dans quelques chapitres qu'il existe des méthodes pour compter le nombre de 1 d'un nombre, celui-ci étant appelé le poids de Hamming.

int log_2 (int a)
{
    int n = NextPowerOf2 (a) ;
    return HammingWeight(n) ;
}

Count Leading ZerosModifier

Dans un ordinateur, les nombres sont de taille fixe. Un nombre est ainsi stocké sur 8, 16, 32, 64 bits. Si jamais un nombre peut être représenté en utilisant moins de bits que prévu, les bits qui restent sont mis à zéro. Par exemple, sur une architecture 8 bits, le nombre 5 ne sera pas stocké comme ceci : 101, mais comme ceci : 00000101. On voit donc que ce nombre contient un certain nombre de zéros non-significatifs. Ces zéros sont placés à gauche du nombre. Plus précisément, notre nombre aura certains de ses bits à 1. Parmi ceux-ci, il y aura un de ces bits qui sera plus à gauche que tous les autres 1. A gauche de ce 1, on peut éventuellement trouver un certain nombre de zéros non-significatifs. L'instruction Count leading zeros a pour objectif de compter ces zéros non-significatifs. Pour un nombre de N bits, le nombre de ces zéros à gauche peut varier entre 0 et N. Si on a 0 zéros non-significatif, dans ce cas, le bit de plus à gauche est un 1. Si jamais on a N de ces zéros, c'est que tous les bits du nombre sont à zéro. En matériel, cette opération est souvent utilisée dans certaines unités de calcul à virgule flottante, dans les opérations de normalisation et d'arrondis du résultat. Néanmoins, il faut préciser que seules les unités de calcul à faible performance ont besoin de déterminer le nombre de zéros les plus à gauche.

On peut calculer ce nombre de zéros à gauche simplement à partir de l'indice du 1 de poids fort, en utilisant l'équation  . On a vu plus haut comment trouver l'indice de ce 1 le plus à gauche. Le nombre de 0 à gauche est simplement égal au nombre de bits de notre nombre, auquel on soustrait la position de ce 1 :  .

Une autre méthode consiste à réutiliser le code qui calcule la puissance de 2 immédiatement supérieure. Pour rappel, la première étape de cet algorithme consiste à remplir les bits à droite du 1 de poids fort par des 1, avec des décalages successifs. Les seuls bits à rester à 0 sont les 0 de poids forts, qu'on souhaite compter. Une fois qu'on a appliqué l'algorithme, on n'a plus qu'à effectuer un calcul de population count et de soustraire le résultat de  .

unsigned NextPowerOf2 (unsigned n)
{
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;

    x = population_count( n ) ;

    return WORDBITS - x ;
}

Une autre solution consiste à effectuer la première étape, à inverser les bits et à calculer la population count. L'inversion des bits garanti que seuls les 0 de poids forts seront à 1, d'où le fait que la population count donne le bon résultat.

unsigned NextPowerOf2 (unsigned n)
{
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;

    return population_count( ! n ) ;
}

Find First SetModifier

Passons maintenant à l'opération Find First Set, qui donne la position du 1 de poids faible. On a vu plus haut que l'on peut isoler ce bit, faire en sorte de mettre tous les autres bits à 0 : il faut utiliser le calcul  . Une fois ce bit isolé, on peut trouver sa position en calculant son logarithme binaire. On a donc :

unsigned ffs (unsigned n)
{
    return log_2( x & -x ) ;
}