operators - xoring - shift a bit in c




Che cosa sono gli operatori bitwise shift(bit-shift) e come funzionano? (6)

Ho cercato di imparare C nel mio tempo libero, e altri linguaggi (C #, Java, ecc.) Hanno lo stesso concetto (e spesso gli stessi operatori) ...

Quello che mi chiedo è, a livello centrale, che cosa fa il bit-shifting (<<, >>, >>>), quali problemi può aiutare a risolvere e quali trucchi si nascondono dietro la curva? In altre parole, la guida di un principiante assoluto per spostare il bit in tutta la sua bontà.


Bit Masking & Shifting

Il cambio di bit viene spesso utilizzato nella programmazione grafica di basso livello. Ad esempio un dato valore di colore del 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 quale parte del colore.

                                 Red     Green     Blue       Alpha
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

Diciamo per 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 & assicura che vengano mantenuti solo i valori in cui la maschera è 1. L'ultima cosa che dobbiamo fare ora è ottenere il valore intero corretto spostando tutti quei bit verso destra di 16 posizioni (spostamento verso destra logico) .

 green_value = masked_color >>> 16

Et voilá, 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 , ...


Diciamo che abbiamo un singolo byte:

0110110

L'applicazione di un singolo bitshift sinistro ci consente di:

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 spostano; sono scartati. Ciò significa che se hai lasciato lo shift 1101100 e poi lo hai spostato a destra, non otterrai lo stesso risultato.

Lo spostamento a sinistra di N equivale a moltiplicare per 2 N.

Spostarsi a destra di N è (se si utilizza il complemento di quelli ) equivale a dividere per 2 N e arrotondare a zero.

Bitshifting può essere utilizzato per moltiplicazioni e divisioni incredibilmente veloci, a patto che tu stia lavorando con una potenza di 2. Quasi tutte le routine grafiche di basso livello utilizzano il cambio di bit.

Ad esempio, nel passato, usavamo la modalità 13h (320x200 256 colori) per i giochi. Nella modalità 13h, la memoria video è stata strutturata in sequenza per pixel. Ciò significava calcolare la posizione di un pixel, si dovrebbe usare la seguente matematica:

memoryOffset = (row * 320) + column

Ora, a quei tempi, la velocità era critica, quindi usavamo i bitshift per fare questa operazione.

Tuttavia, 320 non è una potenza di due, quindi per aggirare questo dobbiamo scoprire qual è la potenza di due che sommati insieme rende 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, eccetto che per una costosa operazione di moltiplicazione, usiamo i due bitshift ... in x86 sarebbe qualcosa del genere (nota, è sempre stato da quando ho fatto il montaggio (ndr: corretti 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 CPU antica.

Sì, lavoreremmo così duramente per eliminare 16 cicli di CPU.

In modalità 32 o 64 bit, entrambe le versioni diventano molto più brevi e veloci. Moderne CPU di esecuzione out-of-order come Intel Skylake (vedi http://agner.org/optimize/ ) hanno un hardware molto veloce che si moltiplica (bassa latenza e throughput elevato), quindi il guadagno è molto più piccolo. La famiglia AMD Bulldozer è un po 'più lenta, specialmente per la moltiplicazione a 64 bit. Sulle CPU Intel e AMD Ryzen, due turni 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 te: vedi come gcc, clang e MSVC usano tutti shift + lea quando ottimizza il return 320*row + col; .

La cosa più interessante da notare qui è che x86 ha un'istruzione shift-and-add ( LEA ) che può fare piccoli turni 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 sinistra o a destra gratuitamente. Quindi scalare con una costante in tempo di compilazione che è noto per essere un power-of-2 può essere persino più efficiente di un multiplo.

OK, ai tempi moderni ... qualcosa di più utile ora sarebbe usare bitshifting per memorizzare due valori a 8 bit in un 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 fare questo per te se hai usato una struct con due membri a 8 bit, ma in pratica non sempre.


Gli operatori di bit shifting fanno esattamente ciò che il loro nome implica. 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 non firmato).
  • << è l'operatore di spostamento a sinistra e soddisfa le esigenze di entrambi i turni logici e aritmetici.

Tutti questi operatori possono essere applicati a valori interi ( int , long , eventualmente short e byte o char ). In alcune lingue, l'applicazione degli operatori di spostamento a qualsiasi tipo di dati più piccolo di int ridimensiona automaticamente l'operando in modo che sia int .

Nota che <<< non è un operatore, perché sarebbe ridondante. Si noti inoltre che C e C ++ non distinguono tra gli operatori di spostamento a destra. Forniscono solo l'operatore >> e il comportamento di spostamento a destra è definito dall'implementazione 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 int 32 bit potrebbe essere:

00000000 00000000 00000000 00000110

Spostando questo modello di bit a sinistra di una posizione ( 6 << 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. Si potrebbe anche notare che lo spostamento a sinistra equivale alla moltiplicazione per potenze di 2. Quindi 6 << 1 equivale a 6 * 2 , e 6 << 3 equivale a 6 * 8 . Un buon compilatore ottimizzante sostituirà le moltiplicazioni con i turni quando possibile.

Spostamento non circolare

Si prega di notare che questi non sono turni circolari. Spostando questo valore verso 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 "alla fine" è persa. Non si avvolge.

Spostamento logico a destra (>>>)

Uno spostamento logico di destra è l'inverso al turno di sinistra. Invece di spostare i bit a sinistra, si spostano semplicemente a destra. Ad esempio, spostando il numero 12:

00000000 00000000 00000000 00001100

a destra di una posizione ( 12 >>> 1 ) tornerà il nostro 6 originale:

00000000 00000000 00000000 00000110

Quindi vediamo che lo spostamento verso destra equivale alla divisione per potenze di 2.

I pezzi persi sono spariti

Tuttavia, uno spostamento non può recuperare i bit "persi". Ad esempio, se spostiamo questo modello:

00111000 00000000 00000000 00000110

a sinistra 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 persi i bit.

Aritmetico spostamento a destra (>>)

Lo spostamento aritmetico a destra è esattamente come lo spostamento logico di destra, tranne che al posto del padding con zero, esso si riempie del bit più significativo. Questo perché il bit più significativo è il bit del segno , o il bit che distingue i numeri positivi e negativi. Riempiendo con il bit più significativo, il giusto spostamento aritmetico è preservativo del segno.

Ad esempio, se interpretiamo questo modello di bit come numero negativo:

10000000 00000000 00000000 01100000

abbiamo il numero -2.147.483.552. Spostando questo a destra 4 posizioni con lo spostamento aritmetico (-2,147,483,552 >> 4) ci darebbe:

11111000 00000000 00000000 00000110

o il numero -134,217,722.

Quindi vediamo che abbiamo conservato il segno dei nostri numeri negativi usando il giusto spostamento aritmetico, piuttosto che il giusto spostamento logico. E ancora una volta, vediamo che stiamo eseguendo la divisione con i poteri di 2.


Le operazioni bit a bit, incluso lo spostamento dei bit, sono fondamentali per l'hardware di basso livello o per la programmazione incorporata. Se leggi una specifica per un dispositivo o anche alcuni formati di file binari, vedrai byte, parole e parole dimezzate, suddivise in bitfield non byte, che contengono vari valori di interesse. L'accesso a questi campi di bit per la lettura / scrittura è l'utilizzo 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 lo farebbe:

 #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 dall'offset 5 e termina a 10 (cioè a 6 bit di lunghezza), è necessario utilizzare una maschera (bit), che quando viene applicata sull'intero pixel a 16 bit, produrrà solo i pezzi a cui siamo interessati

#define GREEN_MASK  0x7E0

La maschera appropriata è 0x7E0 che in binario è 0000011111100000 (che è il 2016 in decimale).

uint16_t green = (pixel & GREEN_MASK) ...;

Per applicare una maschera, si utilizza l'operatore AND (&).

uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

Dopo aver applicato la maschera, ti ritroverai con un numero di 16 bit che in realtà è solo un numero di 11 bit dal momento che il suo MSB è all'11 ° bit. Il verde è in realtà solo lungo 6 bit, quindi abbiamo bisogno di ridimensionarlo usando uno spostamento verso destra (11 - 6 = 5), quindi l'uso di 5 come offset ( #define GREEN_OFFSET 5 ).

Anche comune è l'uso di shift di bit per moltiplicazione rapida e divisione per potenze di 2:

 i <<= x;  // i *= 2^x;
 i >>= y;  // i /= 2^y;

Sto scrivendo solo trucchi e suggerimenti, potrebbe essere utile nei test / esami.

  1. n = n*2 : n = n<<1
  2. n = n/2 : n = n>>1
  3. Verifica se n è potenza di 2 (1,2,4,8, ...): check !(n & (n-1))
  4. Ottenendo x bit di n : n |= (1 << x)
  5. Verifica se x è pari o dispari: x&1 == 0 (pari)
  6. Attiva / disattiva il bit n di x: x ^ (1<<n)

Un trucco è che quanto 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.







binary-operators