bit array

Angol

Főnév

bit array (tsz. bit arrays)

1. (informatika) A bit array (magyarul: bittömb, bitvektor, vagy egyszerűen bitsorozat) egy olyan adatszerkezet, amelyben az adatok egymás után, bitenként vannak tárolva. Minden elem egyetlen bit, azaz 0 vagy 1 értéket vehet fel. Ez az adatszerkezet memóriahatékony megoldás nagy mennyiségű bináris adat tárolására.

---

Miért hasznos a bit array?

• Memóriatakarékosság: Egyetlen bitet használ minden elem tárolására, szemben egy normál bool típus által használt akár 1 byte-tal (8 bit). Így például 8 bool érték elfér 1 byte-ban.
• Gyors logikai műveletek: A bitekre közvetlenül alkalmazhatók bitműveletek (AND, OR, XOR, NOT), amelyek nagyon gyorsak.
• Alkalmazások:
  • Halmazok reprezentálása (pl. elemek előfordulásának jelölése)
  • Sziták (Eratosthenész szita)
  • Bloom filterek
  • Jogosultsági mátrixok
  • Kompakt jelölések, indexelés

---

Hogyan működik?

Egy bit array általában egy vagy több egész szám (például int, uint32_t, uint64_t) belső tömbként van megvalósítva, ahol minden bit egy-egy logikai állapotot reprezentál.

Példa:

• Ha van egy 32 bites uint32_t számunk, akkor egyetlen változó 32 darab bitnyi információt tárolhat.
• Az i-edik bithez való hozzáféréshez biteltolást és maszkolást használunk:

#include <cstdint>

// Példa: bit beállítása és lekérdezése egy 32 bites számban
uint32_t bits = 0; // minden bit 0

// i-edik bit beállítása 1-re
void setBit(uint32_t& bits, int i) {
    bits |= (1u << i);
}

// i-edik bit lekérdezése (0 vagy 1)
bool getBit(uint32_t bits, int i) {
    return (bits >> i) & 1u;
}

---

Bit array műveletek

• Beállítás (set): Egy adott bit értékének 1-re állítása.
• Törlés (clear): Egy adott bit értékének 0-ra állítása.
• Lekérdezés (get/test): Egy adott bit értékének lekérése.
• Toggle (invert): Egy bit értékének megfordítása.
• Bitműveletek: Több bit array egymáson végzett AND, OR, XOR, NOT műveletek.

---

Példák bit array alkalmazásra

• Eratosthenész szita: Nagy prímszámok keresése, ahol a számokat bitek reprezentálják (prím/nem prím).
• Bloom filter: Gyors halmazellenőrző adatstruktúra, amely hash függvények segítségével bit array-t kezel.
• Jogosultságok tárolása: Egy rendszerben egy-egy bit jelezhet egy adott jogosultságot.
• Képadatok: Bitmap képek pixeleinek tárolása.

---

Összefoglalás

Tulajdonság	Leírás
Tárolási egység	Egyetlen bit (0 vagy 1)
Memóriahatékonyság	Nagyon magas, 8x jobb mint a bool tömbök
Gyors műveletek	Bitműveletek (AND, OR, XOR, NOT)
Használati területek	Szita, bloom filter, jogosultság, bitmap

További információk

• bit array - Szótár.net (en-hu)
• bit array - Sztaki (en-hu)
• bit array - Merriam–Webster
• bit array - Cambridge
• bit array - WordNet
• bit array - Яндекс (en-ru)
• bit array - Google (en-hu)
• bit array - Wikidata
• bit array - Wikipédia (angol)