Tablica bitowa

crayze

Ostatnio w komentarzach jednego z artykułów znalazłem:
„Mądrzejsze pytanie:
Dlaczego tablica bool a[8] zajmuje 8 bajtów, a nie 1. No cóż - to jedna z nielicznych wad C++” (użytkownik: JaskMar)

Niestety trzeba się z tym stwierdzeniem zgodzić, ale czy musi tak być na pewno? Można sobie samemu napisać taką „jakby” tablicę bool, w której bool zajmie nam 1 bit. Oto co udało mi się wyskrobać:

/*plik: <bitstable>
Autor: crayze*/

class CBitsTable
{
  public:
    CBitsTable(unsigned int);//constructor
    ~CBitsTable();//deconstructor
    void SetBit(unsigned int,bool);//setting specified bit value
    bool GetBit(unsigned int);//getting specified bit value
    void ZeroTable();//Zero table memory
    unsigned int GetBitsSize();//Get virtual size
    unsigned int GetRealSize();//Get real size
  private:
    unsigned char* table;
    unsigned int BitsSize;
    unsigned int RealSize;
};

CBitsTable::CBitsTable(unsigned int bits)
{
  BitsSize=bits;
  RealSize=BitsSize/8;
  if(BitsSize%8) RealSize++;
  if(BitsSize) table=new unsigned char[RealSize]; else table=0;
}

CBitsTable::~CBitsTable()
{
  delete[] table;
}

void CBitsTable::SetBit(unsigned int index,bool value)
{
  if(table==0||index>=BitsSize) return;
  unsigned int ByteIndex=index/8;
  unsigned int BitIndex=index%8;
  unsigned char Mask;
  Mask=0x01;
  for(register unsigned int i=0;i<BitIndex;i++) Mask*=2;
  if(value==true)
  {
    table[ByteIndex]|=Mask;
  }
  else
  {
    Mask=~Mask;
    table[ByteIndex]&=Mask;
  }
}

bool CBitsTable::GetBit(unsigned int index)
{
  if(table==0) return false;
  unsigned int ByteIndex=index/8;
  unsigned int BitIndex=index%8;
  char Mask=1;
  for(register unsigned int i=0;i<BitIndex;i++) Mask*=2;
  if(table[ByteIndex]&Mask) return true; else return false;
}

unsigned int CBitsTable::GetBitsSize()
{
  return BitsSize;
}

unsigned int CBitsTable::GetRealSize()
{
  return RealSize;
}

void CBitsTable::ZeroTable()
{
  for(register unsigned int i=0;i<RealSize;i++) table[i]=0;
}

Napisałem sobie prostą klasę, która będzie tworzyła tablicę i operowała w niej na pojedynczych bitach.

Metody:
CBitsTable(unsigned int); - konstruktor, jako parametr podajemy wielkość tablicy w bitach!
~CBitsTable(); - dekonstruktor, usuwa dynamiczną tablicę
void SetBit(unsigned int,bool); - ustawia bit, pierwszy parametr to index bitu(tak jak indeksy w tablicy), natomiast drugi to wartość bitu(true – 1 lub false - 0)
bool GetBit(unsigned int); - zwraca wartość bitu w typie bool, parametr to index bitu
void ZeroTable(); - zeruje zawartość tablicy(ustawia wszystkie bity na 0)
unsigned int GetBitsSize(); - zwraca wielkość tablicy w bitach(wartość z konstruktora)
unsigned int GetRealSize(); - zwraca rzeczywisty rozmiar tablicy w bajtach

A to mały przykładzik:

#include "bitstable"
#include <iostream>

using namespace std;

int main(int,char**)
{
  cout<<"Podaj wielkosc tablicy bitow(w bitach): ";
  unsigned int size;
  cin>>size;
  CBitsTable* BT=new CBitsTable(size);
  BT->ZeroTable();
  cout<<"\nRozmiar w bitach: "<<BT->GetBitsSize()<<"\nRozmiar w bajtach: "<<BT->GetRealSize()<<endl;

  cout<<"\n\nTablica:\n";
  for(unsigned int i=0;i<BT->GetBitsSize();i++) if(BT->GetBit(i)) cout<<"1"; else cout<<"0";

  while(1)
  { 
    unsigned int w;
    bool b;
    cout<<"\n\nModyfikacja:\nPodaj numer bitu: ";
    cin>>w;
    cout<<"Podaj wartosc bitu(0 lub 1): ";
    cin>>b;
    BT->SetBit(w,b);

    cout<<"\nTablica:\n";
    for(unsigned int i=0;i<BT->GetBitsSize();i++) if(BT->GetBit(i)) cout<<"1"; else cout<<"0";

    bool c;
    cout<<"\nJesli chesz kontynuowac podaj 1: ";
    cin>>c;
    if(c==false) break;
  }
  delete BT;
  return 0;
}

Oszczędność zajmowanej pamięci jest bardzo duża, wiadomo im większa tablica, tym większa oszczędność, np.
bool tab[20]; - 20B / CBitsTable tab(20); - 3B
bool tab[200]; - 200B / CBitsTable tab(200); - 25B
bool tab[2000]; - 2000B / CBitsTable tab(2000); - 250B
bool tab[10500]; - 10500B / CBitsTable tab(10500); - 1313B
klasyczne: bool tab[8]; - 8B / CBitsTable tab(8); - 1B

8 komentarzy

Ja bym to tak zrobił:

template<typename T>
class BitValue
{
public:
    T Value : 1;
    unsigned OriginalSize() const
    {
        return sizeof(T);
    }
};

Albo klasa służąca do zmiany pojedynczych bitów (poprzez konwersję wskaźnika):

struct Byte
{
    bool B1 : 1,
           B2:  1,
           B3:  1,
           B4:  1,
           B5:  1,
           B6:  1,
           B7:  1,
           B8:  1
};
unsigned char a;
Byte *b = (Byte*) &a;

W STL-u jest bitset. Po co znowu odkrywać koło?

  1. tablica bool a[8] NIEKONIECZNIE zajmuje 8 bajtów - to zalezy od definicji typu bool. Zwykle sizeof(bool) = 1, ale w starszych wersjach Ms Visual C++ byly to 4 bajty na bool.

  2. Nie wiem co autor chcial osiagnac, poza walorem edukacyjnym takiego rozwiazania.
    W obecnych czasach, gdy sa dostepne stosnkowo tanie pamieci masowe i RAM ilosc zajmowanej pamieci nie stanowi duzego problemu, natomiast taka implementacja ma olbrzymi wplyw na wydajnosc - dla procesora nie jest istotne czy wyciaga 1 bajt czy 4 z RAMu - to i tak zajmuje jeden cykl przy 32 bitowej maszynie, natomiast proponowane rozwiazanie narzuca kilkanascie operacji matematycznych, bitshiftow, a w efekcie i tak konwersje typow do bool.
    Wady przewyzszaja niestety zalety. Rozwiazanie moze miec sens kiedy ilosc pamieci ma duze znaczenie, np. w aplikacjach embedded. Tyle tylko, ze wtedy rzadko uzywa sie jezyka C++ z uwagi wlasnie na wymagania pamieciowe i wydajnosciowe tego jezyka.

  3. Nie rozumiem tego:
    RealSize=BitsSize >> 3;
    if(BitsSize & 7) RealSize++; // 7 == 00000111b
    Mamy tu: bitshift, przypisanie, and, porownanie i inkrementacje. Wbrew pozorom, dzielenie wcale nie jest takie wolne a juz na pewno nie jest wolniejsze niz taka kominacja. IMHO lepiej wiec zrobic
    RealSize = BitSize/8; // wynik dzielenia zaokroglony jest w dol wiec nastepna linia
    if (BitSize % 8) RealSize++; // zaokragla w gore wielkosci nie bedace wielokrotnoscia 8

  4. Komentarz o tym jak binarnie kodowana jest liczba 7 nie ma zadnej wartosci dokumentacyjnej.
    Zamiast tego powinien sie znalezc komentarz DLACZEGO taka operacja jest wykonywana.

Dzielenie jest WOOOOLNE! Ponieważ były używane potęgi dwójki, poprawiłem to na operacje bitowe...

To ja może przypomnę, że vector<bool> jest specjalizowany, każdy bool jest reprezentowany w postaci jedego bitu. Po co bawić się własnymi kiepskimi rozwiązaniami skoro są gotowe optymalne. Proponuję zapoznanie się ze standardem.

Jak ktoś ma ochotę i czas, to niech dorobi operator [], i zmieni na <<= jeśli komuś przeszkadza :>
Jak nie to if(nie zapomnę && będę miał czas && będę miał chęci) sam przerobię :>

Jak już to <<= :P

for(register unsigned int i=0;i<BitIndex;i++) Mask*=2;
A czemu nie po prostu
Mask << BitIndex? No i operator [] by ułatwił używanie.