Manipulation de bits

• Fonctions
• Puzzles
• Solutions

Fonctions

Le C possède plusieurs fonctions pour manipuler les bits d'une variable. Après l'introduction de ces fonctions, vous pourrez essayer de resoudre quelques petits puzzles.

• !x - Inverse logique, TRUE devient FALSE et vice versa (0! => 1; x! avec x≠0 => 0)
• ~x - Inverse binaire, chaque bit est inversé (~0110b => 1001b)
• a & b - ET binaire (0110b & 1100b => 0100b)
• a ¦ b - OU binaire (0110b ¦ 1100b => 1110b)
• a ^ b - OU exclusif (0110b ^ 1100b => 1010b)
• a >> b - Décalage droite de b bits
• a << b - Décalage gauche de b bits

  Note: x << 32 n'est pas la même chose que x << 31 << 1.

  Note: le standard C ne défini pas si le décalage à droite est logique ou arithmétique (dans le cas des nombres signés). Pour les type unsigned, le décalage est toujours logique.

Voici quelques petits puzzles. Le but est d'écrire quelques fonctions simple en utilisant un nombre restreint d'opérateurs et avec des constantes entre 0 et 255 seulement. Vous n'avez entre autre pas le droit d'utiliser de boucles, de conditionels, pointeurs, tableaux, macros, casts...

Vous devez aussi essayer de réduire le nombre d'opérations nécessaire dans chaque cas; c'est ça qui est le plus amusant. Si vous arrivez a améillorer la meilleur solution, contactez moi et vous aurez votre nom sur cette page (vous pouvez choisir entre publier votre solution, ou juste avoir votre nom avec votre performance. Si vous trouver une solution aussi optimale qu'une déjà présente, mais dont l'auteur à decidé de ne pas publier la solution, vous pouvez le faire).

Note: Vous pouvez utilisez autant de variables que vous voulez, l'assignation à une variable ne compte pas comme une instruction. Ainsi le code suivant a 5 instructions:

int foo(int x, int y) {
  int a = x & y;
  int b = (a ^ x) | y;
  int c = (a & b) | a;
  return c;
}

Puzzles

1. int bitOr(int x, int y)
   But: Calculer x | y (OU binaire) en utilisant seulement ~ et &.
   Example: bitOr(5, 9) = 13
   Difficulté:
   Opérateurs permis: ~ et &
   Meilleur solution: 4 instructions - Proposer une meilleur solution
   
2. int tmax(void)
   But: Retourner le plus grand entier positif (en complément à deux).
   Difficulté:
   Opérateurs permis: ! ~ & ^ | + << >>
   Meilleur solution: Proposer une solution
   
3. int evenBits(void)
   But: Retourner le nombre qui a tous ses bits pair à 1.
   Difficulté:
   Opérateurs permis: ! ~ & ^ | + <:< >>
   Meilleur solution: Proposer une solution
   
4. int getByte(int x, int n)
   But: Extraire le nième byte de x.
   Example: getByte(0x12345678, 1) = 0x56
   Difficulté:
   Opérateurs permis: ! ~ & ^ | + << >>
   Meilleur solution: Proposer une solution
   
5. int isNegative(int x)
   But: Retourner 1 si x < 0, sinon 0.
   Example: isNegative(-1) = 1
   Difficulté:
   Opérateurs permis: ! ~ & ^ | + << >>
   Meilleur solution: Proposer une solution
   
6. int bitMask(int h, int l)
   But: Générer un mask dont les bits de l à h sont à 1, et le reste à 0.
   Example: bitMask(5, 3) = 0x38
   Note: Vous pouvez assumer que 0≤l≤31 et que 0≤h≤31. Si l>h, alors le mask doit être nul.
   Difficulté:
   Opérateurs permis: ! ~ & ^ | + << >>
   Meilleur solution: 5 instructions - Proposer une meilleur solution
   
7. int reverseBytes(int x)
   But: Inverse les bytes de x.
   Example: reverseBytes(0x01020304) = 0x04030201
   Difficulté:
   Opérateurs permis: ! ~ & ^ | + << >>
   Meilleur solution: Proposer une solution
   
8. int isLess(int x, int y)
   But: Retourner 1 si x<y.
   Example: isLess(4, 5) = 1
   Difficulté:
   Opérateurs permis: ! ~ & ^ | + << >>
   Meilleur solution: Proposer une solution
   
9. int conditional(int x, int y, int z)
   But: Retourner y si x est TRUE sinon z (x ? y : z).
   Example: conditional(2, 4, 5) = 4
   Difficulté:
   Opérateurs permis: ! ~ & ^ | + << >>
   Meilleur solution: Proposer une solution
   
10. int logicalNeg(int x)
    But: Implémenter l'opérateur ! (non logique) sans utiliser !
    Example: logicalNeg(3) = 0, logicalNeg(0) = 1
    Difficulté:
    Opérateurs permis: ~ & ^ | + << >>
    Meilleur solution: Proposer une solution
    
11. int tc2sm(int x)
    But: Convertir le nombre x donné en complément à deux, en un nombre en magnitude-signée.
    Example: tc2sm(-5) = 0x80000005
    Difficulté:
    Opérateurs permis: ! ~ & ^ | + << >>
    Meilleur solution: Proposer une solution
    
12. int bitParity(int x)
    But: Retourner 1 si x contient un nombre impaire de 0.
    Example: bitParity(5) = 0, bitParity(7) = 1
    Difficulté:
    Opérateurs permis: ! ~ & ^ | + << >>
    Meilleur solution: Proposer une solution
    

Solutions

1. int bitOr(int x, int y)
   1/12/2003 Alok Menghrajani - 4 instructions
   Solution:
   

   /* en utilisant les règles de l'algèbre boolean */
   int bitOr(int x, int y) {
     return (~((~x) & (~y)));
   }
   

6. int bitMask(int h, int l)
   1/12/2003 Alok Menghrajani - 5 instructions
   Remarques: je préfère vous laisser chercher la réponse.
   
   
   30/11/2003 Example de solution - 25 instructions
   Remarques: Toutes les anciennes contributions restent.