bitowe pole vs Bitset

Question

że bity mają być przechowywane w tablicy (np struktury). Więc mogę wykonać jeden z dwóch następujących metod

liczba Approach 1 (AN 1)

struct BIT 
{ 
    int data : 1 
}; 

int main() 
{ 
    BIT a[100]; 
    return 0; 
} 

liczba Podejście 2 (AN 2)

int main() 
{ 
    std::bitset<100> BITS; 
    return 0; 
} 

Dlaczego ktoś wolą 2 nad 1?

Answer 1

ponieważ podejście nr. 2 faktycznie używa 100 bitów pamięci masowej plus trochę bardzo niewielkiego (stałego) narzutu, podczas gdy nr. 1 zazwyczaj wykorzystuje cztery bajty pamięci na strukturę Bit. Ogólnie rzecz biorąc, struct jest co najmniej jednym bajtem na standard C++.

#include <bitset> 
#include <iostream> 

struct Bit { int data : 1; }; 

int main() 
{ 
    Bit a[100]; 
    std::bitset<100> b; 
    std::cout << sizeof(a) << "\n"; 
    std::cout << sizeof(b) << "\n"; 
} 

drukuje

400 
16 

Oprócz tego bitset zawija swoją tablicę bit w ładnym obiektem reprezentacji z wielu przydatnych funkcji.

Answer 2

liczba Approach 1 najprawdopodobniej zostanie skompilowany jako tablica liczb 4-bajtowych i jeden bit każdy będzie używany do przechowywania danych. Teoretycznie inteligentny kompilator mógłby zoptymalizować to, ale nie liczyłbym na to.

Czy istnieje powód, dla którego nie chcesz używać std::bitset?

Answer 3

bitset ma more operations

Answer 4

Cytując cplusplus.com's page on bitset, „Klasa jest bardzo podobna do zwykłej tablicy, ale optymalizacji alokacji przestrzeni”. Jeśli twoje int są 4 bajty, bitset używa 32 razy mniej miejsca.

Nawet robienie , jak zasugerował sbi, jest jeszcze gorsze niż bitset, ponieważ większość implementacji ma> = 1-bajtowe boole.

Jeżeli ze względów intelektualnej ciekawości tylko, chciałeś zaimplementować własną bitset, można to zrobić za pomocą bitowych masek:

typedef struct { 
    unsigned char bytes[100]; 
} MyBitset; 

bool getBit(MyBitset *bitset, int index) 
{ 
    int whichByte = index/8; 
    return bitset->bytes[whichByte] && (1 << (index = % 8)); 
} 

bool setBit(MyBitset *bitset, int index, bool newVal) 
{ 
    int whichByte = index/8; 

    if (newVal) 
    { 
    bitset->bytes[whichByte] |= (1 << (index = % 8)); 
    } 
    else 
    { 
    bitset->bytes[whichByte] &= ~(1 << (index = % 8)); 
    } 
} 

(Przepraszam za korzystanie struct zamiast klasy przy okazji. Myślę w prostym C, ponieważ jestem w trakcie zadania niskiego poziomu dla szkoły, oczywiście dwie ogromne korzyści z używania klasy to przeciążanie operatora i możliwość posiadania tablicy o zmiennej wielkości.)

Answer 5

Dobry wybór zależy od tego, w jaki sposób zamierzasz używać bitów.

std::bitset<N> jest stałym rozmiarze. Visual C++ 10.0 jest niezgodny z wrt. do konstruktorów; na ogół trzeba zapewnić obejście. Był to, jak na ironię, z powodu tego, co Microsoft myśli było bug-fix - wprowadzono konstruktora biorąc int argumentu, o ile pamiętam.

std::vector<bool> jest zoptymalizowany w taki sam sposób, jak std::bitset. Koszt: indeksowanie nie zapewnia bezpośrednio odniesienia (nie ma odniesień do poszczególnych bitów w C++), ale zwraca obiekt proxy - co nie jest czymś, co można zauważyć, dopóki nie spróbujesz użyć go jako punktu odniesienia. Zaleta: minimalne miejsce do przechowywania, a wektor można zmienić w razie potrzeby.

Po prostu za pomocą np. unsigned jest również opcją, jeśli masz do czynienia z niewielką liczbą bitów (w praktyce, 32 lub mniej, chociaż formalna gwarancja to tylko 16 bitów).

Wreszcie, wszystkie identyfikatory WIELKIEJ UPPERC są konwencją (z wyjątkiem Microsoft) zarezerwowaną dla makr, aby zmniejszyć prawdopodobieństwo kolizji nazw. Dlatego dobrze jest nie używać wszystkich identyfikatorów WIELKIEJ UPPERCASE do niczego innego niż makra. I zawsze używać WSZYSTKICH identyfikatorów UPPERCASE dla makr (ułatwia to również ich rozpoznawanie).

Cheers & HTH.,