Décaler les bits

Exercice 1

On dispose de l'écriture binaire d'un entier d. On ajoute un 0 à la fin (à droite) de cette écriture pour obtenir un entier f.
Quelle opération permet de passer de l'entier d à l'entier f?

Exemples:

• d = 11_deux donne f = 110_deux.
• d = 1010_deux donne f = 10100_deux.

Solution

Cette opération revient à multiplier l'entier par 2: f = 2d.

Pour bien comprendre cela, écrivons le détail sur les exemples donnés.

• 11_deux = 1 × 2¹ + 1 × 2⁰.
  On ajoute un 0 en fin d'écriture:
  110_deux = 1 × 2² + 1 × 2¹ + 0 × 2⁰
  soit 110_deux = 2 × (1 × 2¹ + 1 × 2⁰),
  c'est à dire: 110_deux = 2 × 11_deux.

• 1010_deux = 1 × 2³ + 0 × 2² + 1 × 2¹ + 0 × 2⁰
  et 10100_deux = 1 × 2⁴ + 0 × 2³ + 1 × 2² + 0 × 2¹ + 0 × 2⁰
  soit 10100_deux = 2 × (1 × 2³ + 0 × 2² + 1 × 2¹ + 0 × 2⁰)
  c'est à dire 10100_deux = 2 × 1010_deux.

Exercice 2

On dispose de l'écriture binaire d'un entier d. On supprime le chiffre le plus à droite de cette écriture.
Quel lien entre l'entier d de départ et l'entier f obtenu ?

Exemples:

• Pour d = 110_deux, on a f = 11_deux.
• Pour d = 1101_deux, on a f = 110_deux.

Solution

f est le quotient de la division euclidienne de d par 2. On a donc f = d//2.

Pour bien comprendre cela, détaillons sur les exemples:

• d = 110_deux, soit d = 1 × 2² + 1 × 2¹ + 0 × 2⁰, soit d = 2 × ( 1 × 2¹ + 1 × 2⁰) + 0. On a écrit d sous la forme 2q+0 où q est entier: le 0 final est le reste de la division de d par 2 et q est le quotient.
  Barrer le 0 final revient à remplacer d par q (on a q = f).

• d = 1101_deux, soit d = 1 × 2³ + 1 × 2² + 0 × 2¹ + 1 × 2⁰.
  Soit d = 2 × (1 × 2² + 1 × 2¹ + 0 × 2⁰) + 1.
  Le 1 final est le reste de la division de d par 2 et le nombre f est le quotient.