Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
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.
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.
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.
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
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 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.
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 ( 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.
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:
Bitski nizovi, uprkos njihovoj jednostavnosti, u nekim slučajevima imaju niz prednosti u odnosu na standardne strukture podataka za neke probleme:
Ipak, bitski nizovi nisu uvek rešenje za sve probleme:
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.
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.