Programowanie w języku C/C++ » Artykuły

Tablica bitowa

  • 2008-12-11 22:26
  • 8 komentarzy
  • 3151 odsłon
  • Oceń ten tekst jako pierwszy
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

kamcio1 2014-08-10 14:46

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;

Intelli 2008-12-12 16:09

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

toady 2008-12-11 21:01

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.

manfredek 2008-12-11 15:40

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

deus 2008-12-11 23:05

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.

crayze 2008-05-15 16:51

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ę :>

Coldpeer 2008-04-30 13:09

Jak już to <<= :P

nav 2008-04-29 18:00

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.