Ci sono dei buoni motivi per usare lo spostamento dei bit, ad eccezione della matematica veloce?

Question

Capisco le operazioni bit a bit e come potrebbero essere utili per scopi diversi, ad es. permessi. Tuttavia, non sembro capire a cosa servono gli operatori di cambio di bit. Capisco come funzionano, ma non riesco a pensare a scenari in cui potrei volerli usare a meno che non voglia fare una moltiplicazione o divisione molto rapida. Ci sono altri motivi per usare il bit-shifting?

Answer 1

Ci sono molte ragioni, ecco alcuni:

1. Diciamo rappresentate un immagine in bianco e nero come una sequenza di bit e si desidera impostare un singolo pixel in questa immagine generico. Ad esempio il tuo offset di byte può essere x >> 3 e il tuo offset di bit può essere x & 0x7 e puoi impostare quel bit per: byte = byte | (1 < < (x & 0x7));
2. Implementazione di algoritmi di compressione dati in cui si gestiscono sequenze di bit a lunghezza variabile, ad es. codifica di Huffman.
3. Stai interagendo con un determinato hardware, ad es. un dispositivo di comunicazione seriale ed è necessario leggere o impostare alcuni bit di controllo.

Per questi e altri motivi, la maggior parte dei processori ha istruzioni di spostamento e/o rotazione di bit e altre istruzioni logiche (e/o/xor/non).

Storicamente la moltiplicazione e la divisione erano significativamente più lente in quanto sono operazioni più complesse e alcune CPU non ne avevano affatto.

vedi anche qui: Have you ever had to use bit shifting in real projects?

Answer 2

Come si indica, uno spostamento a sinistra è la stessa cosa di una moltiplicazione per due. Almeno è quando parliamo di quantità non firmate. Il significato di "spostamento a sinistra" di una quantità firmata è ... dipendente dalla lingua.

Con i compilatori moderni, non c'è davvero alcuna differenza tra la scrittura "i = x * 2;" e "i = x < < 1;" Il compilatore genererà il codice più efficiente. Quindi, in questo senso, non c'è motivo di preferire lo spostamento oltre la moltiplicazione.

Alcuni algoritmi funzionano spostando una quantità lasciata da un bit e quindi impostando il bit basso su 0 o 1. Alcuni semplici algoritmi di compressione funzionano in questo modo. Ad esempio, se il valore accumulato è nella variabile xe il valore corrente (0 o 1) è in y, allora ha più senso scrivere "x = (x < 1) | y", piuttosto che "x = (x * 2) + y ". Entrambi fanno la stessa cosa, ma il primo è più notazionalmente corretto. Non devi pensare, "oh, giusto, moltiplicare per due è lo stesso di un turno di sinistra."

Inoltre, quando si parla di algoritmi che spostano bit, è più conveniente spostare a sinistra o a destra di un numero particolare di bit piuttosto che capire quale multiplo di 2 si desidera moltiplicare o dividere per.

Quindi, mentre in genere non vi è alcun vantaggio in termini di prestazioni per lo spostamento piuttosto che per la moltiplicazione - almeno non quando si lavora con linguaggi di alto livello - ci sono momenti in cui avere la possibilità di spostarsi rende più facilmente comprensibile ciò che si sta facendo.

Answer 3

Ci sono molti posti in cui le operazioni di scorrimento di bit vengono regolarmente utilizzati al di fuori del loro utilizzo in calcoli numerici. Ad esempio, Bitboard è una struttura di dati comunemente utilizzata nei giochi da tavolo per la rappresentazione delle schede.Alcuni dei più forti motori di scacchi utilizzano questa struttura dati principalmente per la velocità e la facilità di generazione e valutazione del movimento. Questi programmi utilizzano pesantemente le operazioni di bit e le operazioni di spostamento di bit sono utilizzate in molti contesti, come la ricerca di maschere di bit, la generazione di nuove mosse sulla lavagna, il calcolo del logaritmo molto rapidamente, ecc. Esistono anche calcoli numerici molto avanzati che possono essere fatto elegantemente con l'uso intelligente delle operazioni di bit. Dai un'occhiata a this site per gli attacchi di bit bit: molti di questi algoritmi usano gli operatori di turno. Le operazioni di cambio di bit vengono regolarmente utilizzate nella programmazione dei driver di periferica, nello sviluppo di codec, nella programmazione di sistemi embedded e così via.

Answer 4

Il cambio consente di accedere a bit specifici all'interno di una variabile. L'espressione (n >> p) & ((1 << m) - 1) recupera una porzione di m bit della variabile n con un offset di p bit da destra.

Ciò consente al programma di utilizzare numeri interi che non sono multipli di 8 bit, il che è utile per la compressione dei dati. Ad esempio, l'ho usato nei miei programmi Netflix Prize per comprimere i record (ID utente a 22 bit + ID film a 15 bit + data a 12 bit + valutazione a 3 bit) in un uint64_t (con 12 bit di riserva) .

Un caso speciale molto comune è il confezionamento di 8 variabili bool in ciascun byte. (Autorizzazioni file Unix, bitmap in bianco e nero, CPU flags registers, ecc.)

Inoltre, la manipolazione dei bit viene utilizzata in UTF-8, che è una codifica di caratteri molto popolare. I caratteri Unicode sono rappresentati distribuendo i loro bit su 1, 2, 3 o 4 byte.