Ho cercato di imparare il C nel mio tempo libero, e altri linguaggi (C#, Java, ecc.) hanno lo stesso concetto (e spesso gli stessi operatori)...
Quello che mi sto chiedendo è, ad un livello base, cosa fa il bit-shifting (<<
, >>
, >>
), quali problemi può aiutare a risolvere, e quali gotchas si nascondono dietro la curva? In altre parole, una guida per principianti assoluti al bit shifting in tutta la sua bontà.
Gli operatori di spostamento di bit fanno esattamente ciò che il loro nome implica. Spostano i bit. Ecco una breve (o meno breve) introduzione ai diversi operatori di spostamento.
>>
è l'operatore di spostamento aritmetico (o firmato) a destra.>>>
è l'operatore di spostamento a destra logico (o senza segno).<<
è l'operatore di spostamento a sinistra, e soddisfa i bisogni di entrambi gli spostamenti logici e aritmetici.Tutti questi operatori possono essere applicati a valori interi (int
, long
, eventualmente short
e byte
o char
). In alcuni linguaggi, applicando gli operatori di spostamento a qualsiasi tipo di dato più piccolo di int
, l'operando viene automaticamente ridimensionato per essere un int
.
Si noti che <<<
non è un operatore, perché sarebbe ridondante.
Si noti anche che C e C++ non distinguono tra gli operatori di spostamento a destra. Essi forniscono solo l'operatore >>
, e il comportamento di spostamento a destra è definito dall'implementazione per i tipi firmati. Il resto della risposta usa gli operatori C# / Java.
(In tutte le principali implementazioni C e C ++, compresi gcc e clang/LLVM, >>
sui tipi firmati è aritmetico. Alcuni codici assumono questo, ma non è qualcosa che lo standard garantisce. Non è non definito, però; lo standard richiede che le implementazioni lo definiscano in un modo o nell'altro. Tuttavia, lo spostamento a sinistra di numeri firmati negativi è un comportamento non definito (overflow di interi firmati). Quindi, a meno che non abbiate bisogno di uno spostamento aritmetico a destra, di solito è una buona idea fare il vostro spostamento di bit con tipi senza segno).
Gli interi sono memorizzati, in memoria, come una serie di bit. Per esempio, il numero 6 memorizzato come un int
a 32 bit sarebbe:
00000000 00000000 00000000 00000110
Spostando questo schema di bit a sinistra di una posizione (6 << 1
) si otterrebbe il numero 12:
00000000 00000000 00000000 00001100
Come puoi vedere, le cifre sono spostate a sinistra di una posizione, e l'ultima cifra a destra è riempita con uno zero. Potreste anche notare che lo spostamento a sinistra è equivalente alla moltiplicazione per potenze di 2. Quindi 6 << 1
è equivalente a 6 * 2
, e 6 << 3
è equivalente a 6 * 8
. Un buon compilatore ottimizzatore sostituirà le moltiplicazioni con gli spostamenti quando possibile.
Si prega di notare che questi sono non spostamenti circolari. Spostando questo valore a sinistra di una posizione (3.758.096.384 << 1
):
11100000 00000000 00000000 00000000
risulta in 3.221.225.472:
11000000 00000000 00000000 00000000
La cifra che viene spostata "fuori dalla fine" si perde. Non si avvolge.
Uno spostamento logico a destra è l'inverso dello spostamento a sinistra. Invece di spostare i bit a sinistra, si spostano semplicemente a destra. Per esempio, spostando il numero 12:
00000000 00000000 00000000 00001100
a destra di una posizione (12 >>>1
) riavremo il nostro 6 originale:
00000000 00000000 00000000 00000110
Così vediamo che lo spostamento a destra è equivalente alla divisione per potenze di 2.
Tuttavia, uno shift non può recuperare i bit "persi". Per esempio, se spostiamo questo schema:
00111000 00000000 00000000 00000110
a sinistra di 4 posizioni (939.524.102 << 4
), otteniamo 2.147.483.744:
10000000 00000000 00000000 01100000
e poi spostando indietro ((939.524.102 << 4) >>4
) otteniamo 134.217.734:
00001000 00000000 00000000 00000110
Non possiamo recuperare il nostro valore originale una volta che abbiamo perso dei bit.
Lo spostamento aritmetico a destra è esattamente come lo spostamento logico a destra, tranne che invece di riempire con lo zero, riempie con il bit più significativo. Questo perché il bit più significativo è il bit sign, o il bit che distingue i numeri positivi e negativi. Imbottendo con il bit più significativo, lo spostamento aritmetico a destra conserva il segno.
Per esempio, se interpretiamo questo schema di bit come un numero negativo:
10000000 00000000 00000000 01100000
abbiamo il numero -2.147.483.552. Spostando questo a destra di 4 posizioni con lo spostamento aritmetico (-2.147.483.552 >4) ci darebbe:
11111000 00000000 00000000 00000110
o il numero -134.217.722.
Così vediamo che abbiamo preservato il segno dei nostri numeri negativi usando lo spostamento aritmetico a destra, piuttosto che lo spostamento logico a destra. E ancora una volta, vediamo che stiamo eseguendo la divisione per potenze di 2.
Diciamo che abbiamo un singolo byte:
0110110
Applicando un singolo bitshift a sinistra otteniamo:
1101100
Lo zero più a sinistra è stato spostato fuori dal byte, e un nuovo zero è stato aggiunto all'estremità destra del byte.
I bit non si sovrappongono, vengono scartati. Ciò significa che se si sposta a sinistra 1101100 e poi a destra, non si otterrà lo stesso risultato.
Spostare a sinistra di N è equivalente a moltiplicare per 2N.
Spostare a destra di N è (se state usando uno'complemento) l'equivalente di dividere per 2N e arrotondare a zero.
Il bitshifting può essere usato per moltiplicazioni e divisioni follemente veloci, a patto che si lavori con una potenza di 2. Quasi tutte le routine grafiche di basso livello usano il bitshifting.
Per esempio, molto tempo fa, usavamo il modo 13h (320x200 256 colori) per i giochi. Nel modo 13h, la memoria video era disposta in modo sequenziale per pixel. Questo significava che per calcolare la posizione di un pixel, avreste usato la seguente matematica:
memoryOffset = (row * 320) + column
Ora, all'epoca, la velocità era fondamentale, quindi si usavano gli spostamenti di bit per fare questa operazione.
Tuttavia, 320 non è una potenza di due, quindi per aggirare questo problema dobbiamo trovare qual è una potenza di due che sommata fa 320:
(row * 320) = (row * 256) + (row * 64)
Ora possiamo convertire il tutto in turni di sinistra:
(row * 320) = (row << 8) + (row << 6)
Per un risultato finale di:
memoryOffset = ((row << 8) + (row << 6)) + column
Ora otteniamo lo stesso offset di prima, tranne che invece di una costosa operazione di moltiplicazione, usiamo i due bitshift... in x86 sarebbe qualcosa di simile a questo (nota, è passato un'eternità da quando ho fatto assembly (nota dell'editore: corretto un paio di errori e aggiunto un esempio a 32 bit)):
mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]
; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov
Totale: 28 cicli su qualunque CPU antica avesse questi tempi.
Vrs
mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6; 2
shl di, 8; 2
add di, ax; 2 (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]
12 cicli sulla stessa antica CPU.
Sì, lavoreremmo così duramente per risparmiare 16 cicli di CPU.
In modalità 32 o 64 bit, entrambe le versioni diventano molto più corte e veloci. Le moderne CPU ad esecuzione fuori ordine come Intel Skylake (vedi http://agner.org/optimize/) hanno moltiplicatori hardware molto veloci (bassa latenza e alto throughput), quindi il guadagno è molto più piccolo. AMD Bulldozer-family è un po' più lento, specialmente per i multipli a 64 bit. Sulle CPU Intel, e AMD Ryzen, due spostamenti sono leggermente più bassi di latenza ma più istruzioni di un multiplo (che può portare a un throughput inferiore):
imul edi, [row], 320 ; 3 cycle latency from [row] being ready
add edi, [column] ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column], in 4 cycles from [row] being ready.
vs.
mov edi, [row]
shl edi, 6 ; row*64. 1 cycle latency
lea edi, [edi + edi*4] ; row*(64 + 64*4). 1 cycle latency
add edi, [column] ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column], in 3 cycles from [row] being ready.
I compilatori lo faranno per voi: Guardate come gcc, clang, e MSVC usano tutti shift+lea quando ottimizzano return 320*row + col;
.
La cosa più interessante da notare qui è che x86 ha un'istruzione shift-and-add (LEA
) che può fare piccoli shift a sinistra e aggiungere allo stesso tempo, con le prestazioni di un'istruzione add
. ARM è ancora più potente: un operando di qualsiasi istruzione può essere spostato a sinistra o a destra gratuitamente. Quindi scalare per una costante di tempo di compilazione che è nota per essere una potenza di 2 può essere ancora più efficiente di un moltiplicatore.
OK, tornando ai tempi moderni... qualcosa di più utile ora sarebbe usare il bitshifting per memorizzare due valori a 8 bit in un intero a 16 bit. Per esempio, in C#:
// Byte1: 11110000
// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;
In C++, i compilatori dovrebbero farlo per te se usi una struct
con due membri a 8 bit, ma in pratica non lo fanno sempre.
Un problema è che quanto segue dipende dall'implementazione (secondo lo standard ANSI):
char x = -1;
x >> 1;
x può ora essere 127 (01111111) o ancora -1 (11111111).
In pratica, di solito è la seconda.