Cosa sono gli operatori bitwise shift (bit-shift) e come funzionano?
https://stackoverflow.com/questions/141525
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho cercato di imparare la C nel mio tempo libero e altre lingue (C #, Java, ecc.) hanno lo stesso concetto (e spesso gli stessi operatori) ...
Quello che mi chiedo è, a livello centrale, cosa fa il bit-shifting (<<, >>, >>>), quali problemi può aiutare a risolvere e quali aspetti si nascondono dietro la curva? In altre parole, una guida per principianti assoluti allo spostamento dei bit in tutta la sua bontà.
Soluzione
Gli operatori di spostamento dei bit fanno esattamente ciò che implica il loro nome. Spostano i bit. Ecco una breve (o non così breve) introduzione ai diversi operatori di turno.
Gli operatori
-
>>è l'operatore di spostamento a destra aritmetico (o firmato). -
>>>è l'operatore di spostamento a destra logico (o senza segno). -
<<è l'operatore di spostamento a sinistra e soddisfa le esigenze sia dei turni logici che aritmetici.
Tutti questi operatori possono essere applicati a valori interi (int, long, possibilmente short e byte o char). In alcune lingue, l'applicazione degli operatori di turno a qualsiasi tipo di dati inferiore a <<< ridimensiona automaticamente l'operando come 6 << 1.
Nota che 6 * 2 non è un operatore, perché sarebbe ridondante. Si noti inoltre che C e C ++ non fanno distinzione tra gli operatori di spostamento a destra. Forniscono solo l'operatore 6 << 3 e il comportamento con spostamento a destra è l'implementazione definita per i tipi firmati.
Spostamento a sinistra (< <)
I numeri interi sono memorizzati, in memoria, come una serie di bit. Ad esempio, il numero 6 memorizzato come 6 * 8 a 32 bit sarebbe:
00000000 00000000 00000000 00000110
Spostando questo schema di bit verso sinistra in una posizione (3,758,096,384 << 1) si otterrebbe il numero 12:
00000000 00000000 00000000 00001100
Come puoi vedere, le cifre si sono spostate a sinistra di una posizione e l'ultima cifra a destra è riempita con uno zero. Potresti anche notare che lo spostamento a sinistra equivale alla moltiplicazione per potenze di 2. Quindi 12 >>> 1 è equivalente a 939,524,102 << 4 e (939,524,102 << 4) >>> 4 è equivalente a <=>. Un buon compilatore di ottimizzazione sostituirà le moltiplicazioni con turni quando possibile.
Spostamento non circolare
Si noti che si tratta di non spostamenti circolari. Spostando questo valore a sinistra di una posizione (<=>):
11100000 00000000 00000000 00000000
risulta in 3.221.225.472:
11000000 00000000 00000000 00000000
La cifra che viene spostata " dalla fine " è perduto. Non si avvolge.
Spostamento destro logico (> > >)
Uno spostamento logico a destra è il contrario dello spostamento a sinistra. Invece di spostare i bit verso sinistra, si spostano semplicemente verso destra. Ad esempio, spostando il numero 12:
00111000 00000000 00000000 00000110
a destra di una posizione (<=>) ripristinerà il nostro originale 6:
10000000 00000000 00000000 01100000
Quindi vediamo che spostarsi a destra equivale alla divisione per poteri di 2.
I bit persi sono andati
Tuttavia, uno spostamento non può recuperare " perso " bit. Ad esempio, se spostiamo questo modello:
00001000 00000000 00000000 00000110
alle 4 posizioni a sinistra (<=>), otteniamo 2.147.483.744:
11111000 00000000 00000000 00000110
e poi tornando indietro (<=>) otteniamo 134.217.734:
<*>Non possiamo ripristinare il valore originale una volta che abbiamo perso i bit.
Spostamento a destra aritmetico (> >)
Lo spostamento verso destra aritmetico è esattamente come lo spostamento verso destra logico, tranne che per il padding con zero, esegue il pad con il bit più significativo. Questo perché il bit più significativo è il segno o il bit che distingue i numeri positivi e negativi. Riempiendo con il bit più significativo, lo spostamento aritmetico destro preserva i segni.
Ad esempio, se interpretiamo questo modello di bit come un numero negativo:
<*>abbiamo il numero -2.147.483.552. Spostando questo a 4 posizioni giuste con lo spostamento aritmetico (-2.147.483.552 & Gt; & Gt; 4) ci darebbe:
<*>o il numero -134.217.722.
Quindi vediamo che abbiamo preservato il segno dei nostri numeri negativi usando lo spostamento destro aritmetico, piuttosto che lo spostamento destro logico. E ancora una volta, vediamo che stiamo eseguendo la divisione per poteri di 2.
Altri suggerimenti
Diciamo che abbiamo un solo byte:
0110110
L'applicazione di un singolo bit shift sinistro ci rende:
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 ribaltano; vengono scartati. Ciò significa che se hai lasciato il turno 1101100 e poi spostato a destra, non otterrai lo stesso risultato indietro.
Lo spostamento a sinistra di N equivale alla moltiplicazione di 2 N .
Lo spostamento a destra di N è (se si utilizza complemento di uno ) è equivalente di divisione per 2 N e arrotondamento a zero.
Il Bitshifting può essere utilizzato per una moltiplicazione e una divisione follemente veloci, a condizione che tu stia lavorando con una potenza di 2. Quasi tutte le routine grafiche di basso livello usano il bitshifting.
Ad esempio, ai vecchi tempi, abbiamo usato la modalità 13h (320x200 256 colori) per i giochi. In modalità 13h, la memoria video è stata disposta in sequenza per pixel. Ciò significava calcolare la posizione di un pixel, si userebbe la seguente matematica:
memoryOffset = (row * 320) + column
Ora, a quei tempi, la velocità era fondamentale, quindi avremmo usato i bitshift per fare questa operazione.
Tuttavia, 320 non è un potere di due, quindi per ovviare a questo dobbiamo scoprire qual è un potere di due che sommato fa 320:
(row * 320) = (row * 256) + (row * 64)
Ora possiamo convertirlo in turni a 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 per un'operazione di moltiplicazione costosa, usiamo i due bit-shift ... in x86 sarebbe qualcosa del genere (nota, è stato per sempre da quando ho fatto il montaggio (editor nota: 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ì, lavoreremo sodo per radere via 16 cicli della CPU.
In modalità 32 o 64 bit, entrambe le versioni diventano molto più brevi e veloci. Moderne CPU di esecuzione fuori servizio come Intel Skylake (vedi http://agner.org/optimize/ ) hanno una moltiplicazione hardware molto rapida (bassa latenza e throughput elevato), quindi il guadagno è molto più piccolo. La famiglia di bulldozer AMD è un po 'più lenta, specialmente per la moltiplicazione a 64 bit. Nelle CPU Intel e AMD Ryzen, due turni hanno una latenza leggermente inferiore ma più istruzioni di una moltiplicazione (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 te: guarda come gcc, clang e MSVC usano tutti shift + lea durante l'ottimizzazione return 320*row + col; .
La cosa più interessante da notare qui è che x86 ha comeistruzione hift-and-add (LEA) che può fare piccoli spostamenti a sinistra e aggiungere allo stesso tempo, con le prestazioni come e add istruzioni. ARM è ancora più potente: un operando di qualsiasi istruzione può essere spostato a destra oa sinistra gratuitamente. Quindi il ridimensionamento in base a una costante di tempo di compilazione nota per essere una potenza di 2 può essere persino più efficiente di un moltiplicare.
OK, ai giorni nostri ... qualcosa di più utile ora sarebbe usare lo spostamento dei bit per memorizzare due valori a 8 bit in un numero intero a 16 bit. Ad esempio, in C #:
// Byte1: 11110000
// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;
In C ++, i compilatori dovrebbero farlo per te se hai usato un struct con due membri a 8 bit, ma in pratica non sempre.
Le operazioni bit a bit, incluso il bit shift, sono fondamentali per l'hardware di basso livello o per la programmazione integrata. Se leggi una specifica per un dispositivo o anche alcuni formati di file binari, vedrai byte, parole e parole, suddivisi in campi di bit non allineati a byte, che contengono vari valori di interesse. L'accesso a questi campi di bit per la lettura / scrittura è l'uso più comune.
Un semplice esempio reale nella programmazione grafica è che un pixel a 16 bit è rappresentato come segue:
bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| Blue | Green | Red |
Per ottenere il valore verde devi fare questo:
#define GREEN_MASK 0x7E0
#define GREEN_OFFSET 5
// Read green
uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;
Spiegazione
Per ottenere il valore di SOLO verde, che inizia con l'offset 5 e termina con 10 (cioè lungo 6 bit), è necessario utilizzare una maschera (bit), che quando viene applicata sull'intero pixel a 16 bit , produrrà solo i bit a cui siamo interessati.
#define GREEN_MASK 0x7E0
La maschera appropriata è 0x7E0 che in binario è 0000011111100000 (ovvero 2016 in decimale).
uint16_t green = (pixel & GREEN_MASK) ...;
Per applicare una maschera, si utilizza l'operatore AND (& amp;).
uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;
Dopo aver applicato la maschera, ti ritroverai con un numero a 16 bit che in realtà è solo un numero a 11 bit poiché il suo MSB è nell'11 ° bit. Il verde in realtà è lungo solo 6 bit, quindi dobbiamo ridimensionarlo usando uno spostamento a destra (11 - 6 = 5), quindi l'uso di 5 come offset (#define GREEN_OFFSET 5).
Inoltre è comune usare i bit shift per una rapida moltiplicazione e divisione per potenze di 2:
i <<= x; // i *= 2^x;
i >>= y; // i /= 2^y;
Bit Masking &; Spostando
Lo spostamento dei bit viene spesso utilizzato nella programmazione grafica di basso livello. Ad esempio un determinato valore di colore dei pixel codificato in una parola a 32 bit.
Pixel-Color Value in Hex: B9B9B900
Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000
Per una migliore comprensione, lo stesso valore binario etichettato con quali sezioni rappresenta la parte di colore.
Red Green Blue Alpha
Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000
Diciamo ad esempio che vogliamo ottenere il valore verde di questo colore di pixel. Possiamo facilmente ottenere quel valore mascherando e spostando .
La nostra maschera:
Red Green Blue Alpha
color : 10111001 10111001 10111001 00000000
green_mask : 00000000 11111111 00000000 00000000
masked_color = color & green_mask
masked_color: 00000000 10111001 00000000 00000000
L'operatore & logico garantisce che vengano conservati solo i valori in cui la maschera è 1. L'ultima cosa che ora dobbiamo fare è ottenere il valore intero corretto spostando tutti quei bit a destra di 16 posizioni (spostamento logico a destra) .
green_value = masked_color >>> 16
Et voil & # 225 ;, abbiamo il numero intero che rappresenta la quantità di verde nel colore dei pixel:
Pixels-Green Value in Hex: 000000B9
Pixels-Green Value in Binary: 00000000 00000000 00000000 10111001
Pixels-Green Value in Decimal: 185
Questo è spesso usato per codificare o decodificare formati di immagine come jpg, png, ....
Un problema è che ciò che segue dipende dall'implementazione (secondo lo standard ANSI):
char x = -1;
x >> 1;
x ora può essere 127 (01111111) o ancora -1 (11111111).
In pratica, di solito è quest'ultimo.
Sto solo scrivendo suggerimenti e trucchi, potrebbe essere utile in test / esami.
-
n = n*2:n = n<<1 -
n = n/2:n = n>>1 - Verifica se n ha una potenza di 2 (1,2,4,8, ...): controlla
!(n & (n-1)) - Ottenere x th bit di
n:n |= (1 << x) - Verifica se x è pari o dispari:
x&1 == 0(pari) - Attiva il n th bit di x:
x ^ (1<<n)
Si noti che nell'implementazione Java, il numero di bit da spostare è modificato dalla dimensione della sorgente.
Ad esempio:
(long) 4 >> 65
è uguale a 2. Potresti aspettarti che spostare i bit a destra di 65 volte azzererebbe tutto, ma in realtà è l'equivalente di:
(long) 4 >> (65 % 64)
Questo è vero per < < ;, > > ;, e > > > ;. Non l'ho provato in altre lingue.
Alcune operazioni / manipolazioni di bit utili in Python. Implementato @Ravi Prakash risponde in python.
# basic bit operations
# int to bin
print(bin(10))
# bin to int
print(int('1010',2))
# multiplying x with 2 .... x**2== x << 1
print(200<<1)
# dividing x with 2 .... x /2 == x >> 1
print(200>>1)
# modulo x with 2 .... x%2 == x&1
if 20&1==0:
print("20 is a even number")
# check if n is power of 2 : check !(n & (n-1))
print(not(33 &(33-1)))
# getting xth bit of n : (n>>x)&1
print((10>>2)&1) # bin of 10==1010 and 2nd bit is 0
# toggle nth bit of x : x^(1<<n)
# take bin(10)==1010 and toggling 2nd bit in bin(10) we get 1110 === bin(14)
print(10^(1<<2))
Tieni presente che sulla piattaforma Windows è disponibile solo la versione a 32 bit di PHP.
Quindi se ad esempio si sposta < < o > > più che di 31 bit, i risultati non sono prevedibili. Di solito viene restituito il numero originale anziché zero, e può essere un bug davvero complicato.
Ovviamente se usi la versione a 64 bit di PHP (unix), dovresti evitare lo spostamento di oltre 63 bit. Tuttavia, ad esempio, MySQL utilizza BIGINT a 64 bit, quindi non dovrebbero esserci problemi di compatibilità.
AGGIORNAMENTO: da PHP7 Windows, i build php sono finalmente in grado di utilizzare numeri interi a 64 bit: La dimensione di un numero intero dipende dalla piattaforma, sebbene un valore massimo di circa due miliardi sia il valore normale (ovvero 32 bit con segno). Le piattaforme a 64 bit di solito hanno un valore massimo di circa 9E18, tranne su Windows precedente a PHP 7, dove era sempre a 32 bit.
