Bitski niz

Из Википедије, слободне енциклопедије

Bitski niz (eng. Bit array) je niz koji skladišti bitove. Može biti korišćen kao jednostavna struktura podataka. Bitski niz je veoma efikasan zato što se operacije nad bitovima izvršavaju brzo.

Definicija[уреди]

Bitski niz se koristi za obeležavanje nekih podataka vrednostima {0,1}. Vrednost bita može biti interpretirana na razne načine, na primer prisutan/odsutan, zakljucan/otkljucan, tacno/netacno, itd. Poenta je da postoje samo dve moguce vrednosti i samim tim se mogu smestiti u jedan bit.

Osnovne operacije[уреди]

Iako većina mašina nije u stanju da adresira pojedinačne bitove, niti imaju instrukcije za baratanje pojedinačnim bitovima, svakim bitom se može manipulisati korišćenjem bitskih operatora.

  • Bitovsko ILI (eng. OR) može biti korišćeno za postavljanje nekog bita na jedinicu : 11101010 OR 00000100 = 11101110
  • Bitovsko I (eng. AND) može biti korišćeno za postavljanje nekog bita na nulu: 11101010 AND 11111101 = 11101000
  • Sa bitskim operatorom I možemo proveriti da li bit na nekoj poziciji ima vrednost 1 ili 0:
11101010 AND 00000001 = 00000000 = 0
11101010 AND 00000010 = 00000010 ≠ 0
  • Ekskluzivno ILI (eng. XOR) može biti korišćeno za invertovanje nekog bita:
11101010 XOR 00000100 = 11101110
11101110 XOR 00000100 = 11101010
  • Bitska Negacija (eng. NOT) može biti korišćena za invertovanje svih bitova:
NOT 10110010 = 01001101

Kako bi se postigao željeni efekat nad bitovima datog broja, običaj je da se vrši njegovo kombinovanje bitovskim operatorima sa specijalno pripremljenim konstantama koje se obično nazivaju maske. Masku možemo pomerati Bitskim šiftovanjem u levu stranu ili u desnu stranu(>>, <<).

Za dva zadata bitska niza iste dužine , možemo odrediti njihovu uniju(eng. union),presek(eng. intersection) i razliku(eng. diference) koristeći n/w jednostavnih bitskih operacija (2n/w za razliku), kao i komplement(eng. complement) oba niza:

 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])

Ako želimo da prodjemo kroz niz bitova i da izvršimo neku obradu tog niza, to možemo da uradimo efikasno koristeći dvostruku ugnežđenu petlju. Samo n/w memorijskog prostora nam je potrebno:

 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


Prebrojavanje[уреди]

Ako želimo da nadjemo broj bitova koji imaju vrednost 1,koristimo algoritam prebrojavanje (eng. Hamming weight). Postoji dosta efikasnih algoritama, koji prebrojavaju bitove koristeći jednostavne bitske operacije.

Sortiranje[уреди]

Sortiranje bitskog niza se lako može uraditi u vremenskoj složenosti O(n). Prvo prebrojimo koliko ima jedinica i ako ih ima k , tih k jedinica stavimo na kraj niza, a ostatak niza popunimo nulama.

Inverzija[уреди]

Vertikalno okretanje slike koja zauzima jedan bit po pikselu ( eng. one-bit-per-pixel ), zahteva zamenu bitova pojedinih reči pa b31 b30 ... b0 postaje b0 ... b30 b31. Kada ova operacija nije dostupna na procesoru, i dalje je moguće da se ovo uradi sukcesivnim prolazom, na primer za 32 bita:

exchange two 16bit halfwords
exchange bytes by pairs (0xddccbbaa -> 0xccddaabb)
...
swap bits by pairs
swap bits (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1)
 
Poslednja operacija može biti zapisana na ovaj način :((x&0x55555555)<<1) | (x&0xaaaaaaaa)>>1)).

Pronaći prvu jedinicu[уреди]

Pronaći prvu jedinicu ( eng. find first set-FFS ) je operacija koja pronalazi indeks ili poziciju bita koji ima najmanju težinu u bitskoj reči ( eng. word ). Ova operacija ima široku hardversku podršku i efikasne algoritme za njeno izvršavanje. Kako bi ovaj algoritam radio i za duže bitske nizove, koji imaju više bitskih reči, možemo prvo pronaći prvu bitsku reč koja je različita od nule, i onda na tu reč primeniti FFS.

Kompresija[уреди]

Bitski niz je najgušće pakovanje za bitove, gde je svaki bit nezivisan i ima vrednost jedan ili nula.Većina podataka nije nezavisna(niz bitova koji čine taj podatak nisu nasumičnim redom poredjani), pa je moguće da se ti podaci kompaktnije sačuvaju. Na primer običnu sliku možemo kompresovati tako da zauzima manje memorije.Kodiranje(eng. Run-length encoding (RLE)[1] )je najčešće korišćeno za kompresovanje dugih nizova.Sa druge strane, ako kompresujemo bitove previše agresivno izlažemo se riziku da izgubimo kvalitet podatka koji kompresujemo.

Ovde su navedeni neki primeri kompresovanja:

Examples:

  • compressedbitset: WAH Compressed BitSet for Java
  • javaewah: A compressed alternative to the Java BitSet class (using Enhanced WAH)
  • CONCISE: COmpressed 'N' Composable Integer Set, another bitmap compression scheme for Java
  • EWAHBoolArray: A compressed bitmap/bitset class in C++
  • CSharpEWAH: compressed bitset class in C#
  • SparseBitmap: a simple sparse bitmap implementation in Java

Prednosti i mane[уреди]

Bitski nizovi, uprkos njihovoj jednostavnosti, u nekim slučajevima imaju niz prednosti u odnosu na standardne strukture podataka za neke probleme:

  • Izuzetno su kompaktni.Samo nekoliko drugih struktura podataka može da skladišti n nezavisnih podataka u n/w bitskih reči.
  • Oni omogućavaju malim bitskim nizovima da budu skladišteni u registrima, i da se sa njima manipuliše dug vremenski period bez dodatnog zauzeća memorije.
  • Zbog mogućnosti paralelizma na nivou bita, limitiranog pristupa memoriji, i maksimalnog korišćenja keša procesora (eng. data cache), često pokazuju bolje rezultate nego druge strukture podataka.

Ipak, bitski nizovi nisu uvek rešenje za sve probleme:

  • Bez kompresije, oni su rasipajuća struktura podataka za oskudne nizove (nizovi koji imaju malo elemenata u odnosu na njihovu dužinu) u vremenskom i memorijskom smislu.
  • Pristup pojedinačnim elementima može biti skup i težak za neke programske jezike.

Primena[уреди]

Zbog njihove kompaktnosti, bitski nizovi imaju široku primenu u oblastima gde je memorijski prostor i efikasnost prioritet.Najčešće su korišćeni za jednostavne strukture podataka(eng. flags) koji mogu imati vrednost tačno ili netačno.

Bitski nizovi se koriste za implementaciju politike čekanja(eng. priority queue), gde je bit na poziciji k postavljen na jedinicu samo ako je k na čekanju.

Druga primena bitskih nizova se može naći u Blumovom filteru[2] koji je prostorna efikasna probalistička struktura podataka koja služi za testiranje da li je element član skupa.Takodje bitski niz može biti iskorišćen za pravljenje probalističke heš tabelekoja prihvata lažne negativne ili lažne pozitivne rezultate.

Bitski nizovi i operacije nad njima su jako bitne za konstruisanje jezgrovite strukture podataka(eng. Succinct data structure), koja koristi što manje memorijskog prostora.U tom kontekstu, operacije poput pronalaženja n-tog bita ili brojanje bitova počev od neke pozicije, postaju jako bitne.

Podrška programskim jezicima[уреди]

U programskom jeziku C postoji podrška za rad sa bitskim nizovima. C podržava bitovske operatore (moguće ih je primenjivati samo na celobrojne argumente. Korišćenjem bitskih operatora lako se može pristupiti bitovima.

U programskom jeziku Java postoji klasa BitSet koja kreira bitski niz sa kojim se može manupilusati sa funkcijama koji su dosta slični sa bitskim operatorima u prograsmkom jeziku C.

.NET Framework sadrži kolekcijsku klasu BitArray. Ta klasa može da skladišti vrednosti koji su tipa boolean. Takodje podržava nasumičan pristup i bitske operacije.

Programski jezik Haskell trenutno nema standardnu podršku za bitske operacije, ali i GHC i Hugs imaju modul Data.Bits[3] koji ima odabrane funkcije za rad sa bitskim operacijama.

Reference[уреди]

Spoljašnje veze[уреди]