Operazione bit a bit

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

Bit addressingEdit

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 spostamento inducono uno schema di indirizzamento sui bit.Ignorando gli effetti di contorno ad entrambe le estremità del registro, le operazioni di spostamento aritmetiche e logiche si comportano allo stesso modo e uno spostamento di 8 posizioni di bit trasporta il modello di bit di 1 posizione di byte nel modo seguente:

Aritmetica shiftEdit

a Sinistra shift aritmetico

shift aritmetico a Destra

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

Questo esempio utilizza 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 verso l’esterno (forse nel flag carry) e un nuovo 1 è stato copiato nella posizione più a sinistra, preservando il segno del numero. I turni multipli sono talvolta abbreviati in un singolo turno di un certo numero di cifre. Ad esempio:

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

Uno spostamento aritmetico sinistro per n equivale a moltiplicare per 2n (a condizione che il valore non trabocchi), mentre uno spostamento aritmetico destro per n del valore del complemento di due equivale a dividere per 2n e arrotondare verso l’infinito negativo. Se il numero binario viene trattato come complemento, la stessa operazione di spostamento a destra determina la divisione per 2n e l’arrotondamento verso zero.

Logical shiftEdit

shift logico a Sinistra

a Destra shift logico

In una logica di spostamento, gli zeri sono spostati a sostituire il scartato bit. Pertanto, gli spostamenti a sinistra logici e aritmetici sono esattamente gli stessi.

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

Circular Shift

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

RotateEdit

a Sinistra circolare spostamento o rotazione

circolare Destra maiusc o ruotare

In questa operazione, a volte chiamato ruotare carry, i bit sono “ruotato”, come se l’estremità sinistra e destra del registro unite. Il valore che viene spostato a destra durante uno spostamento a sinistra è qualsiasi valore sia stato spostato a sinistra e viceversa per un’operazione di spostamento a destra. Questo è utile se è necessario mantenere tutti i bit esistenti, ed è spesso usato nella crittografia digitale.

Ruotare attraverso carryEdit

a Sinistra ruota attraverso trasportare

a Destra rotazione attraverso trasportare

Ruotare attraverso il carry è una variante dell’operazione di rotazione, dove il bit che viene spostato in (su entrambe le estremità) è il vecchio valore del carry flag e bit che viene spostato fuori (all’altra estremità) diventa il nuovo valore del carry flag.

Una singola rotazione tramite carry può simulare uno spostamento logico o aritmetico di una posizione impostando preventivamente il flag carry. Ad esempio, se il flag carry contiene 0, x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE è uno spostamento logico a destra e se il flag carry contiene una copia del bit del segno, x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE è uno spostamento aritmetico a destra. Per questo motivo, alcuni microcontrollori come le FOTO di fascia bassa hanno solo rotazione e rotazione tramite carry e non si preoccupano delle istruzioni di spostamento aritmetiche o logiche.

Ruota attraverso carry è particolarmente utile quando si eseguono turni su numeri più grandi della dimensione nativa della parola del processore, perché se un numero elevato è memorizzato in due registri, il bit che viene spostato da un’estremità del primo registro deve entrare all’altra estremità del secondo. Con rotate-through-carry, quel bit viene “salvato” nel flag carry durante il primo turno, pronto a passare durante il secondo turno senza alcuna preparazione aggiuntiva.

In lingue di alto livellomodifica

C-familyEdit

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

x = y << 2;

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

I turni possono comportare un comportamento definito dall’implementazione o un comportamento indefinito, quindi è necessario prestare attenzione quando li si utilizza. Il risultato dello spostamento di un conteggio di bit maggiore o uguale alla dimensione della parola è un comportamento indefinito in C e C++. Spostamento a destra un valore negativo è definito dall’implementazione e non raccomandato dalla buona pratica di codifica; il risultato dello spostamento a sinistra di un valore firmato non è definito 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.

Circular shiftsEdit

La famiglia C di linguaggi non ha un operatore di rotazione, ma uno può essere sintetizzato dagli operatori di spostamento. È necessario prestare attenzione per garantire che la dichiarazione sia ben formata per evitare comportamenti indefiniti e attacchi di temporizzazione nel software con requisiti di sicurezza. Ad esempio, un’implementazione ingenua che a sinistra ruota un valore senza segno a 32 bit x per n posizioni è semplicemente:

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

Tuttavia, uno spostamento di 0 bit determina un comportamento indefinito nell’espressione di destra (x >> (32 - n)) perché 32 - 0 è 32 e 32 è al di fuori dell’intervallo incluso. Un secondo tentativo potrebbe comportare:

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

dove viene testato l’importo del turno per garantire che non introduca un comportamento indefinito. Tuttavia, il ramo aggiunge un percorso di codice aggiuntivo e presenta un’opportunità per l’analisi dei tempi e l’attacco, che spesso non è accettabile nei software ad alta integrità. Inoltre, il codice viene compilato in più istruzioni della macchina, che spesso è meno efficiente dell’istruzione nativa del processore.

Per evitare il comportamento indefinito e i rami sotto GCC e Clang, si consiglia di quanto segue. Il modello è riconosciuto da molti compilatori e il compilatore emetterà una singola istruzione di rotazione:

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

Esistono anche intrinseche specifiche del compilatore che implementano turni circolari, come _rotl8, _rotl16, _rotr8, _rotr16 in Microsoft Visual C++. Clang fornisce alcune intrinseche di rotazione per la compatibilità Microsoft che soffre i problemi di cui sopra. GCC non offre intrinseche di rotazione. Intel fornisce anche intrinseche x86.

JavaEdit

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

Maggiori dettagli sugli operatori Java shift:

• Gli operatori << (spostamento a sinistra), >> (spostamento a destra con segno) e >>> (spostamento a destra senza segno) sono chiamati operatori di spostamento.
• Il tipo di espressione shift è il tipo promosso dell’operando di sinistra. Ad esempio, aByte >>> 2 equivale a ((int) aByte) >>> 2.
• Se il tipo promosso dell’operando di sinistra è int, solo i cinque bit di ordine più basso dell’operando di destra vengono utilizzati come distanza di spostamento. È come se l’operando di destra fosse sottoposto a un operatore AND logico bit per bit & con il valore di maschera 0x1f (0b11111). La distanza di spostamento effettivamente utilizzata è quindi sempre compresa tra 0 e 31.
• Se il tipo promosso dell’operando di sinistra è lungo, solo i sei bit di ordine più basso dell’operando di destra vengono utilizzati come distanza di spostamento. È come se l’operando di destra fosse sottoposto a un operatore AND logico bit per bit & con il valore di maschera 0x3f (0b111111). La distanza di spostamento effettivamente utilizzata è quindi sempre compresa tra 0 e 63.
• Il valore di n >>> s è n posizioni di bit s spostate a destra con estensione zero.
• Nelle operazioni di bit e shift, il tipo byteviene convertito implicitamente in int. Se il valore del byte è negativo, il bit più alto è uno, quindi quelli vengono utilizzati per riempire i byte aggiuntivi nell’int. Quindi byte b1 = -5; int i = b1 | 0x0200; si tradurrà ini == -5 .

JavaScriptEdit

JavaScript utilizza operazioni bit a bit per valutare ciascuna delle 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 di spostamento logico sinistro e destro sono rispettivamente “shl ” e ” shr“. Anche per gli interi con segno, shr si comporta come uno spostamento logico e non copia il bit del segno. Il numero di posti da spostare è dato come secondo argomento. Ad esempio, quanto segue assegna x il risultato dello spostamento di y a sinistra di due bit:

x := y shl 2;