Les décalages binaires (bitwise shifts)

Les décalages binaires sont des opérations effectuées directement sur les bits d’un nombre binaire, consistant à déplacer les bits vers la gauche ou vers la droite. Ces opérations sont très courantes en informatique et en programmation, car elles permettent d’effectuer des opérations arithmétiques rapides (comme la multiplication ou la division par des puissances de 2), des manipulations de bits, et des optimisations dans certains algorithmes.

Il existe deux principaux types de décalages binaires :

Décalage à gauche (left shift) : déplace les bits vers la gauche.
Décalage à droite (right shift) : déplace les bits vers la droite.

En plus des décalages arithmétiques, il y a des décalages logiques et arithmétiques, chacun ayant un comportement légèrement différent, en particulier pour les nombres signés.

1. Décalage à gauche (Left Shift)

Un décalage à gauche (noté <<) déplace tous les bits d’un nombre vers la gauche d’un certain nombre de positions. Les zéros sont insérés à droite, et les bits à gauche qui sont déplacés hors de la plage sont perdus.

Fonctionnement :

Chaque décalage à gauche d’un bit correspond à une multiplication par 2.

Exemple :

Décalons 5 (représenté par 00000101 en binaire sur 8 bits) de 1 bit vers la gauche.

00000101 << 1 = 00001010

Cela correspond à 10 en décimal (soit 5 × 2 = 10).

Si nous décalons encore de 1 bit, nous obtenons :

00001010 << 1 = 00010100

Cela correspond à 20 en décimal (soit 10 × 2 = 20).

Propriétés :

Un décalage à gauche de n bits multiplie un nombre par 2ⁿ.
Les bits décalés à gauche sont perdus (coupés) si la représentation binaire n’a pas assez de bits.

2. Décalage à droite (Right Shift)

Un décalage à droite (noté >>) déplace tous les bits d’un nombre vers la droite d’un certain nombre de positions. Selon le type de décalage à droite (logique ou arithmétique), des zéros ou des copies du bit de signe sont insérés à gauche.

Types de décalages à droite :

Décalage logique à droite : des zéros sont insérés à gauche, et les bits décalés hors de la plage à droite sont perdus. Ce type de décalage est utilisé pour les nombres non signés.
Décalage arithmétique à droite : le bit de signe (MSB) est copié lors du décalage. Cela permet de préserver le signe du nombre. Ce type de décalage est utilisé pour les nombres signés.

Fonctionnement :

Chaque décalage à droite d’un bit correspond à une division par 2 (sans la partie décimale).

Exemple : Décalage logique à droite

Décalons 12 (représenté par 00001100 en binaire sur 8 bits) de 1 bit vers la droite :

00001100 >> 1 = 00000110

Cela correspond à 6 en décimal (soit 12 ÷ 2 = 6).

Si nous décalons encore de 1 bit, nous obtenons :

00000110 >> 1 = 00000011

Cela correspond à 3 en décimal (soit 6 ÷ 2 = 3).

Exemple : Décalage arithmétique à droite

Prenons -12 en complément à deux sur 8 bits : 11110100 (représentation de -12).

Un décalage arithmétique à droite d’un bit copierait le bit de signe (le bit à gauche) à chaque itération :

11110100 >> 1 = 11111010

Cela correspond à -6 en binaire signé (complément à deux), car le bit de signe a été conservé.

Propriétés :

Un décalage à droite de n bits divise un nombre par 2ⁿ (avec troncature).
Les décalages arithmétiques à droite préservent le signe du nombre, car le bit de signe est copié.
Les décalages logiques à droite insèrent des zéros à gauche, ce qui convient aux nombres non signés.

3. Décalage logique vs. arithmétique

Décalage logique : Utilisé principalement pour les nombres non signés. Il insère toujours des zéros dans les bits déplacés à gauche ou à droite, peu importe le signe.
Décalage arithmétique : Utilisé pour les nombres signés. Il conserve le bit de signe lors des décalages à droite pour maintenir le signe du nombre.

Exemple : Décalage logique vs arithmétique

Prenons le nombre -8 (en complément à deux sur 8 bits) : 11111000.

Décalage logique à droite (>>) : 01111100 → Cela donne un résultat positif (inapproprié pour un nombre signé).
Décalage arithmétique à droite (>>) : 11111100 → Le bit de signe est conservé, et le résultat reste négatif.

4. Applications des décalages binaires

Les décalages binaires sont très couramment utilisés en informatique et en programmation pour plusieurs raisons :

1. Multiplication et division rapide par des puissances de 2

Les décalages binaires permettent de multiplier ou de diviser un nombre par des puissances de 2 de manière extrêmement rapide et efficace, en évitant les opérations arithmétiques traditionnelles.

Décalage à gauche : Multiplie par 2ⁿ.
Décalage à droite : Divise par 2ⁿ.

2. Manipulation des bits (bitwise operations)

Les décalages sont également utilisés pour manipuler les bits d’un nombre. Par exemple, ils permettent d’extraire des bits spécifiques dans une séquence binaire, de compresser des données, ou d’effectuer des opérations sur des drapeaux (flags).

3. Optimisation dans les algorithmes

Dans certains algorithmes de cryptographie, d’encodage, ou de compression, les décalages binaires sont utilisés pour des opérations de transformation de bits rapides, telles que l’alignement des données, le codage des nombres ou le chiffrement.

4. Masquage de bits (bit masking)

En combinaison avec des opérations logiques comme le ET logique (&), les décalages peuvent être utilisés pour masquer ou extraire des bits spécifiques. Par exemple, vous pouvez utiliser un décalage à droite pour déplacer des bits significatifs vers une position spécifique, puis appliquer un masque pour isoler ces bits.

Les décalages binaires sont des opérations essentielles pour manipuler et traiter les bits dans les ordinateurs. Les deux principales opérations de décalage, à gauche et à droite, permettent de multiplier et diviser par des puissances de 2 de manière rapide et efficace. En fonction du type de décalage (logique ou arithmétique), les bits peuvent être remplis avec des zéros ou avec des copies du bit de signe, ce qui est important pour gérer les nombres signés.

Ces opérations sont couramment utilisées pour l’optimisation, le traitement rapide des données, et la manipulation des bits dans divers algorithmes informatiques.