A bittömb (más néven bit array, bitmask, 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 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.A bitszintű párhuzamosság (bit-level parallelism) a párhuzamos számítás egy olyan formája, amely a processzor szóméretének növelésén alapul. A szóméret növelése csökkenti azoknak az utasításoknak a számát, amelyeket a processzornak végre kell hajtania ahhoz, hogy olyan változókon végezzen műveletet, amelyek mérete nagyobb, mint a szó hossza. 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 miatt némi hely pazarolódik.
Meghatározás 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ó egy logikai mátrixnak 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 jelenti.Irving Copilowish (December 1948) "Matrix development of the calculus of relations", Journal of Symbolic Logic 13(4): 193–203 Jstor link
Alapvető műveletek 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 () állítson be egy bitet egyre: 11101010 OR 00000100 = 11101110 ÉS () egy bit zéróra állításához: 11101010 AND 11111101 = 11101000 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)
az invertáláshoz vagy a bit váltásához: 11101010 11101110 XOR 00000100 XOR 00000100 = 11101110 = 11101010
minden bit megfordításhoz: NOT 10110010 = 01001101
Az ezekhez a műveletekhez szükséges bitmaszkot ú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 egyszerű bitművelettel (különbség esetén ), valamint bármelyik komplementjét 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 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 referenciahelyel rendelkezik, ami később nagy teljesítménynövekedést eredményez az adat gyorsítótár segítségével.A számítástechnikában a referencia lokalitása, más néven lokalitás elve, a processzor azon tendenciája, hogy rövid időn belül ismétlődően hozzáférjen ugyanahhoz a memóriahely-tartományhoz. Ha egy gyorsítótársor szóból áll, csak körülbelül cache-kihagyás fordul elő.
Bonyolultabb műveletek A karakterláncokhoz hasonlóan egyszerű definiálni a length, substring, lexicographical compare, concatenation, reverse műveleteket. E műveletek némelyikének végrehajtása érzékeny a bájtsorrendre.
Népesség / Hamming-súly 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.
Inverzió 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 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)).
Keresd meg az elsőt A find first set vagy find first one műveletSzámítógépes szoftverekben és hardverekben a find first set vagy find first one egy olyan bitművelet, amely előjel nélküli gépi szó esetén a legkisebb helyiértékű bit indexét vagy pozícióját jelöli ki a szószámlálásban a legkisebb jelentőségű bit helyétől számítva. 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 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) szintén egyszerűen kiterjeszthetők bittömbre.
Tömörítés 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.A számítástechnikában a tömbprogramozás (array programming) olyan megoldásokat jelent, amelyek lehetővé teszik a műveletek egyszerre teljes értékhalmazra történő alkalmazását. 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).Történelmi okokból a bitmap-tömörítés és az invertált listatömörítés külön kutatási területként fejlődött ki, és csak később ismerték el, hogy lényegében ugyanazt a problémát oldják meg.Jianguo Wang; Chunbin Lin; Yannis Papakonstantinou; Steven Swanson. "An Experimental Study of Bitmap Compression vs. Inverted List Compression" . 2017. doi: 10.1145/3035918.3064007
Hátrányok és előnyök 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,A számítástechnikában a Judy-tömb egy olyan adatstruktúra, amely egyfajta asszociatív tömböt valósít meg nagy teljesítménnyel és alacsony memóriahasználattal. trie-ketAz informatikában a trie, más néven digital tree vagy prefix tree egy speciális keresőfa adatstruktúra, amely karakterláncok tárolására és lekérésére szolgál egy szótárból vagy halmazból. 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.
Alkalmazások 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 esetében használják, ahol a indexű bit akkor és csak akkor van beállítva, ha 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órialapok, inode-ok,Az inode (index node – indexcsomópont) egy Unix-stílusú fájlrendszer adatszerkezete, amely fájlrendszerobjektumot, például egy fájlt vagy egy könyvtárat ír le. 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, 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 -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.