Tablica bitowa

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