Битски низ

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

Битски низ (енг. Бит арраy) је низ који складишти битове. Може бити коришћен као једноставна структура података. Битски низ је веома ефикасан зато што се операције над битовима извршавају брзо.

Дефиниција[уреди | уреди извор]

Битски низ се користи за обележавање неких података вредностима {0,1}. Вредност бита може бити интерпретирана на разне начине, на пример присутан/одсутан, закљуцан/откљуцан, тацно/нетацно, итд. Поента је да постоје само две могуце вредности и самим тим се могу сместити у један бит.

Основне операције[уреди | уреди извор]

Иако већина машина није у стању да адресира појединачне битове, нити имају инструкције за баратање појединачним битовима, сваким битом се може манипулисати коришћењем битских оператора.

  • Битовско ИЛИ (енг. ОР) може бити коришћено за постављање неког бита на јединицу : 11101010 ОР 00000100 = 11101110
  • Битовско I (енг. АНД) може бити коришћено за постављање неког бита на нулу: 11101010 АНД 11111101 = 11101000
  • Са битским оператором I можемо проверити да ли бит на некој позицији има вредност 1 или 0:
11101010 АНД 00000001 = 00000000 = 0
11101010 АНД 00000010 = 00000010 ≠ 0
  • Ексклузивно ИЛИ (енг. XОР) може бити коришћено за инвертовање неког бита:
11101010 XОР 00000100 = 11101110
11101110 XОР 00000100 = 11101010
  • Битска Негација (енг. НОТ) може бити коришћена за инвертовање свих битова:
НОТ 10110010 = 01001101

Како би се постигао жељени ефекат над битовима датог броја, обичај је да се врши његово комбиновање битовским операторима са специјално припремљеним константама које се обично називају маске. Маску можемо померати Битским шифтовањем у леву страну или у десну страну(>>, <<).

За два задата битска низа исте дужине , можемо одредити њихову унију(енг. унион),пресек(енг. интерсецтион) и разлику(енг. диференце) користећи н/w једноставних битских операција (2н/w за разлику), као и комплемент(енг. цомплемент) оба низа: 

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

Ако желимо да продјемо кроз низ битова и да извршимо неку обраду тог низа, то можемо да урадимо ефикасно користећи двоструку угнежђену петљу. Само н/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


Пребројавање[уреди | уреди извор]

Ако желимо да надјемо број битова који имају вредност 1,користимо алгоритам пребројавање (енг. Хамминг wеигхт). Постоји доста ефикасних алгоритама, који пребројавају битове користећи једноставне битске операције.

Сортирање[уреди | уреди извор]

Сортирање битског низа се лако може урадити у временској сложености О(н). Прво пребројимо колико има јединица и ако их има к , тих к јединица ставимо на крај низа, а остатак низа попунимо нулама.

Инверзија[уреди | уреди извор]

Вертикално окретање слике која заузима један бит по пикселу ( енг. оне-бит-пер-пиxел ), захтева замену битова појединих речи па b31 b30 ... b0 постаје b0 ... b30 b31. Када ова операција није доступна на процесору, и даље је могуће да се ово уради сукцесивним пролазом, на пример за 32 бита: 

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

Пронаћи прву јединицу[уреди | уреди извор]

Пронаћи прву јединицу ( енг. финд фирст сет-ФФС ) је операција која проналази индекс или позицију бита који има најмању тежину у битској речи ( енг. wорд ). Ова операција има широку хардверску подршку и ефикасне алгоритме за њено извршавање. Како би овај алгоритам радио и за дуже битске низове, који имају више битских речи, можемо прво пронаћи прву битску реч која је различита од нуле, и онда на ту реч применити ФФС.

Компресија[уреди | уреди извор]

Битски низ је најгушће паковање за битове, где је сваки бит незивисан и има вредност један или нула.Већина података није независна(низ битова који чине тај податак нису насумичним редом поредјани), па је могуће да се ти подаци компактније сачувају. На пример обичну слику можемо компресовати тако да заузима мање меморије.Кодирање(енг. Рун-ленгтх енцодинг (РЛЕ)[1] )је најчешће коришћено за компресовање дугих низова.Са друге стране, ако компресујемо битове превише агресивно излажемо се ризику да изгубимо квалитет податка који компресујемо.

Овде су наведени неки примери компресовања:

Еxамплес:

  • цомпресседбитсет: WАХ Цомпрессед БитСет фор Јава
  • јаваеwах: А цомпрессед алтернативе то тхе Јава БитСет цласс (усинг Енханцед WАХ)
  • ЦОНЦИСЕ: ЦОмпрессед 'Н' Цомпосабле Интегер Сет, анотхер битмап цомпрессион сцхеме фор Јава
  • ЕWАХБоолАрраy: А цомпрессед битмап/битсет цласс ин C++
  • ЦСхарпЕWАХ: цомпрессед битсет цласс ин C#
  • СпарсеБитмап: а симпле спарсе битмап имплементатион ин Јава

Предности и мане[уреди | уреди извор]

Битски низови, упркос њиховој једноставности, у неким случајевима имају низ предности у односу на стандардне структуре података за неке проблеме:

  • Изузетно су компактни.Само неколико других структура података може да складишти н независних података у н/w битских речи.
  • Они омогућавају малим битским низовима да буду складиштени у регистрима, и да се са њима манипулише дуг временски период без додатног заузећа меморије.
  • Због могућности паралелизма на нивоу бита, лимитираног приступа меморији, и максималног коришћења кеша процесора (енг. дата цацхе), често показују боље резултате него друге структуре података.

Ипак, битски низови нису увек решење за све проблеме:

  • Без компресије, они су расипајућа структура података за оскудне низове (низови који имају мало елемената у односу на њихову дужину) у временском и меморијском смислу.
  • Приступ појединачним елементима може бити скуп и тежак за неке програмске језике.

Примена[уреди | уреди извор]

Због њихове компактности, битски низови имају широку примену у областима где је меморијски простор и ефикасност приоритет.Најчешће су коришћени за једноставне структуре података(енг. флагс) који могу имати вредност тачно или нетачно.

Битски низови се користе за имплементацију политике чекања(енг. приоритy qуеуе), где је бит на позицији к постављен на јединицу само ако је к на чекању.

Друга примена битских низова се може наћи у Блумовом филтеру[2] који је просторна ефикасна пробалистичка структура података која служи за тестирање да ли је елемент члан скупа.Такодје битски низ може бити искоришћен за прављење пробалистичке хеш табелекоја прихвата лажне негативне или лажне позитивне резултате.

Битски низови и операције над њима су јако битне за конструисање језгровите структуре података(енг. Суццинцт дата струцтуре), која користи што мање меморијског простора.У том контексту, операције попут проналажења н-тог бита или бројање битова почев од неке позиције, постају јако битне.

Подршка програмским језицима[уреди | уреди извор]

У програмском језику C постоји подршка за рад са битским низовима. C подржава битовске операторе (могуће их је примењивати само на целобројне аргументе. Коришћењем битских оператора лако се може приступити битовима.

У програмском језику Јава постоји класа BitSet која креира битски низ са којим се може манупилусати са функцијама који су доста слични са битским операторима у програсмком језику C.

.НЕТ Фрамеwорк садржи колекцијску класу BitArray. Та класа може да складишти вредности који су типа боолеан. Такодје подржава насумичан приступ и битске операције.

Програмски језик Хаскелл тренутно нема стандардну подршку за битске операције, али и ГХЦ и Хугс имају модул Data.Bits[3] који има одабране функције за рад са битским операцијама.

Референце[уреди | уреди извор]

  1. ^ Рун-Ленгтх Енцодинг (РЛЕ)
  2. ^ www.цс.уцхицаго.еду/~матеи/ПАПЕРС/бф.доц‎
  3. ^ Дата.Битс

Спољашње везе[уреди | уреди извор]

Преузето из „https://sr.wikipedia.org/w/index.php?title=Bitski_niz&oldid=26730939”