为何美国政府和民间对华态度迥异
F?név
bit array (tsz. bit arrays)
- (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_tszá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 |