A cosa servono gli operatori di bit? [chiuso]

19

I linguaggi di programmazione vengono spesso con vari operatori di bit (ad esempio spostamento a sinistra e a destra bit a bit, AND bit a bit, OR, XOR ...). Questi non si abituano molto, o almeno è stata la mia esperienza. Talvolta vengono utilizzati in sfide di programmazione o domande di interviste, oppure la soluzione li richiede, ad esempio:

  • Senza utilizzare alcun operatore di uguaglianza, crea una funzione che restituisce true quando due valori sono uguali
  • Senza utilizzare una terza variabile, scambia il valore di due variabili

Questi, di nuovo, probabilmente hanno pochi usi nel mondo reale . Immagino che dovrebbero essere più veloci perché manipolano direttamente la memoria a un livello basso.

Perché sono così trovati nella maggior parte dei linguaggi di programmazione? Qualche caso d'uso nel mondo reale?

    
posta Anto 05.04.2011 - 20:02
fonte

15 risposte

53

No, hanno molte applicazioni reali e sono operazioni fondamentali sui computer.

Sono usati per

  • Giocoliere di blocchi di byte che non si adattano ai tipi di dati dei linguaggi di programmazione
  • Commutazione della codifica avanti e indietro dal grande al piccolo endian.
  • Imballaggio di 4 bit di dati a 6 bit in 3 byte per alcune connessioni seriali o usb
  • Molti formati di immagine hanno quantità di bit diverse assegnate a ciascun canale di colore.
  • Tutto ciò che riguarda pin IO in applicazioni incorporate
  • La compressione dei dati, che spesso non ha dati adatti ai bei limiti di 8 bit. \
  • Algoritmi di hashing, CRC o altri controlli di integrità dei dati.
  • crittografia
  • Psuedorandom number generation
  • Raid 5 utilizza XOR bit a bit tra i volumi per calcolare la parità.
  • Tonnellate di più

In realtà, logicamente, tutte le operazioni su un computer si riducono infine a combinazioni di queste operazioni bit a basso livello, che si svolgono all'interno delle porte elettriche del processore.

    
risposta data 05.04.2011 - 20:06
fonte
13

Perché sono operazioni fondamentali.

Secondo la stessa linea di pensiero, potresti sostenere che addition ha pochi usi del mondo reale, dal momento che può essere completamente sostituito con sottrazione (e negazione) e moltiplicazione. Ma continuiamo ad aggiungere perché è un'operazione fondamentale.

E non pensare per un momento che solo perché non hai visto molto bisogno di operazioni bit a bit non significa che non vengano utilizzati molto spesso. In effetti, ho usato operazioni bit a bit in quasi tutte le lingue che ho usato per cose come il bit masking.

In cima alla mia testa, ho usato le operazioni bit a bit per l'elaborazione delle immagini, bitfield e flag, l'elaborazione del testo (ad esempio, tutti i caratteri di una particolare classe condividono spesso un pattern di bit comune), la codifica e la decodifica dei dati serializzati, la decodifica Opcode VM o CPU e così via. Senza le operazioni bit a bit, la maggior parte di queste attività richiederebbe operazioni molte volte più complesse per eseguire l'attività in modo meno affidabile o con una leggibilità inferiore.

Ad esempio:

// Given a 30-bit RGB color value as a 32-bit int
// A lot of image sensors spit out 10- or 12-bit data
// and some LVDS panels have a 10- or 12-bit format
b = (color & 0x000003ff);
g = (color & 0x000ffc00) >> 10;
r = (color & 0x3ff00000) >> 20;

// Going the other way:
color = ((r << 20) & 0x3ff00000) | ((g << 10) & 0x000ffc00) | (b & 0x000003ff);

Decodificare le istruzioni della CPU per CPU di tipo RISC (come quando si emula un'altra piattaforma) richiede l'estrazione di parti di un valore elevato come sopra. A volte, eseguire queste operazioni con moltiplicazione e divisione e modulo, ecc., Può essere fino a dieci volte più lento delle operazioni bitwise equivalenti.

    
risposta data 05.04.2011 - 20:14
fonte
12

Un tipico esempio è l'estrazione dei singoli colori da un valore RGB a 24 bit e viceversa.

MODIFICA: dal link

    value =  ((int)(frgbvalue[2]*255 + 0.5))    |
                (((int)(frgbvalue[1]*255 + 0.5)) << 8 )  |
                (((int)(frgbvalue[0]*255 + 0.5)) << 16 ) |
                (((int)(falpha*255 + 0.5)) << 24 );
    
risposta data 05.04.2011 - 20:06
fonte
6

Ecco un esempio del mondo reale che troverai in Quake 3, Quake 4. Doom III. Tutti quei giochi che hanno utilizzato il motore Q3 .

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}

(Per capire quel codice devi capire come sono memorizzati i numeri in virgola mobile, non posso assolutamente approfondire su quello)

In termini di utilizzo, a meno che non ci si trovi in campi che richiedono lo spostamento di bit come la rete o la grafica, è possibile che il loro scopo sia leggermente accademico. Ma comunque interessante (almeno per me).

    
risposta data 06.04.2011 - 00:56
fonte
4

Lo spostamento è più veloce di moltiplicare o dividere per una potenza di due. Ad esempio, un < < = 2 moltiplica a per 4. Al contrario, a > > = 2 divide a per quattro. È anche possibile eseguire il bit-bang dei dati su un dispositivo utilizzando gli operatori bit-wise. Ad esempio, possiamo inviare N flussi di dati seriali da una porta pin N usando le operazioni shift, xor e "e" all'interno di N loop. Tutto ciò che può essere realizzato in logica digitale può essere realizzato anche su software e viceversa.

    
risposta data 06.04.2011 - 01:40
fonte
3

Molto tempo fa, gli operatori di bit erano utili. Oggi lo sono meno. Oh, non sono del tutto inutili, ma è passato molto tempo da quando ne ho visto uno usato che dovrebbe essere stato usato.

Nel 1977 ero un programmatore di linguaggio assembly. Ero convinto che l'assemblatore fosse l'unica vera lingua. Ero certo che il linguaggio come Pascal fosse per i weenies accademici che non hanno mai dovuto fare qualcosa di real .

Poi ho letto "The C Programming Language" di Kernighan e Ritchie. Mi ha cambiato completamente la mente. La ragione? Aveva bit operatori! era un linguaggio assembly! Aveva solo una sintassi diversa.

In quei giorni non potevo concepire di scrivere codice senza ands, ors, turni e rotazioni. Al giorno d'oggi non li uso quasi mai.

Quindi, la risposta breve alla tua domanda è: "Niente". Ma non è abbastanza giusto. Quindi la risposta più lunga è: "Per lo più nulla".

    
risposta data 06.04.2011 - 06:08
fonte
2

crittografia

Suggerisco di dare un'occhiata a uno snippet molto piccolo dal algoritmo di crittografia DES :

temp = ((left >>> 1) ^ right) & 0x55555555; right ^= temp; left ^= (temp << 1);
temp = ((right >>> 8) ^ left) & 0x00ff00ff; left ^= temp; right ^= (temp << 8);
temp = ((right >>> 2) ^ left) & 0x33333333; left ^= temp; right ^= (temp << 2);
temp = ((left >>> 16) ^ right) & 0x0000ffff; right ^= temp; left ^= (temp << 16);
temp = ((left >>> 4) ^ right) & 0x0f0f0f0f; right ^= temp; left ^= (temp << 4);
    
risposta data 05.04.2011 - 20:11
fonte
2

Molte buone risposte, quindi non ripeterò tali usi.

Li uso parecchio nel codice gestito (C # / .Net), e non ha nulla a che fare con il risparmio di spazio, alte prestazioni o algoritmi di spostamento dei bit intelligenti. A volte alcune logiche si adattano perfettamente alla memorizzazione dei dati in questo modo. Li uso spesso quando ho un enum ma le istanze possono contemporaneamente assumere più valori da quell'enumerazione. Non posso pubblicare un esempio di codice dal lavoro, ma un rapido google per "Flags enum" ("Flags" è il modo C # di definire un enum da utilizzare in modo bit per bit) fornisce questo bell'esempio: link .

    
risposta data 05.04.2011 - 22:15
fonte
2

Esiste anche un calcolo parallelo a bit. Se i tuoi dati sono solo di 1 e 0, puoi comprimere 64 di essi in una parola lunga non firmata e ottenere operazioni parallele a 64 km. Le informazioni genetiche sono due bit (che rappresentano la codifica AGCT del DNA), e se puoi fare i vari calcoli in modo parallelo al bit, puoi fare molto di più che se non lo fai. Per non parlare della densità dei dati in memoria - se la memoria, o la capacità del disco o la larghezza di banda delle comunicazioni è limitata implica che la compressione / decompressione dovrebbe essere considerata. Anche i numeri interi a bassa precisione, che si presentano in aree come l'elaborazione delle immagini, possono trarre vantaggio dall'ingegnoso calcolo parallelo a bit. È un'arte tutta per sé.

    
risposta data 06.04.2011 - 00:11
fonte
1

Perché vengono trovati?

Probabilmente è perché corrispondono alle istruzioni di assemblaggio e talvolta sono utili solo per le cose in lingue di livello superiore. La stessa cosa vale per il temuto GOTO che corrisponde all'istruzione di assemblaggio JMP .

Quali sono i loro usi?

In realtà ci sono solo molti usi da nominare, quindi mi limiterò a dare un utilizzo recente, anche se molto localizzato. Lavoro molto con l'assembly 6502 e stavo lavorando su una piccola applicazione che converte gli indirizzi di memoria, i valori, i valori di confronto, ecc. In codici che possono essere usati per il dispositivo GameGenie (fondamentalmente una applicazione cheat per il NES). I codici sono creati con un po 'di manipolazione.

    
risposta data 05.04.2011 - 20:06
fonte
1

Molti programmatori in questi giorni sono usati per computer con memoria quasi infinita.

Ma alcuni usano ancora piccoli microcontrollori in cui ogni bit conta (quando si ha solo 1k o meno RAM per esempio), e gli operatori bit a bit permettono a un programmatore di usare quei bit uno alla volta invece di sprecare un po ' entità di astrazione di programmazione molto più ampia di quanto potrebbe essere necessaria per mantenere uno stato richiesto dall'algoritmo. L'IO su quei dispositivi può anche richiedere di essere letto o controllato su basi bit a bit.

Il "mondo reale" ha molto più di quei piccoli microcontrollori di server o PC.

Per i tipi di CS teorici puri, le macchine di Turing si basano su bit di stato.

    
risposta data 05.04.2011 - 21:55
fonte
1

Solo uno dei tanti possibili usi degli operatori bit a bit ...

Gli operatori bit a bit possono anche aiutare a rendere il tuo codice più leggibile. Considera la seguente dichiarazione di funzione ....

int  myFunc (bool, bool, bool, bool, bool, bool, bool, bool);

...

myFunc (false, true, false, false, false, true, true, false);

È molto facile dimenticare quale parametro booleano significa cosa scrivere e persino leggere il codice. È anche facile perdere traccia del conteggio. Tale routine può essere ripulita.

/* More descriptive names than MY_FLAGx would be better */
#define MY_FLAG1    0x0001
#define MY_FLAG2    0x0002
#define MY_FLAG3    0x0004
#define MY_FLAG4    0x0008
#define MY_FLAG5    0x0010
#define MY_FLAG6    0x0020
#define MY_FLAG7    0x0040
#define MY_FLAG8    0x0080

int  myFunc (unsigned myFlags);

...

myFunc (MY_FLAG2 | MY_FLAG6 | MY_FLAG7);

Con nomi di flag più descrittivi, diventa molto più leggibile.

    
risposta data 06.04.2011 - 14:51
fonte
1

Se sai qualcosa su Unicode , probabilmente conosci UTF-8. Utilizza un sacco di bit di test, turni e maschere per impacchettare il codice a 20 bit in 1 o 4 byte.

    
risposta data 07.04.2011 - 15:53
fonte
0

Non li uso spesso, ma a volte sono utili. Mi viene in mente Gestione Enum .

Esempio:

enum DrawBorder{None = 0, Left = 1, Top = 2, Right = 4, Bottom = 8}

DrawBorder drawBorder = DrawBorder.Left | DrawBorder.Right;//Draw right & left border
if(drawBorder & DrawBorder.Left == DrawBorder.Left)
  //Draw the left border
if(drawBorder & DrawBorder.Top == DrawBorder.Top)
  //Draw the top border
//...
    
risposta data 06.04.2011 - 17:21
fonte
0

Non sono sicuro che questo utilizzo sia stato ancora notato:

Vedo OR parecchio quando lavoro con il codice sorgente illumos (openSolaris) per ridurre più valori di ritorno a 0 o 1, ad es.

int ret = 0;
ret |= some_function(arg, &arg2); // returns 0 or 1
ret |= some_other_function(arg, &arg2); // returns 0 or 1
return ret;
    
risposta data 04.09.2012 - 17:59
fonte

Leggi altre domande sui tag