Operazione bitwise

Gli spostamenti di bit sono talvolta considerati operazioni bitwise, perché trattano un valore come una serie di bit piuttosto che come una quantità numerica. In queste operazioni le cifre vengono spostate, o spostati, a sinistra o a destra. I registri in un processore di computer hanno una larghezza fissa, quindi alcuni bit saranno “spostati fuori” dal registro ad un’estremità, mentre lo stesso numero di bit sono “spostati dentro” dall’altra estremità; le differenze tra gli operatori di bit shift stanno nel modo in cui determinano i valori dei bit spostati dentro.

Indirizzamento dei bitModifica

Se la larghezza del registro (spesso 32 o anche 64) è maggiore del numero di bit (di solito 8) della più piccola unità indirizzabile (elemento atomico), spesso chiamata byte, le operazioni di shift inducono uno schema di indirizzamento sui bit.Trascurando gli effetti di confine alle due estremità del registro, le operazioni di spostamento aritmetico e logico si comportano allo stesso modo, e uno spostamento di 8 posizioni di bit trasporta lo schema di bit di 1 posizione di byte nel modo seguente:

Shift aritmeticoEdit

Spostamento aritmetico a sinistra

Spostamento aritmetico a destra

In uno spostamento aritmetico, i bit che vengono spostati fuori da entrambe le estremità vengono scartati. In uno spostamento aritmetico a sinistra, gli zeri sono spostati a destra; in uno spostamento aritmetico a destra, il bit di segno (il MSB nel complemento a due) è spostato a sinistra, conservando così il segno dell’operando.

Questo esempio usa un registro a 8 bit, interpretato come complemento a due:

 00010111 (decimal +23) LEFT-SHIFT= 00101110 (decimal +46)

 10010111 (decimal −105) RIGHT-SHIFT= 11001011 (decimal −53)

Nel primo caso, la cifra più a sinistra è stata spostata oltre la fine del registro, e un nuovo 0 è stato spostato nella posizione più a destra. Nel secondo caso, l’1 più a destra è stato spostato fuori (forse nel flag di riporto), e un nuovo 1 è stato copiato nella posizione più a sinistra, conservando il segno del numero. Gli spostamenti multipli sono talvolta abbreviati in un singolo spostamento di un certo numero di cifre. Per esempio:

 00010111 (decimal +23) LEFT-SHIFT-BY-TWO= 01011100 (decimal +92)

Uno spostamento aritmetico a sinistra di n è equivalente alla moltiplicazione per 2n (a condizione che il valore non trabocchi), mentre uno spostamento aritmetico a destra di n di un valore di complemento a due è equivalente alla divisione per 2n e all’arrotondamento all’infinito negativo. Se il numero binario è trattato come complemento a uno, allora la stessa operazione di spostamento a destra risulta nella divisione per 2n e nell’arrotondamento verso lo zero.

Spostamento logicoModifica

Spostamento logico a sinistra

Spostamento logico a destra

In uno spostamento logico, gli zeri vengono spostati per sostituire i bit scartati. Pertanto, gli spostamenti logici e aritmetici a sinistra sono esattamente gli stessi.

Tuttavia, poiché lo spostamento logico a destra inserisce bit di valore 0 nel bit più significativo, invece di copiare il bit di segno, è ideale per i numeri binari senza segno, mentre lo spostamento aritmetico a destra è ideale per i numeri binari a due complementi di segno.

Circular shiftEdit

Un’altra forma di spostamento è lo spostamento circolare, rotazione bitwise o rotazione bit.

RotateEdit

Spostamento o rotazione circolare a sinistra

Spostamento circolare a destra o rotate

In questa operazione, a volte chiamata rotate no carry, i bit sono “ruotati” come se le estremità sinistra e destra del registro fossero unite. Il valore che viene spostato a destra durante un left-shift è qualunque valore sia stato spostato a sinistra, e viceversa per un’operazione di right-shift. Questo è utile se è necessario mantenere tutti i bit esistenti, ed è frequentemente usato nella crittografia digitale.

Ruota attraverso carryEdit

Ruota a sinistra attraverso il trasporto

Ruota a destra attraverso il riporto

Rotate through carry è una variante dell’operazione di rotazione, dove il bit che viene spostato all’interno (da una parte o dall’altra) è il vecchio valore del flag di trasporto, e il bit che viene spostato all’esterno (dall’altra parte) diventa il nuovo valore del flag di trasporto.

Un singolo rotate through carry può simulare uno spostamento logico o aritmetico di una posizione impostando il carry flag in anticipo. Per esempio, se il carry flag contiene 0, allora x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE è uno spostamento logico a destra, e se il carry flag contiene una copia del bit di segno, allora x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE è uno spostamento aritmetico a destra. Per questo motivo, alcuni microcontrollori come i PIC di fascia bassa hanno solo rotate e rotate through carry, e non si preoccupano delle istruzioni di spostamento aritmetico o logico.

Rotate through carry è particolarmente utile quando si eseguono spostamenti su numeri più grandi della dimensione nativa della parola del processore, perché se un numero grande è memorizzato in due registri, il bit che viene spostato da un’estremità del primo registro deve arrivare all’altra estremità del secondo. Con rotate-through-carry, quel bit viene “salvato” nel flag di trasporto durante il primo spostamento, pronto per essere spostato durante il secondo spostamento senza alcuna preparazione extra.

Nei linguaggi di alto livelloModifica

C-familyEdit

Nei linguaggi C-family, gli operatori logici di spostamento sono “<<” per lo spostamento a sinistra e “>>” per lo spostamento a destra. Il numero di posti da spostare è dato come secondo argomento all’operatore. Per esempio,

x = y << 2;

assegna x il risultato dello spostamento y a sinistra di due bit, che è equivalente a una moltiplicazione per quattro.

Gli spostamenti possono risultare in un comportamento definito dall’implementazione o in un comportamento non definito, quindi bisogna fare attenzione quando li si usa. Il risultato dello spostamento di un numero di bit maggiore o uguale alla dimensione della parola è un comportamento non definito in C e C++. Lo spostamento a destra di un valore negativo è definito dall’implementazione e non raccomandato dalla buona pratica di codifica; il risultato dello spostamento a sinistra di un valore firmato è indefinito se il risultato non può essere rappresentato nel tipo di risultato.

In C#, lo spostamento a destra è uno spostamento aritmetico quando il primo operando è un int o long. Se il primo operando è di tipo uint o ulong, lo spostamento a destra è uno spostamento logico.

Spostamento circolareModifica

I linguaggi della famiglia C mancano di un operatore di rotazione, ma uno può essere sintetizzato dagli operatori di spostamento. Bisogna fare attenzione a garantire che la dichiarazione sia ben formata per evitare un comportamento indefinito e attacchi temporali nel software con requisiti di sicurezza. Per esempio, un’implementazione ingenua che ruota a sinistra un valore senza segno a 32 bit x di n posizioni è semplicemente:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (32 - n));

Tuttavia, uno spostamento di 0 bit risulta in un comportamento non definito nell’espressione di destra (x >> (32 - n)) perché 32 - 032, e 32 è fuori dall’intervallo compreso. Un secondo tentativo potrebbe risultare in:

uint32_t x = ..., n = ...;uint32_t y = n ? (x << n) | (x >> (32 - n)) : x;

dove l’importo dello spostamento viene testato per assicurarsi che non introduca un comportamento non definito. Tuttavia, il ramo aggiunge un ulteriore percorso di codice e presenta un’opportunità per l’analisi dei tempi e l’attacco, che spesso non è accettabile nel software ad alta integrità. Inoltre, il codice si compila in più istruzioni macchina, che è spesso meno efficiente dell’istruzione nativa del processore.

Per evitare il comportamento non definito e i rami sotto GCC e Clang, si raccomanda quanto segue. Il modello è riconosciuto da molti compilatori, e il compilatore emetterà una singola istruzione rotate:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (-n & 31));

Ci sono anche intrinseci specifici del compilatore che implementano spostamenti circolari, come _rotl8, _rotl16, _rotr8, _rotr16 in Microsoft Visual C++. Clang fornisce alcune intrinseche di rotazione per la compatibilità con Microsoft che soffrono dei problemi di cui sopra. GCC non offre intrinseci di rotazione. Intel fornisce anche intrinseci x86.

JavaEdit

In Java, tutti i tipi interi sono firmati, quindi gli operatori “<<” e “>>” eseguono spostamenti aritmetici. Java aggiunge l’operatore “>>>” per eseguire spostamenti logici a destra, ma poiché le operazioni logiche e aritmetiche di spostamento a sinistra sono identiche per gli interi firmati, non esiste un operatore “<<<” in Java.

Altri dettagli sugli operatori di spostamento Java:

• Gli operatori << (spostamento a sinistra), >> (spostamento a destra firmato), e >>> (spostamento a destra non firmato) sono chiamati operatori di spostamento.
• Il tipo dell’espressione shift è il tipo promosso dell’operando di sinistra. Per esempio, aByte >>> 2 è equivalente a ((int) aByte) >>> 2.
• Se il tipo promosso dell’operando di sinistra è int, solo i cinque bit di ordine inferiore dell’operando di destra sono usati come distanza di spostamento. È come se l’operando di destra fosse sottoposto a un operatore logico bitwise AND & con il valore della maschera 0x1f (0b11111). La distanza di spostamento effettivamente utilizzata è quindi sempre nell’intervallo da 0 a 31, incluso.
• Se il tipo promosso dell’operando di sinistra è lungo, allora solo i sei bit di ordine inferiore dell’operando di destra sono utilizzati come distanza di spostamento. È come se l’operando di destra fosse sottoposto a un operatore logico bitwise AND & con il valore della maschera 0x3f (0b111111). La distanza di spostamento effettivamente utilizzata è quindi sempre nell’intervallo da 0 a 63, compreso.
• Il valore di n >>> s è n posizioni s bit spostate a destra con estensione zero.
• Nelle operazioni di bit e shift, il tipo byte è implicitamente convertito in int. Se il valore del byte è negativo, il bit più alto è uno, quindi gli uno sono usati per riempire i byte extra nell’int. Quindi byte b1 = -5; int i = b1 | 0x0200; risulterà i == -5.

JavaScriptEdit

JavaScript usa operazioni bitwise per valutare ciascuna di due o più unità posto a 1 o 0.

PascalEdit

In Pascal, così come in tutti i suoi dialetti (come Object Pascal e Standard Pascal), gli operatori logici di spostamento sinistro e destro sono rispettivamente “shl” e “shr“. Anche per gli interi firmati, shr si comporta come uno spostamento logico, e non copia il bit di segno. Il numero di posti da spostare è dato come secondo argomento. Per esempio, il seguente assegna a x il risultato dello spostamento di y a sinistra di due bit:

x := y shl 2;