Réponse.

L'opération de décalage circulaire (rotary/circular shift) consiste à déplacer les bits d'un nombre d'un certain nombre de positions tout en transférant les bits "sortis" à l'autre extrémité. En C, il n'existe pas d'opérateur intégré pour cette tâche ; cette situation est historiquement liée à la portabilité de la bibliothèque standard et à la nécessité de définir explicitement le comportement pour différentes plateformes.

Le problème est que les opérateurs de décalage standard (<<, >>) ne rendent pas le décalage circulaire : ils déplacent seulement les bits, et les bits "sortis" sont remplacés par des zéros. Pour effectuer un décalage circulaire, il faut combiner explicitement les résultats de deux décalages et masquer le résultat avec un nombre de bits donné.

La solution consiste à implémenter le décalage circulaire manuellement. Pour un entier non signé de 32 bits, cela se présente comme suit :

uint32_t rotate_left(uint32_t value, unsigned int shift) {
    return (value << shift) | (value >> (32 - shift));
}

uint32_t rotate_right(uint32_t value, unsigned int shift) {
    return (value >> shift) | (value << (32 - shift));
}

Caractéristiques clés :

Il n’existe pas d’opérateur de décalage circulaire intégré en C.
Il faut combiner manuellement deux décalages et utiliser un masque.
Il est impératif de prendre en compte la taille du type de données (bits) pour garantir la portabilité.

Questions piégeuses.

L'opérateur << ou >> peut-il implémenter un décalage circulaire sans opérations supplémentaires ?

Non. Les décalages normaux remplacent les bits sortis par des zéros et ne les déplacent pas de l’autre côté.

Que se passe-t-il si on décale de la taille du type (shift vaut le nombre de bits dans le nombre) ?

Le comportement est indéfini (Undefined Behavior selon la norme C), il est donc impératif de faire un décalage modulo la taille du type.

Pour les types signés, est-il sûr d'appliquer un décalage circulaire avec ces fonctions ?

Non, utilisez toujours des types non signés, car les décalages bit-à-bit pour les types signés se comportent différemment selon le compilateur et l'architecture.

Erreurs typiques et anti-patrons

Utiliser des types signés au lieu de non signés pour les décalages bit-à-bit.
Ne pas tenir compte de la taille du type (par exemple, 32 contre 64 bits).
Absence de masquage du décalage (par exemple, ne pas faire shift = shift % 32 pour les nombres de 32 bits).

Exemple concret

Cas négatif

Utilisation d'un décalage normal pour un décalage circulaire :

uint32_t x = 0xFA3C0F00;
uint32_t y = x << 5; // Ne porte pas le caractère circulaire

Avantages :

Simplicité d’écriture.

Inconvénients :

Les bits sont perdus, le comportement ne correspond pas aux attentes, ce qui peut créer un bogue difficile à détecter dans des programmes cryptographiques et de traitement de données.

Cas positif

Utilisation d'une fonction manuelle de décalage circulaire en tenant compte de la taille du type et de la protection contre l'UB :

uint32_t x = 0xFA3C0F00;
uint32_t y = rotate_left(x, 5);