Quanto può essere utile un programmatore a tutto tondo con operazioni bit-wise? [chiuso]

33

Ho consultato recentemente alcuni codici OpenJDK e ho trovato alcuni intriganti pezzi di codice che hanno a che fare con operazioni bit-saggio . Ho persino chiesto una domanda su di esso su StackOverflow.

Un altro esempio che illustra il punto:

 1141       public static int bitCount(int i) {
 1142           // HD, Figure 5-2
 1143           i = i - ((i >>> 1) & 0x55555555);
 1144           i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
 1145           i = (i + (i >>> 4)) & 0x0f0f0f0f;
 1146           i = i + (i >>> 8);
 1147           i = i + (i >>> 16);
 1148           return i & 0x3f;
 1149       }

Questo codice può essere trovato nella classe Integer .

Non posso fare a meno di sentirmi stupido quando guardo questo. Mi sono perso una o due lezioni al college o non è qualcosa che dovrei solo ottenere ? Posso fare semplici operazioni bit-like (come ANDing, ORing, XORing, shifting), ma dai, come fa qualcuno a inventarsi un codice come quello sopra?

Quanto deve essere valido un programmatore a tutto tondo con operazioni bit-like?

Nota a margine ... Ciò che mi preoccupa è che la persona che ha risposto alla mia domanda su StackOverflow ha risposto in pochi minuti. Se fosse riuscito a farlo, perché ho semplicemente guardato i cervi nei fari?

    
posta c_maker 28.10.2011 - 12:08
fonte

13 risposte

38

Direi che come sviluppatore a tutto tondo, è necessario comprendere gli operatori e le operazioni bit a bit.

Quindi, come minimo, dovresti essere in grado di capire il codice sopra dopo un po 'di riflessione.

Le operazioni bit a bit tendono ad essere piuttosto di basso livello, quindi se lavori su siti web e software LOB, è improbabile che tu le usi molto.

Come altre cose, se non le usi molto, non ne parleresti.

Quindi non dovresti preoccuparti che qualcuno sia in grado di capirlo molto velocemente, dato che (probabilmente) lavorano molto con questo tipo di codice. Possibilmente scrivendo codice OS, codice del driver o altra manipolazione complicata del bit.

    
risposta data 28.10.2011 - 12:58
fonte
36

Se capisci come risolvere problemi come "determinare se i bit 3 e 8 sono impostati," "clear bit 5" o "trovare il valore intero rappresentato dai bit 7-12" hai abbastanza comprensione degli operatori bit a bit seleziona la casella Can Twiddle Bits nell'elenco di controllo "a tutto tondo"

Ciò che è nel tuo esempio viene da Hacker's Delight , una raccolta di algoritmi ad alte prestazioni per manipolare piccoli bit di dati come numeri interi. Chiunque abbia scritto quel codice originariamente non l'ha sputato in cinque minuti; la storia dietro di esso è più probabile che ci fosse bisogno di un modo veloce e privo di branchie per contare i bit e l'autore ha avuto un po 'di tempo da dedicare a fissare le stringhe di bit e preparare un modo per risolvere il problema. Nessuno capirà come funziona a prima vista a meno che non l'abbia visto prima. Con una solida conoscenza delle basi bit a bit e un po 'di tempo trascorso a sperimentare il codice, potresti probabilmente capire come fa ciò che fa.

Anche se non capisci questi algoritmi, solo sapere che esistono aggiunge alla tua "arrotondatezza" perché quando arriva il momento di affrontare, ad esempio, il conteggio delle bit ad alte prestazioni, sai cosa studiare. Nel mondo pre-Google, era molto più difficile scoprire queste cose; ora è a portata di mano.

L'utente che ha risposto alla tua domanda SO potrebbe aver già visto il problema o ha studiato l'hashing. Scrivilo e chiedi.

    
risposta data 28.10.2011 - 13:58
fonte
8

Dal tuo esempio ci sono alcune cose che dovresti assolutamente conoscere senza pensare veramente.

1143 i = i - ((i > > 1) & 0x55555555);

Dovresti riconoscere il pattern di bit 0x555 ... come un pattern a bit alternato 0101 0101 0101 e che gli operatori lo stanno sfalsando di 1 bit (a destra), e che & è un'operazione di mascheramento (e cosa significa mascheramento).

1144 i = (i & 0x33333333) + ((i > > 2) & 0x33333333);

Di nuovo un pattern, questo è 0011 0011 0011. Anche questa volta sta cambiando due e mascherando di nuovo. lo spostamento e il mascheramento seguono uno schema che dovresti riconoscere ...

1145 i = (i + (i > > > 4)) & 0x0f0f0f0f;

il modello si solidifica. Questa volta è 00001111 00001111 e, naturalmente, questa volta la stiamo spostando 4. ogni volta che cambiamo la dimensione della maschera.

1148 return i & 0x3f;

un altro pattern di bit, 3f è un blocco di zeri seguito da un blocco più grande di quelli.

Tutte queste cose dovrebbero essere ovvie a colpo d'occhio se sei "Ben arrotondato". Anche se non penserai mai che lo userai, ti mancheranno probabilmente alcune opportunità per semplificare enormemente il tuo codice se non lo sai.

Anche in un linguaggio di livello superiore, i pattern di bit vengono utilizzati per memorizzare MOLTE quantità maggiori di dati in campi più piccoli. Questo è il motivo per cui vedi sempre i limiti di 127/8, 63/4 e 255/6 nei giochi, è perché devi memorizzare così tante di queste cose che senza riempire i campi sarai costretto a usare fino a dieci volte il quantità di memoria. (Bene, l'ultimo sarebbe se tu avessi bisogno di memorizzare un gran numero di booleani in un array, potresti risparmiare 32-64 volte la quantità di memoria che useresti se non ci pensassi - la maggior parte delle lingue implementa i booleani come una parola che spesso sarà di 32 bit. Quelli che non si sentono a proprio agio a questo livello non resisteranno alle opportunità di archiviare dati come questo semplicemente perché hanno paura dell'ignoto.

Fuggiranno anche da cose come l'analisi manuale dei pacchetti recapitati sulla rete in un formato compresso - qualcosa che è banale se non si ha paura. Questo potrebbe richiedere un gioco che richiede un pacchetto da 1k fino a 200 byte, il pacchetto più piccolo scorrerà attraverso la rete in modo più efficiente e ridurrà la latenza e consentirà una maggiore velocità di interazione (che potrebbe abilitare intere nuove modalità di gioco per un gioco).

    
risposta data 28.10.2011 - 18:17
fonte
5

Mi è capitato di riconoscere il codice perché l'ho visto prima nel software per manipolare i frame video. Se lavorassi regolarmente con elementi come CODEC audio e video, protocolli di rete o registri di chip, vedresti molte operazioni bit a bit e diventerebbe una tua seconda natura.

Non dovresti sentirti male se il tuo lavoro non coincide molto spesso con quei domini. Conosco bene le operazioni a bit, ma rallento molto nelle rare occasioni in cui ho bisogno di scrivere una GUI, a causa di tutte le stranezze con i layout, la ponderazione e l'espansione e di cui sono certo una seconda natura per gli altri. I tuoi punti di forza sono ovunque tu abbia più esperienza.

    
risposta data 28.10.2011 - 15:24
fonte
4

le cose principali di cui dovresti essere a conoscenza è come vengono rappresentati gli interi (in generale un bitvector a lunghezza fissa in cui la lunghezza dipende dalla piattaforma) e quali operazioni sono disponibili su di essi

le operazioni aritmetiche principali + - * / % possono essere capite senza bisogno di capirle anche se può essere utile per le micro-ottimizzazioni (sebbene la maggior parte delle volte il compilatore sarà in grado di occuparsene per te)

il set di manipolazione di bit | & ~ ^ << >> >>> richiede almeno una comprensione passante per poterli utilizzare

tuttavia la maggior parte delle volte li userai solo per passare i flag di bit a un metodo come OR ing insieme e passare un int e poi AND out le impostazioni è più leggibile che passare più (fino a 32 ) booleani in un lungo elenco di parametri e consente di modificare i possibili flag senza cambiare l'interfaccia

per non parlare dei booleani sono generalmente tenuti separatamente in byte o intro invece di comprimerli insieme come fanno le bandiere

come per lo snippet di codice esegue un conteggio parallelo dei bit che consente all'algoritmo di funzionare in O(log(n)) dove n è il numero di bit invece del ciclo naive che è O(n)

il primo passo è il più difficile da capire, ma se inizi dal setup devi sostituire le sequenze di bit 0b00 in 0b00 , 0b01 in 0b01 , 0b10 in 0b01 e 0b11 in 0b10 diventa più facile da seguire

così per il primo passo i - ((i >>> 1) & 0x55555555) se prendiamo i per essere uguale a 0b00_01_10_11 quindi l'output di questo dovrebbe essere 0b00_01_01_10

(nota che 0x5 è uguale a 0b0101 )

se prendiamo i = 0b00_01_10_11 questo significa che 0b00_01_01_10 - (0b00_00_11_01 & 0b01_01_01_01) è 0b00_01_10_11 - 0b00_00_01_01 che a sua volta diventa 0b00_01_01_10

avrebbero potuto fare (i & 0x55555555) + ((i >>> 1) & 0x55555555) per lo stesso risultato, ma questa è un'altra operazione

i seguenti passaggi sono in un vena simile

    
risposta data 28.10.2011 - 13:11
fonte
3

Tutti dovrebbero capire le operazioni di base bit-wise. È la composizione delle operazioni di base per eseguire le attività in un modo ottimizzato e robusto che richiede molta pratica.

Coloro che lavorano quotidianamente con la manipolazione dei bit (come persone incorporate), ovviamente, svilupperanno una strong intuizione e un bel bagaglio di trucchi.

Quanta abilità dovrebbe avere un programmatore che non fa cose di basso livello con manipolazione bit-wise? Basta essere in grado di sedersi con una stanza come quella che hai incollato e lavorarci lentamente come se fosse un rompicapo o un rompicapo.

Per lo stesso motivo, direi che un programmatore incorporato dovrebbe capire tanto su http come uno sviluppatore web capisce la manipolazione bit-wise. In altre parole, è "OK" non essere maghi con la manipolazione di bit se non lo si usa sempre.

    
risposta data 28.10.2011 - 15:31
fonte
3

La gioia di Hacker è un'opera derivata. L'antenato di tutti è HakMem del 1972. link

L'importante è sapere che l'algoritmo ovvio per qualsiasi attività non è necessariamente il migliore. Ci sono molti casi in cui la conoscenza dell'esistenza di una soluzione elegante a un problema partucolare è ciò che è importante.

    
risposta data 28.10.2011 - 19:42
fonte
3

Quanto è difficile interpretare gli operatori bit a bit?

Programma programmi embedded. Ho praticato molto questa roba. La tua domanda collegata sulle mappe hash con il codice

static int hash(int h) {
   // This function ensures that hashCodes that differ only by
   // constant multiples at each bit position have a bounded
   // number of collisions (approximately 8 at default load factor).
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

mi è sembrato perfetto nel tempo necessario a dettare il codice ad alta voce. Gli eventi descritti in bitCount sono immediatamente chiari, ma ci vuole un minuto per capire perché conta effettivamente bit. I commenti sarebbero grandiosi, tuttavia, e renderebbero la comprensione di ciò che il codice fa solo leggermente più difficile del problema dell'hash.

È importante fare la distinzione tra leggere e capire il codice. Sono in grado di interpretare il codice bitCount e di leggere quello che fa, ma dimostrando il motivo per cui funziona o anche che funzioni potrebbe richiedere un minuto. C'è una differenza tra l'essere in grado di leggere il codice senza intoppi ed essere in grado di ingannare il motivo per cui il codice è così com'è. Alcuni algoritmi sono semplicemente difficili. Il cosa del codice hash aveva senso, ma il commento spiegava perché ciò che veniva fatto. Non scoraggiarti se una funzione che usa operatori bit a bit è difficile da capire, sono spesso usati per fare cose matematiche difficili che sarebbero difficili a prescindere dal formato.

Un'analogia

Sono abituato a questa roba. Un argomento a cui non sono abituato è regex. Mi occupo occasionalmente di script di compilazione, ma mai nel lavoro di sviluppo quotidiano.

So come usare i seguenti elementi di un'espressione regolare:

  • [] classi di caratteri
  • I caratteri * , . e +
  • Inizio della stringa ^ e fine della stringa $
  • Le classi di carattere \ d, \ w, \ s
  • Il flag / g

Questo è sufficiente per creare query semplici e molte delle query che vedo non si discostano molto da questo.

Qualunque cosa non sia in questa lista, cerco un foglio dei trucchi. Qualunque cosa, eccetto {} e () - Il cheat sheet non sarà sufficiente. So abbastanza di questi ragazzi per sapere che avrò bisogno di una lavagna, un manuale di riferimento e magari un collega. Puoi impacchettare alcuni algoritmi pazzi in poche righe brevi di espressioni regolari.

Per progettare un'espressione regolare che richiede o suggerisce qualcosa che non è nella mia lista di elementi conosciuti, ho intenzione di elencare tutte le classi di input che mi aspetto di riconoscere e metterli in una suite di test. Elaborerò l'espressione regolare lentamente e in modo incrementale, con un sacco di passaggi intermittenti, e commetterò questi passaggi al controllo del codice sorgente e / o li lascerò in un commento, così posso capire cosa sarebbe dovuto succedere più tardi quando si rompe. Se è in codice di produzione, farò in modo che venga esaminato da qualcuno con più esperienza.

È qui che ti trovi con operatori bit a bit?

Quindi vuoi essere ben arrotondato?

Secondo me, se sei in grado di interpretare il codice come questo tirando fuori un pezzo di carta o andando alla lavagna e eseguendo manualmente le operazioni, sei qualificato a tutto tondo. Per qualificarsi come un buon programmatore a tutto tondo nell'area delle operazioni bit a bit dovresti essere in grado di fare quattro cose:

  1. Essere in grado di leggere e scrivere operazioni comuni fluidamente
    Per un programmatore di applicazioni, le operazioni comuni con operatori bit a bit includono gli operatori di base di | e & per impostare e deselezionare i flag. Questo dovrebbe essere facile. Dovresti essere in grado di leggere e scrivere cose come

    open('file', O_WRONLY | O_APPEND | O_CREAT );
    // Use an OR operator ^ here and ^ here to set multiple flags
    

    senza rallentare (supponendo che tu sappia cosa significano i flag ).

  2. Essere in grado di leggere operazioni più complesse con un po 'di lavoro
    I bit di conteggio sono molto veloci nel tempo O (log (n)) senza rami, garantendo che il numero di collisioni in hashCode possa differire di una quantità limitata e analisi degli indirizzi email , numeri di telefono o HTML con una regex sono problemi difficili. È ragionevole per chiunque non sia un esperto in queste aree di raggiungere la lavagna, è irragionevole non poter iniziare a lavorare per capire.

  3. Essere in grado di scrivere alcuni algoritmi complessi con molto lavoro
    Se non sei un esperto, non dovresti aspettarti di essere in grado di fare cose complesse e difficili. Tuttavia, un buon programmatore dovrebbe essere in grado di farlo funzionare continuamente. Fallo abbastanza e sarai presto un esperto :)

risposta data 28.10.2011 - 19:56
fonte
2

Se andassi in un'università decente avresti dovuto prendere lezioni in Discrete Mathematics. Avresti imparato l'aritmetica binaria, l'ottale e l'esadecimale e le porte logiche.

Su questa nota è normale sentirsi confusi da questo, se vi è una qualsiasi consolazione dal momento che scrivo principalmente applicazioni web, raramente ho bisogno di guardare o scrivere un codice come questo, ma poiché capisco l'aritmetica binaria e il comportamento di gli operatori bit a bit posso finalmente capire cosa sta succedendo qui dato un tempo sufficiente.

    
risposta data 28.10.2011 - 13:12
fonte
2

Come programmatore di telefoni cellulari ho dovuto affrontare questo genere di cose. È ragionevolmente comune dove il dispositivo non ha molta memoria, o dove la velocità di trasmissione è importante. In entrambi i casi, cerchi di raccogliere quante più informazioni possibili in pochi byte.

Non ricordo di aver usato operatori bit a bit in 5 anni circa di PHP (forse sono solo io), non in 10 anni circa di programmazione Windows, sebbene alcune cose di Windows di livello inferiore facciano parte del pacchetto.

Dici "Non posso fare a meno di sentirmi stupido quando guardo questo". NON - sentirsi arrabbiato.

Hai appena incontrato l'output di un programmatore cowboy.

Non sa nulla della scrittura di codice gestibile? Spero sinceramente che sia lui a dover tornare su questo in un anno e provare a ricordare cosa significa.

Non so se hai tagliato commenti o se non ce ne sono stati, ma questo codice non ha superato la revisione del codice in cui ero responsabile del QA s / w (e sono stato un paio di volte).

Ecco una buona regola empirica - gli unici "interi nudi" ammessi nel codice sono 0 1nd 1. Tutti altri numeri dovrebbero essere #define, costi, enumerazioni, ecc., a seconda della lingua.

Se questi 3 e 0x33333333 hanno detto qualcosa come NUM_WIDGET_SHIFT_BITS e WIDGET_READ_MASK, il codice sarebbe stato più facile da leggere.

Vergogna a chi lo ha messo in un progetto open source, ma anche ai commenti sul codice personale e usa definizioni / enfasi significative e hai i tuoi standard di codifica.

    
risposta data 28.10.2011 - 16:54
fonte
1

Questo particolare pezzo di codice è tratto direttamente dal libro Delirio di hacker , figura 5.2. È online in C (la funzione pop) qui . Nota che l'autore ora consiglia di utilizzare le versioni aggiornate: link

Se vuoi imparare questo tipo di micro-ottimizzazioni suggerirei quel libro; è divertente, ma a meno che non si stia programmando bit a livello molto basso spesso non lo capirai; e la maggior parte delle volte il tuo compilatore sarà in grado di fare molti di questi tipi di ottimizzazioni per te.

Aiuta anche a riscrivere tutti i numeri esadecimali in binario per capire questi tipi di algoritmi e lavorarci sopra su un caso o su due.

    
risposta data 28.10.2011 - 18:18
fonte
1

Spiegazione per esempio. I dati sono sequenze di bit. Consente di contare i bit sul byte 01001101 con le seguenti operazioni disponibili: 1. Possiamo controllare il valore dell'ultimo bit. 2. Possiamo spostare la sequenza.

  1. 01001101 - > l'ultimo byte è 1, totale = 1. turni
  2. 10100110 - > l'ultimo byte è 0, totale = 1. turni
  3. 01010011 - > l'ultimo byte è 1, totale = 2. turni
  4. 10101001 - > l'ultimo byte è 1, totale = 3. turni
  5. 11010100 - > l'ultimo byte è 0, totale = 3. turni
  6. 01101010 - > l'ultimo byte è 0, totale = 3. turni
  7. 00110101 - > l'ultimo byte è 1, totale = 4. turni
  8. 10011010 - > l'ultimo byte è 0, totale = 4. turni

La nostra risposta: 4.

Non è stato difficile, vero? Il grosso problema con le operazioni bit a bit è che ci sono cose limitate che possiamo fare. Non possiamo accedere un po 'direttamente. Ma possiamo, ad esempio, conoscere il valore dell'ultimo bit confrontandolo con la MASK 00000001 e possiamo fare in modo che ogni bit sia l'ultimo con le operazioni di shift. Ovviamente, l'algoritmo risultante sembrerà spaventoso per chi non è abituato. Niente a che fare con l'intelligenza.

    
risposta data 28.10.2011 - 21:56
fonte
0

Non direi che ne hai bisogno a meno che il lavoro che stai facendo sia legato a:

  • Elaborazione audio
  • Elaborazione video
  • Grafica
  • Networking (in particolare dove la dimensione del pacchetto è importante)
  • Enorme quantità di dati

Anche l'archiviazione delle autorizzazioni nei flag di stile unix è un altro uso, se si dispone di un modello di autorizzazioni particolarmente complesso per il proprio sistema, o se si desidera veramente racchiudere tutto in un singolo byte, a scapito della leggibilità.

A parte queste aree, lo considererei un grande vantaggio se uno sviluppatore / sviluppatore senior potrebbe dimostrare lo spostamento di bit e utilizzare | & e ^ poiché mostra un interesse per la professione che potresti dire porta a un codice più stabile e affidabile.

Per quanto riguarda non "ottenere" il metodo a prima vista, come accennato hai bisogno di una spiegazione di ciò che sta facendo e un po 'di background. Non direi che è correlato all'intelligenza, ma quanto sei abile nel lavorare con esadecimale giorno per giorno e riconoscere i problemi che alcuni schemi possono risolvere.

    
risposta data 29.10.2011 - 12:19
fonte

Leggi altre domande sui tag