6. Programmation et binaire

Il s'agit dans cette partie d'écrire et tester des fonctions qui agissent sur des entiers non signés.

Pour tester la fonction, on pourra utiliser une macro-instruction du C et des entiers 32 bits non signés en définissant le type u32 :

  1. #include <cstdlib>  // for uint32_t
  2. #include <iostream>
  3.  
  4. //
  5. // Définition d'un type entier 32 bits non signé
  6. // appelé u32 pour Unsigned 32 bits
  7. //
  8. typedef uint32_t u32;
  9.  
  10. //
  11. // Macro instruction qui compare le paramètre x à y.
  12. // Normalement x correspond à la valeur issue d'un appel
  13. // de fonction.
  14. //
  15. // L'utilisation de #x transforme le x sous forme d'une
  16. // chaîne de caractères, ainsi #msb(0) devient "msb(0)".
  17. //
  18. // Si x est différent de y on affiche une erreur avec
  19. // la chaîne qui correspond à l'appel de fonction et
  20. // la chaîne qui correspond à la valeur attendue.
  21. //
  22. //
  23. #define TEST_IF_EQUAL(x,y) if (x != y) { \
  24.     std::cout << "!!! Erreur !!! " << #x << " != " << #y << std::endl; \
  25. } else { \
  26.     std::cout << #x << " = " << #y << std::endl; \
  27. }
  28. ...
  29.  
  30. /* ------------------------------------------------------------------
  31.    QUOI
  32.      Fonction qui retourne le bit le plus significatif de son
  33.      opérande x.
  34.  
  35.    COMMENT
  36.       comment allez-vous implanter la fonction
  37.  
  38.    VALEUR DE RETOUR
  39.      Si x == 0, on retourne le code d'erreur 255
  40.      sinon, si x == 1, on retourne 0, puisque 2^0 = 1
  41.      etc.
  42.  
  43.    ------------------------------------------------------------------ */
  44. u32 msb( u32 x ) {
  45.    ...
  46.  
  47.    return ...;
  48. }
  49.  
  50. /* ------------------------------------------------------------------
  51.    QUOI
  52.      Fonction principale qui réalise les tests
  53.      
  54.    ------------------------------------------------------------------ */
  55. int main() {
  56.  
  57.     // Tests liés à la fonction msb(x)
  58.     TEST_IF_EQUAL( msb(   0 ), 255);
  59.     TEST_IF_EQUAL( msb(   1 ),   0);
  60.     TEST_IF_EQUAL( msb(   2 ),   1);
  61.     TEST_IF_EQUAL( msb( 255 ),   7);
  62.     TEST_IF_EQUAL( msb( 0x800F0000 ), 31);
  63.     ...
  64.     return EXIT_SUCCESS;
  65. }
  66.  
  67.  

Exercice 6.1

Ecrire une fonction u32 msb(u32 x) qui cherche le bit le plus significatif (most significant bit) d'un entier non signé. Le bit le plus significatif est le bit d'indice le plus haut qui est à 1.

La fonction doit retourner les valeurs suivantes :

  • pour $x=0$, on retourne $255$, il s'agit d'un code d'erreur, puisque la valeur $0$ correspond à la valeur que doit retourner la fonction pour $x=1$
  • pour $x=1$ ($2^0$), on retourne $0$
  • pour $x=2$ ($2^1$), on retourne $1$
  • pour $x=255$ ($1111\_1111_2$), on retourne $7$
  • pour $x=800F0000_{16}$, on retourne $31$

Pour aller plus loin

Il existe d'autres moyens d'obtenir cette valeur en utilisant

  • le type double du langage C/C++.
  • ou la fonction __builtin_clz du compilateur gcc/g++
  • ou l'instruction assembleur bsr

Exercice 6.2

Ecrire une fonction u32 popcnt(u32 x) qui calcule le nombre de bits à 1 dans $x$. popcnt est l'abréviation de population count.

La fonction doit retourner les valeurs suivantes :

  • pour $x=0$, on retourne $0$
  • pour $x=1$, on retourne $1$
  • pour $x=15$, on retourne $4$
  • pour $x=204=1100\_1100_2$, on retourne $4$
  • pour $x=FF\_FF\_FF\_FF_{16}$, on retourne $32$

Pour aller plus loin

Lire le chapitre 12 du livre Programmation Assembleur x86 32 et 64 bits sous Linux Ubuntu afin de comprendre comment on peut implanter cette fonction de manière efficace.

Exercice 6.3

Ecrire une fonction bool even(u32 x) qui indique si un nombre est pair.

Exercice 6.4

Ecrire une fonction bool is_power_of_2(u32 x) qui indique si le nombre x est une puissance de 2.

  • pour $x=0$, on retourne false
  • pour $x=1$, on retourne true
  • pour $x=2$, on retourne true
  • pour $x=3$, on retourne false
  • pour $x=255$, on retourne false

Pour aller plus loin

Bit Twiddling Hacks (que l'on peut traduire par bidouillage de bits)