Risposta.

L'operazione di rotazione circolare (rotary/circular shift) è uno spostamento dei bit di un numero di un certo numero di posizioni con il riutilizzo dei bit "persi" all'estremità opposta. Nel linguaggio C non esiste un operatore incorporato per questo compito; tale soluzione è storicamente legata alla portabilità della libreria standard e alla necessità di definire esplicitamente il comportamento per diverse piattaforme.

Il problema è che gli operatori di shift standard (<<, >>) non effettuano uno shift circolare: spostano solo i bit e i "persi" vengono sostituiti da zeri. Per lo shift circolare è necessario combinare esplicitamente i risultati di due shift e mascherare il risultato con il numero di bit specificato.

La soluzione è implementare lo shift circolare manualmente. Per un numero unsigned a 32 bit, appare così:

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));
}

Caratteristiche chiave:

Nessun operatore incorporato di rotary shift in C.
È necessario combinare manualmente i due shift e la maschera.
Si deve considerare la dimensione del tipo di dato (bit) per la portabilità.

Domande trabocchetto.

L'operatore << o >> può implementare uno shift circolare senza operazioni aggiuntive?

No. I normali shift sostituiscono i bit che escono dai limiti con zeri, non li traslano dall'altra parte.

Cosa succede se si effettua uno shift della dimensione del tipo (shift uguale al numero di bit del numero)?

Il comportamento non è definito (Undefined Behavior secondo lo standard C), è necessario effettuare sempre lo shift modulo la dimensione del tipo.

È sicuro effettuare un rotary shift con questi operatori per i tipi signed?

No, utilizza sempre tipi unsigned, poiché gli shift bit a bit per i tipi signed si comportano diversamente a seconda del compilatore e dell'architettura.

Errori tipici e anti-pattern

Uso di tipi signed invece di unsigned per gli shift bit.
Mancata considerazione della dimensione del tipo (ad esempio, 32 contro 64 bit).
Assenza di mascheramento dello shift (ad esempio, non applicare shift = shift % 32 per numeri a 32 bit).

Esempio dalla vita reale

Caso negativo

Utilizzare uno shift normale per uno spostamento circolare:

uint32_t x = 0xFA3C0F00;
uint32_t y = x << 5; // Non ha carattere circolare

Vantaggi:

Semplicità di scrittura.

Svantaggi:

I bit vengono persi, il comportamento non corrisponde alle aspettative, bug difficili da individuare in programmi crittografici e nell'elaborazione dati.

Caso positivo

Utilizzare una funzione manuale di rotary shift tenendo conto della dimensione del tipo e proteggendosi dall'UB:

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