Matrice de biți - Bit array

O matrice de biți (cunoscută și sub numele de hartă de biți , set de biți , șir de biți sau vector de biți ) este o structură de date a matricei care stochează în mod compact biți . Poate fi folosit pentru a implementa o structură simplă de date . O matrice de biți este eficientă în exploatarea paralelismului la nivel de biți din hardware pentru a efectua operațiuni rapid. O matrice de biți tipică stochează kw biți, unde w este numărul de biți din unitatea de stocare, cum ar fi un octet sau un cuvânt , iar k este un număr întreg negativ. Dacă w nu împarte numărul de biți de stocat, un spațiu este irosit din cauza fragmentării interne .

Definiție

O matrice de biți este o mapare de la un domeniu (aproape întotdeauna un interval de numere întregi) la valori din setul {0, 1}. Valorile pot fi interpretate ca întunecate / luminoase, absente / prezente, blocate / deblocate, valide / invalide, etc. Ideea este că există doar două valori posibile, deci pot fi stocate într-un singur bit. Ca și în cazul altor matrice, accesul la un singur bit poate fi gestionat prin aplicarea unui index matricei. Presupunând că dimensiunea (sau lungimea) acestuia este de n biți, matricea poate fi utilizată pentru a specifica un subset al domeniului (de exemplu, {0, 1, 2, ..., n −1}), unde un 1-bit indică prezența și un 0-bit absența unui număr în set. Această structură de date utilizează aproximativ n / w cuvinte de spațiu, unde w este numărul de biți din fiecare cuvânt mașină . Indiferent dacă bitul cel mai puțin semnificativ (al cuvântului) sau bitul cel mai semnificativ indică cel mai mic indice este în mare măsură irelevant, dar primul tinde să fie preferat (pe mașinile puțin endiene ).

Operațiuni de bază

Deși majoritatea mașinilor nu sunt capabile să adreseze biți individuali în memorie și nici nu au instrucțiuni de manipulare a biților individuali, fiecare bit dintr-un cuvânt poate fi selectat și manipulat folosind operații bitbit . În special:

  • SAU poate fi folosit pentru a seta un bit la unul: 11101010 SAU 00000100 = 11101110
  • ȘI poate fi folosit pentru a seta un bit la zero: 11101010 ȘI 11111101 = 11101000
  • ȘI împreună cu testarea zero pot fi utilizate pentru a determina dacă este setat un bit:
    11101010 ȘI 00000001 = 00000000 = 0
    11101010 ȘI 00000010 = 00000010 ≠ 0
  • XOR poate fi folosit pentru a inversa sau comuta puțin:
    11101010 XOR 00000100 = 11101110
    11101110 XOR 00000100 = 11101010
  • NOT poate fi folosit pentru a inversa toți biții.
    NU 10110010 = 01001101

Pentru a obține masca de biți necesară pentru aceste operații, putem folosi un operator de schimbare de biți pentru a deplasa numărul 1 la stânga cu numărul corespunzător de locuri, precum și negarea pe biți dacă este necesar.

Având în vedere două matrici de biți de aceeași dimensiune reprezentând seturi, putem calcula diferența lor de uniune , intersecție și set-teoretică folosind operații de bit simple n / w fiecare (2 n / w pentru diferență), precum și complementul oricăruia: 

for i from 0 to n/w-1
    complement_a[i] := not a[i]
    union[i]        := a[i] or b[i]
    intersection[i] := a[i] and b[i]
    difference[i]   := a[i] and (not b[i])

Dacă dorim să parcurgem biții unei matrice de biți, putem face acest lucru eficient folosind o buclă dublă cuibărită care parcurge fiecare cuvânt, unul câte unul. Sunt necesare doar accesuri de memorie n / w : 

for i from 0 to n/w-1
    index := 0    // if needed
    word := a[i]
    for b from 0 to w-1
        value := word and 1 ≠ 0
        word := word shift right 1
        // do something with value
        index := index + 1    // if needed

Ambele mostre de cod prezintă o localitate ideală de referință , care va primi ulterior o creștere mare a performanței dintr-o memorie cache de date. Dacă o linie cache este k cuvinte, vor apărea doar aproximativ n / wk cache.

Operațiuni mai complexe

La fel ca în cazul șirurilor de caractere , este simplu să definim lungimea , șirul , comparația lexicografică , concatenarea , operațiile inversate . Implementarea unora dintre aceste operațiuni este sensibilă la endianitate .

Populația / greutatea Hamming

Dacă dorim să găsim numărul de 1 biți dintr-o matrice de biți, numit uneori număr de populație sau greutate Hamming, există algoritmi eficienți fără ramuri care pot calcula numărul de biți dintr-un cuvânt folosind o serie de operații simple de biți. Pur și simplu rulăm un astfel de algoritm pe fiecare cuvânt și păstrăm un total de rulare. Numărarea zerourilor este similară. Consultați articolul Hamming Weight pentru exemple de implementare eficientă.

Inversia

Răsucirea verticală a unei imagini de un bit pe pixel sau a unor algoritmi FFT necesită răsucirea biților de cuvinte individuale (așa b31 b30 ... b0devine b0 ... b30 b31). Când această operațiune nu este disponibilă pe procesor, este încă posibil să procedați prin treceri succesive, în acest exemplu pe 32 de biți: 

exchange two 16-bit halfwords
exchange bytes by pairs (0xddccbbaa -> 0xccddaabb)
...
swap bits by pairs
swap bits (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1)

The last operation can be written ((x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)).

Găsiți primul

Găsi primul set sau să găsească mai întâi o identifică indicele de funcționare sau poziția 1-bit cu cel mai mic indice într - o matrice, și are suport pe scară largă de hardware (pentru tablouri nu mai mare decât un cuvânt) și algoritmi eficienți pentru calculul acesteia. Când o coadă de prioritate este stocată într-o matrice de biți, găsiți prima poate fi utilizată pentru a identifica elementul cu cea mai mare prioritate din coadă. Pentru a extinde o dimensiune de cuvânt, găsiți mai întâi unul până la matrice mai lungi, puteți găsi primul cuvânt diferit de zero și apoi puteți rula găsi primul pe acel cuvânt. Operațiunile aferente găsi primul zero , conta zero la început , conta pe cele mai importante , conta zerouri , conta trailing cele , și log bază 2 ( a se vedea găsi primul set ) poate fi , de asemenea , extins la o matrice de biți într - un mod simplu.

Comprimare

O matrice de biți este cea mai densă stocare pentru biți „aleatori”, adică în care fiecare bit este la fel de probabil să fie 0 sau 1 și fiecare este independent. Dar majoritatea datelor nu sunt aleatorii, deci poate fi posibil să le stocați mai compact. De exemplu, datele unei imagini tipice de fax nu sunt aleatorii și pot fi comprimate. Codificarea pe lungime de rulare este frecvent utilizată pentru a comprima aceste fluxuri lungi. Cu toate acestea, majoritatea formatelor de date comprimate nu sunt atât de ușor de accesat aleatoriu; de asemenea, prin comprimarea matricilor de biți prea agresivi, riscăm să pierdem beneficiile datorită paralelismului la nivel de biți ( vectorizare ). Astfel, în loc să comprimăm matrici de biți ca fluxuri de biți, am putea să le comprimăm ca fluxuri de octeți sau cuvinte (a se vedea indexul Bitmap (compresie) ).

Avantaje și dezavantaje

Matricile de biți, în ciuda simplității lor, au o serie de avantaje marcate față de alte structuri de date pentru aceleași probleme:

  • Sunt extrem de compacte; nicio altă structură de date nu poate stoca n bucăți de date independente în cuvinte n / w .
  • Acestea permit mici matrice de biți să fie stocate și manipulate în registrul setat pentru perioade lungi de timp, fără acces la memorie.
  • Datorită capacității lor de a exploata paralelismul la nivel de biți, de a limita accesul la memorie și de a utiliza la maximum memoria cache , deseori depășesc multe alte structuri de date pe seturi de date practice, chiar și cele care sunt mai eficiente asimptotic.

Cu toate acestea, matricile de biți nu sunt soluția la toate. În special:

  • Fără compresie, acestea sunt structuri de date pentru seturi risipitoare pentru seturi rare (cele cu puține elemente în comparație cu intervalul lor) atât în ​​timp cât și în spațiu. Pentru astfel de aplicații, ar trebui luate în considerare matricele de biți comprimate, matricele Judy , încercările sau chiar filtrele Bloom .
  • Accesarea elementelor individuale poate fi costisitoare și dificil de exprimat în unele limbi. Dacă accesul aleatoriu este mai comun decât secvențial și matricea este relativ mică, o matrice de octeți poate fi preferabilă pe o mașină cu adresare de octeți. Cu toate acestea, o matrice de cuvinte nu este probabil justificată din cauza spațiului uriaș și a memoriei cache suplimentare pe care o provoacă, cu excepția cazului în care mașina are doar adresare de cuvinte.

Aplicații

Datorită compactității lor, matricile de biți au o serie de aplicații în domenii în care spațiul sau eficiența sunt la un nivel superior. Cel mai frecvent, acestea sunt utilizate pentru a reprezenta un grup simplu de steaguri booleene sau o secvență ordonată de valori booleene.

Tablourile de biți sunt utilizate pentru cozile prioritare , unde bitul de la indexul k este setat dacă și numai dacă k se află în coadă; această structură de date este utilizată, de exemplu, de kernel-ul Linux și beneficiază puternic de o operațiune de găsire-primul-zero în hardware.

Tablourile de biți pot fi utilizate pentru alocarea paginilor de memorie , inodurilor , sectoarelor de discuri etc. În astfel de cazuri, poate fi folosit termenul bitmap . Cu toate acestea, acest termen este frecvent utilizat pentru a se referi la imagini raster , care pot utiliza mai mulți biți pe pixel .

O altă aplicație a matricilor de biți este filtrul Bloom , o structură probabilistică de date a seturilor care poate stoca seturi mari într-un spațiu mic în schimbul unei probabilități mici de eroare. De asemenea, este posibil să se construiască tabele hash probabiliste bazate pe matrici de biți care acceptă fie fals pozitivi, fie falși negativi.

Matricile de biți și operațiunile pe ele sunt, de asemenea, importante pentru construirea unor structuri de date succinte , care utilizează aproape de spațiul minim posibil. În acest context, operații , cum ar fi găsirea n - lea 1 bit sau numărarea numărului de biți 1 până la o anumită poziție devin importante.

Tablourile de biți sunt, de asemenea, o abstracție utilă pentru examinarea fluxurilor de date comprimate , care conțin adesea elemente care ocupă porțiuni de octeți sau nu sunt aliniate la octeți. De exemplu, reprezentarea de codificare Huffman comprimată a unui singur caracter de 8 biți poate avea o lungime cuprinsă între 1 și 255 biți.

În regăsirea informațiilor , matricile de biți reprezintă o reprezentare bună pentru listele de postare a termenilor foarte frecvenți. Dacă calculăm decalajele dintre valorile adiacente într-o listă de numere întregi strict crescătoare și le codificăm folosind codare unară , rezultatul este o matrice de biți cu 1 bit în poziția a n- a dacă și numai dacă n este în listă. Probabilitatea implicită a unui decalaj de n este 1/2 n . Acesta este și cazul special al codificării Golomb în care parametrul M este 1; acest parametru este selectat în mod normal numai când -log (2- p ) / log (1- p ) ≤ 1, sau aproximativ termenul apare în cel puțin 38% din documente.

Suport lingvistic

Limbaj de programare APL sprijină pe deplin matrice de biți de formă arbitrară și mărime ca un boolean datatype distinct de numere întregi. Toate implementările majore ( Dyalog APL, APL2, APL Next, NARS2000, Gnu APL etc.) împachetează biții dens în orice dimensiune este cuvântul mașină. Biții pot fi accesați individual prin notația obișnuită de indexare (A [3]), precum și prin toate funcțiile și operatorii primitivi obișnuiți, unde sunt adesea operați utilizând un algoritm special de caz, cum ar fi însumarea biților printr-o căutare de tabel a octeților .

Limbajul de programare C e câmpuri de biți , pseudo-obiecte găsite în structs cu o dimensiune egală cu unele număr de biți, sunt de fapt matrice de biți mici; sunt limitate prin faptul că nu pot cuprinde cuvinte. Deși oferă o sintaxă convenabilă, biții sunt totuși accesați utilizând operatori bytewise pe majoritatea mașinilor și pot fi definiți numai în mod static (cum ar fi matricile statice ale lui C, dimensiunile lor sunt fixate în timpul compilării). Este, de asemenea, un idiom obișnuit pentru programatorii C să folosească cuvintele ca matrice de biți mici și să acceseze biți din aceștia folosind operatori de biți. Un fișier antet disponibil pe scară largă, inclus în sistemul X11 , xtrapbits.h, este „un mod portabil pentru sisteme de a defini manipularea câmpului de biți a matricilor de biți”. O descriere mai explicativă a abordării menționate mai sus poate fi găsită în comp.lang.c faq .

În C ++ , deși indivizii boolocupă de obicei același spațiu ca un octet sau un număr întreg, tipul STLvector<bool> este o specializare șablon parțială în care biții sunt împachetați ca o optimizare a eficienței spațiului. Deoarece octeții (și nu biții) sunt cea mai mică unitate adresabilă din C ++, operatorul [] nu returnează o referință la un element, ci în schimb returnează o referință proxy . Acest lucru ar putea părea un punct minor, dar înseamnă că acesta nuvector<bool> este un container STL standard, motiv pentru care utilizarea este, în general, descurajată. O altă clasă STL unică , creează un vector de biți fixați la o anumită dimensiune în timpul compilării, iar în interfața și sintaxa sa seamănă mai mult cu utilizarea idiomatică a cuvintelor ca seturi de biți de către programatorii C. De asemenea, are o anumită putere suplimentară, cum ar fi capacitatea de a conta eficient numărul de biți care sunt setați. Bibliotecile Boost C ++ oferă o clasă a cărei dimensiune este specificată în timpul rulării. vector<bool>bitsetdynamic_bitset

Limbajul de programare D oferă matrice de biți în biblioteca standard, Phobos, în std.bitmanip. La fel ca în C ++, operatorul [] nu returnează o referință, deoarece biții individuali nu sunt direct adresați pe majoritatea hardware-ului, ci în schimb returnează un bool.

În Java , clasa BitSetcreează o matrice de biți care este apoi manipulată cu funcții numite după operatorii bit-bit familiari programatorilor C. Spre deosebire de cel bitsetdin C ++, Java BitSetnu are o stare de "dimensiune" (are o dimensiune efectiv infinită, inițializată cu 0 biți); un bit poate fi setat sau testat la orice index. În plus, există o clasă EnumSet, care reprezintă un set de valori de tip enumerat intern ca vector de biți, ca o alternativă mai sigură la câmpurile de biți.

.NET Framework furnizează o BitArrayclasă de colectare. Stochează biți folosind o matrice de tip int(fiecare element din matrice reprezintă de obicei 32 de biți). Clasa acceptă operatori cu acces aleator și bit-bit, poate fi repetată și Lengthproprietatea sa poate fi modificată pentru a o dezvolta sau a o tăia.

Deși Standard ML nu are suport pentru matricele de biți, Standard ML din New Jersey are o extensie, BitArraystructura, în biblioteca sa SML / NJ. Nu are dimensiuni fixe și acceptă operații de set și operații de biți, inclusiv, neobișnuit, operații de schimbare.

Haskell, de asemenea, în prezent nu are suport standard pentru operațiile bit-bit, dar atât GHC, cât și Hugs oferă un Data.Bitsmodul cu funcții și operatori bit-bit asortate, inclusiv operații de deplasare și rotire și o matrice „necăsuțată” peste valori booleene poate fi utilizată pentru a modela o matrice Bit, deși acest lucru nu are suport de la fostul modul.

În Perl , șirurile pot fi utilizate ca tablouri de biți expandabile. Acestea pot fi manipulate folosind operatorii obișnuiți pe biți ( ~ | & ^), iar biții individuali pot fi testați și setați utilizând funcția vec .

În Ruby , puteți accesa (dar nu setați) un număr întreg ( Fixnumsau Bignum) folosind operatorul de paranteză ( []), ca și cum ar fi o matrice de biți.

Apple Fundația Core biblioteca conține CFBitVector și CFMutableBitVector structuri.

PL / I acceptă tablouri de șiruri de biți de lungime arbitrară, care pot fi fie de lungime fixă, fie variabile. Elementele matricei pot fi aliniate - fiecare element începe pe un octet sau o limită de cuvânt - sau nealiniat - elementele se succed imediat, fără nicio umplutură.

PL / pgSQL și SQL-ul PostgreSQL suportă șiruri de biți ca tip nativ. Există două tipuri de biți SQL: și , unde este un număr întreg pozitiv. bit(n)bit varying(n)n

Limbajele de descriere hardware, cum ar fi VHDL , Verilog și SystemVerilog acceptă nativ vectori de biți, deoarece aceștia sunt utilizați pentru modelarea elementelor de stocare, cum ar fi flip-flop-urile , autobuzele hardware și semnalele hardware în general. În limbajele de verificare hardware, cum ar fi OpenVera , e și SystemVerilog , vectorii de biți sunt folosiți pentru a prelua valori din modelele hardware și pentru a reprezenta datele care sunt transferate către hardware în timpul simulărilor.

Common Lisp oferă o bit-vectorimplementare unidimensională ca un caz special al dispozitivului încorporat array, acționând într-o capacitate duală, ca o clasă și ca un tip de specificator. Fiind un derivat al matricei, se bazează pe make-arrayfuncția generală care urmează să fie configurată cu un tip de element de bit, care permite opțional vectorul de biți să fie desemnat ca redimensionabil dinamic. Cu bit-vectortoate acestea, extinderea nu este infinită. Există un simple-bit-vectortip mai restricționat , care exclude în mod explicit caracteristicile dinamice. Vectorii biți sunt reprezentați și pot fi construiți într-un mod mai concis de către macro-ul cititor . În plus față de funcțiile generale aplicabile tuturor matricilor, există operațiuni dedicate pentru vectorii de biți. Bits unice pot fi accesate și modificate folosind și funcțiile și un număr extins de operații logice este acceptată. #*bitsbitsbit

Vezi si

Referințe

linkuri externe