Bittömb

A bittömb (más néven bit array, bitmask,^[1] bit map, bit set, bit string, vagy bit vector) egy olyan tömb adatszerkezet, amely kompakt módon tárolja a biteket. Egyszerű halmaz adatszerkezet(wd) megvalósítására használható. A bit tömb hatékonyan kihasználja a hardver bit-szintű párhuzamosságát a műveletek gyors elvégzése érdekében.^[2] Egy tipikus bittömb kw bitet tárol, ahol w a bitek száma a tárolási egységben, például egy bájtban vagy szóban, k pedig egy nemnegatív egész szám. Ha w nem osztja meg a tárolandó bitek számát, akkor a belső töredezettség(wd) miatt némi hely pazarolódik.

A bittömb egy leképezés valamilyen tartományból (szinte mindig egész számok tartományából) a {0, 1} halmaz értékeire. Az értékek értelmezhetők sötét/világos, hiányzó/jelenlévő, zárolt/feloldott, érvényes/érvénytelen stb. értékként. A lényeg az, hogy csak két lehetséges érték van, így ezek egy bitben tárolhatók. Más tömbökhöz hasonlóan, az egyes bitekhez való hozzáférés a tömb indexének alkalmazásával kezelhető. Feltételezve, hogy a tömb mérete (vagy hossza) n bit, a tömb használható a tartomány egy részhalmazának (pl. {0, 1, 2, ..., n−1}) megadására, ahol az 1-bit egy szám jelenlétét, a 0-bit pedig hiányát jelzi a halmazban. Ez a halmaz adatszerkezet körülbelül n/w szónyi helyet használ, ahol w az egyes gépi szavak bitjeinek száma. Az, hogy (a szóban) a legkisebb értékű bit vagy a legnagyobb értékű bit jelzi-e a legkisebb indexszámot, nagyrészt lényegtelen, de az előbbi általában előnyösebb (kis-endian gépeken).

Egy véges bináris reláció(wd) egy logikai mátrixnak(wd) nevezett bittömbbel ábrázolható. A relációs algebrában ezeket a tömböket mátrixszorzással állítják össze, ahol az aritmetika Boole-szerű, és egy ilyen összeállítás relációk kompozícióját(wd) jelenti.^[3]

Bár a legtöbb gép nem képes a memóriában egyes biteket megszólítani, és nem is rendelkezik utasításokkal az egyes bitek manipulálására, a word egyes bitjei kiemelhetők és manipulálhatók bitműveletekkel. Különösen:

A vagy-művelettel (OR) állítson be egy bitet egyre:

   11101010
OR 00000100
 = 11101110

ÉS (AND) egy bit zéróra állításához:

    11101010
AND 11111101
  = 11101000

AND annak meghatározásához, hogy egy bit be van-e állítva, zéró-teszteléssel:

       11101010                11101010
   AND 00000001            AND 00000010
     = 00000000              = 00000010
(=0 ∴ bit nincs beállítva)     (≠0 ∴ bit be van állítva)

XOR az invertáláshoz vagy a bit váltásához:

    11101010        11101110
XOR 00000100    XOR 00000100
  = 11101110      = 11101010

NOT minden bit megfordításhoz:

NOT 10110010
  = 01001101

Az ezekhez a műveletekhez szükséges bitmaszkot(wd) úgy kapjuk meg, hogy egy biteltolás operátorral (<<) az 1-es számot a megfelelő számú hellyel balra toljuk, valamint szükség esetén bitenkénti negálással.

Adott két azonos méretű, halmazokat reprezentáló bittömböt, ezek unióját, metszetét és halmazelméleti különbségét egyenként n/w egyszerű bitművelettel (különbség esetén 2n/w), valamint bármelyik komplementjét(wd) kiszámíthatjuk:

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

Ha egy bittömb bitjein szeretnénk végigmenni, akkor ezt hatékonyan megtehetjük egy kétszeresen egymásba ágyazott ciklus segítségével, amely minden egyes szón egyenként végigfut. Csak n/w memória-hozzáférésekre van szükség:

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

Mindkét kódminta ideális referenciális lokalitással rendelkezik, ami később nagy teljesítménynövekedést eredményez az adat gyorsítótár segítségével.^[4] Ha egy gyorsítótársor k szóból áll, csak körülbelül n/wk cache-kihagyás fordul elő.

A karakterláncokhoz hasonlóan egyszerű definiálni a length, substring, lexicographical(wd) compare, concatenation, reverse műveleteket. E műveletek némelyikének végrehajtása érzékeny a bájtsorrendre.

Ha egy bittömbben az 1 bitek számát szeretnénk megtalálni, amit néha populációszámnak vagy Hamming-súlynak neveznek, akkor léteznek hatékony, elágazásmentes algoritmusok, amelyek egyszerű bitműveletek sorozatával kiszámítják a bitek számát egy szóban. Egyszerűen lefuttatunk egy ilyen algoritmust minden egyes szóra, és összegezzük a futások eredményét. A nullák számlálása hasonló. A hatékony megvalósításra vonatkozó példákat lásd a Hamming-súly szócikkben.

Az egy bit-per-pixeles kép függőleges átfordítása, vagy néhány FFT algoritmus, az egyes szavak bitjeinek átfordítását igényli (így b31 b30 ... b0 b0 ... b30 b31 lesz). Ha ez a művelet nem áll rendelkezésre a processzoron, akkor is lehetséges egymást követő átmenetekkel haladni, ebben a példában 32 biten:

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

A find first set vagy find first one művelet^[5] egy tömbben a legkisebb indexű 1-bit indexét vagy pozícióját azonosítja, és széles körben elterjedt hardveres támogatással (egy szónál nem nagyobb tömbök esetén) és hatékony algoritmusokkal rendelkezik a számításához. Ha egy prioritási sor(wd) egy bittömbben van tárolva, a find first one művelet használható a sor legmagasabb prioritású elemének azonosítására. A szóméretű find first one hosszabb tömbökre való kiterjesztéséhez megkereshetjük az első nem nulla szót, majd a find first one keresést futtathatjuk ezen a szón. A kapcsolódó műveletek find first zero, count leading zeros, count leading ones, count trailing zeros, count trailing ones, és log base 2 (lásd find first set(wd)) szintén egyszerűen kiterjeszthetők bittömbre.

A bittömb a legsűrűbb tároló a „random” bitek számára, azaz ahol minden bit egyforma valószínűséggel 0 vagy 1, és mindegyik független. A legtöbb adat azonban nem véletlenszerű, ezért lehet tömörebben tárolni. Például egy tipikus faxkép adatai nem véletlenszerűek, és tömöríthetők. A hosszú adatfolyamok tömörítésére általában a futáshossz-kódolást használják. A legtöbb tömörített adatformátumhoz azonban nem olyan könnyű közvetlenül hozzáférni; továbbá a bittömbök túl agresszív tömörítésével azt kockáztatjuk, hogy elveszítjük a bit-szintű párhuzamosságból (vektorizáció) származó előnyöket.^[6] Ezért ahelyett, hogy a bittömböket bitfolyamként tömörítenénk, inkább bájt- vagy szófolyamként tömöríthetnénk őket (lásd Bittérkép-index#tömörítés(wd)).^[7][8]

A bittáblák egyszerűségük ellenére számos jelentős előnnyel rendelkeznek más adatstruktúrákkal szemben ugyanezen problémák esetében:

• Rendkívül kompaktak; egyetlen más adatszerkezet sem képes n független adatot tárolni n/w szóval.
• Ezek lehetővé teszik, hogy kis bittömböket tároljanak és manipuláljanak a regiszterkészletben hosszú időn keresztül, memória-hozzáférések nélkül.
• Mivel képesek kihasználni a bit-szintű párhuzamosságot, korlátozzák a memória-hozzáférést és maximálisan kihasználják a gyorsítótárat, gyakran felülmúlnak számos más adatstruktúrát gyakorlati adathalmazokon, még azokat is, amelyek aszimptotikusan hatékonyabbak.

A bit tömbök azonban nem jelentenek megoldást mindenre. Különösen:

• Tömörítés nélkül ezek a ritka halmazok (a tartományukhoz képest kevés elemmel rendelkező halmazok) idő- és térpazarló adatszerkezetei. Az ilyen alkalmazásoknál inkább a tömörített bittömböket, Judy-tömböket(wd),^[9] trie-ket(wd)^[10] vagy akár Bloom-szűrőket kell fontolóra venni.
• Az egyes elemek elérése költséges és nehezen kifejezhető lehet egyes nyelveken. Ha a véletlenszerű hozzáférés gyakoribb, mint a szekvenciális, és a tömb viszonylag kicsi, a bájtos címzésű gépen előnyösebb lehet a bájtos tömb. A szótömb azonban valószínűleg nem indokolt a hatalmas helyterhelés és az általa okozott további gyorsítótár-kihagyások miatt, kivéve, ha a gép csak szócímzéssel rendelkezik.

Kompaktságuk miatt a bittömböknek számos alkalmazásuk van olyan területeken, ahol a hely vagy a hatékonyság a legfontosabb. Leggyakrabban logikai flag-ek egyszerű csoportjának vagy Boole-értékek rendezett sorozatának ábrázolására használják őket.

A bittömböket prioritási sorok(wd) esetében használják, ahol a k indexű bit akkor és csak akkor van beállítva, ha k a sorban van; ezt az adatszerkezetet használja például a Linux kernel, és nagy előnye van a hardveres find-first-zero műveletnek.

A bittömbök használhatók memória-lapok(wd), inode-ok(wd),^[11] lemezszektorok stb. kiosztására. Ilyen esetekben a bitmap kifejezés használható. Ezt a kifejezést azonban gyakran a raszteres képekre használják, amelyek pixelenként több bitet is használhatnak.

A bittömbök másik alkalmazása a Bloom-szűrő, egy valószínűségi halmaz adatszerkezet(wd), amely kis hibavalószínűségért cserébe nagy halmazokat képes kis helyen tárolni. Lehetőség van olyan valószínűségi hash-táblák építésére is, amelyek bittömbökön alapulnak, és amelyek elfogadják a hamis pozitív vagy hamis negatív eredményt.

A bittömbök és a rajtuk végzett műveletek szintén fontosak a tömör adatszerkezetek létrehozásához, amelyek a lehető legkevesebb helyet használják. Ebben az összefüggésben olyan műveletek válnak fontossá, mint az n-edik 1 bit megtalálása vagy az 1 bitek számának megszámlálása egy bizonyos pozícióig.

A bittömbök hasznos absztrakciót jelentenek a tömörített adatfolyamok vizsgálatához is, amelyek gyakran tartalmaznak olyan elemeket, amelyek bájtrészeket foglalnak el, vagy nem bájt-kiosztásúak. Például egyetlen 8 bites karakter tömörített Huffman-kódolású ábrázolása 1 és 255 bit között lehet.

Az információkeresésben a bittömbök jól reprezentálják a nagyon gyakori kifejezések kiküldési listáit.^[12] Ha egy szigorúan növekvő egész számokból álló listában kiszámítjuk a szomszédos értékek közötti hézagokat, és azokat unáris kódolással(wd) kódoljuk, akkor az eredmény egy olyan bittömb lesz, amelynek n-edik pozíciójában 1 bit van, ha és csak akkor, ha n szerepel a listában. Az n-es rés implikált valószínűsége 1/2ⁿ. Ez a Golomb-kódolás(wd)^[13] speciális esete is, ahol az M paraméter 1; ezt a paramétert általában csak akkor választjuk ki, ha −log(2 − p) / log(1 − p) ≤ 1, vagy ha a kifejezés a dokumentumok legalább 38%-ában előfordul.

Az APL programozási nyelv teljes mértékben támogatja a tetszőleges alakú és méretű bittömböket, mint az egész számoktól eltérő Boolean adattípust. Minden nagyobb implementáció (Dyalog APL, APL2, APL Next, NARS2000, Gnu APL stb.) sűrűn pakolja a biteket bármilyen méretű gépi szóba. A biteket a szokásos indexelési jelöléssel (A[3]), valamint az összes szokásos primitív függvényen és operátoron keresztül külön-külön is elérhetjük, ahol gyakran egy speciális algoritmus segítségével operálunk velük, például a bitek összegzésével a bájtok táblázatos keresése révén.

A C programozási nyelv bitmezői, a struktúrákban található pszeudo-objektumok, amelyek mérete bizonyos számú bitnek felel meg, valójában kis bittömbök; korlátozza őket, hogy nem tudnak szavakra kiterjedni. Bár kényelmes szintaxist biztosítanak, a biteket a legtöbb gépen még mindig bájtos operátorokkal lehet elérni, és csak statikusan definiálhatók (a C statikus tömbjeihez hasonlóan a méretük a fordításkor rögzül). Szintén gyakori idióma a C programozók számára, hogy a szavakat kis bittömbökként használják, és bitoperátorok segítségével érik el azok bitjeit. Az X11 rendszerben található, széles körben elérhető fejlécfájl, az xtrapbits.h „egy hordozható módszer a rendszerek számára a bittömbök bitmező manipulációjának meghatározására”. A fent említett megközelítés bővebb leírása a comp.lang.c faq-ban található.

A C++-ban, bár az egyes bool-ok jellemzően ugyanannyi helyet foglalnak el, mint egy bájt vagy egy egész szám, az STL vector<bool> típusa egy részleges sablon specializáció, amelyben a bitek helyhatékonysági optimalizálásként vannak becsomagolva.^[14] Mivel a bájtok (és nem a bitek) a legkisebb címezhető egység a C++-ban, a [] operátor nem egy elemre való hivatkozást ad vissza, hanem egy proxy-hivatkozást. Ez apróságnak tűnhet, de ez azt jelenti, hogy a vector<bool> nem egy szabványos STL tároló, ezért a vector<bool> használatától általában óva intenek. Egy másik egyedi STL-osztály, a bitset,^[15] a fordítási időben meghatározott méretben rögzített bitekből álló vektort hoz létre, és interfészében és szintaxisában jobban hasonlít a szavaknak a C programozók által bitkészletként való idiomatikus használatára. Emellett rendelkezik néhány további képességgel is, mint például a beállított bitek száma hatékony számlálásának képessége. A Boost C++ könyvtárak(wd) biztosítanak egy dynamic_bitset osztályt^[16], amelynek mérete a futási időben adható meg.^[17]

A D programozási nyelv a szabványos könyvtárában, a Phobosban, az std.bitmanip állományban biztosítja a bittömböket. A C++-hoz hasonlóan a [] operátor nem ad vissza hivatkozást, mivel az egyes bitek a legtöbb hardveren nem címezhetőek közvetlenül, hanem egy bool-t ad vissza.

Javában a BitSet osztály egy bittömböt hoz létre, amelyet aztán a C programozók által ismert bitenkénti operátorokról elnevezett függvényekkel lehet kezelni. A C++-ban található bitset-tel ellentétben a Java BitSet nem rendelkezik „méret” állapottal (gyakorlatilag végtelen méretű, 0 bitekkel inicializálva); egy bit bármely indexen beállítható vagy tesztelhető. Ezen kívül létezik egy EnumSet osztály, amely egy felsorolásos típusú(wd) értékkészletet belsőleg bitvektorként reprezentál, a bitmezők biztonságosabb alternatívájaként.

A .NET keretrendszer egy BitArray gyűjteményi osztályt biztosít. A biteket egy int típusú tömb segítségével tárolja (a tömb minden eleme általában 32 bitet képvisel).^[18] Az osztály támogatja a véletlenszerű hozzáférést (random access) és a bitenkénti operátorokat, iterálható, és a Length tulajdonsága megváltoztatható, hogy növelje vagy csonkítsa.

Bár a Standard ML nem támogatja a bittömböket, a Standard ML of New Jersey(wd) rendelkezik egy kiterjesztéssel, a BitArray struktúrával az SML/NJ könyvtárában. Ez nem rögzített méretű, és támogatja a halmazműveleteket és a bitműveleteket, beleértve szokatlan módon a shiftműveleteket is.

A Haskell jelenleg szintén nem rendelkezik szabványos támogatással a bitenkénti műveletekhez, de mind a GHC(wd), mind a Hugs(wd) biztosít egy Data.Bits modult válogatott bitenkénti függvényekkel és operátorokkal, beleértve a shift és rotate műveleteket, és egy „unboxed” tömb Boolean értékek felett használható egy Bit-tömb modellezésére, bár az előbbi modulból hiányzik a támogatás.

Perlben a karakterláncok bővíthető bittömbökként használhatók. Ezeket a szokásos bitenkénti operátorokkal (~ | & ^) lehet manipulálni,^[19] az egyes bitek pedig a vec függvénnyel tesztelhetők és állíthatók be.^[20]

A Ruby-ban egy egész szám (Fixnum vagy Bignum) egy bitjét a zárójeles operátor ([]) segítségével érheti el (de nem állíthatja be), mintha az egy bitekből álló tömb lenne.

Az Apple Core Foundation könyvtár^[21] CFBitVector és CFMutableBitVector struktúrákat tartalmaz.

A PL/I támogatja a tetszőleges hosszúságú bitsorozatok tömbjeit, amelyek lehetnek fix hosszúságúak vagy változó hosszúságúak. A tömb elemei lehetnek igazítottak — minden elem egy bájt- vagy szóhatáron kezdődik — vagy nem igazítottak — az elemek közvetlenül követik egymást kitöltés nélkül.

A PL/pgSQL(wd) és a PostgreSQL SQL natív típusként támogatja a bitsorozatokat (bit strings). Két SQL bit típus létezik: bit(n) és bit varying(n), ahol n egy pozitív egész szám.^[22]

Az olyan hardverleíró nyelvek, mint a VHDL, Verilog és SystemVerilog(wd) natívan támogatják a bitvektorokat, mivel ezeket olyan tárolóelemek, mint a flip-flopok, hardverbuszok és általában a hardverjelek modellezésére használják. Az olyan hardververifikációs nyelvekben, mint az OpenVera(wd), e(wd) és SystemVerilog, a bitvektorokat a hardvermodellekből származó értékek mintavételezésére, valamint a szimulációk során a hardverre továbbított adatok ábrázolására használják.

A Common Lisp a beépített array speciális eseteként egy egydimenziós bit-vector implementációt biztosít, amely kettős minőségben, osztályként és típusmeghatározóként is működik.^[23] A tömb származékaként az általános make-array függvényre támaszkodik, amelyet bit elemtípussal kell konfigurálni, ami opcionálisan lehetővé teszi a bitvektor dinamikusan átméretezhetővé tételét. A bit-vector azonban nem végtelen kiterjedésű. Létezik egy korlátozottabb simple-bit-vector típus, amely kifejezetten kizárja a dinamikus jellemzőket.^[24] A bitvektorok a #*bits reader macro-val ábrázolhatók és szerkeszthetők tömörebben.^[25] A minden tömbre alkalmazható általános függvényeken kívül léteznek speciális műveletek a bitvektorokra. Az egyes biteket a bit és sbit függvények^[26] segítségével lehet elérni és módosítani, és számos logikai művelet támogatott.^[27]

• Aritmetikai-logikai egység
• Kettes számrendszer
• Bitművelet
• Bitmező
• Bitstream

• Ez a szócikk részben vagy egészben a Bit array című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.