Programowanie w języku C/C++

Pola bitowe

  • 2008-04-28 00:04
  • 3 komentarze
  • 11035 odsłon
  • 6/6
Pole bitowe - w programowaniu oznaczenie pola w strukturze tak by jego typem była liczba całkowita o danej stałej liczbie bitów. Umożliwia to tworzenie pól w strukturze mniejszych niż jeden bajt i oszczędniejsze użycie pamięci.

źródło: Wikipedia

Spis treści

          1 Pojęcie pola bitowego w języku ANSI C
               1.1 Flagi bitowe
               1.2 Pole bitowe
          2 Pojęcie pola bitowego w języku C++

Pojęcie pola bitowego w języku ANSI C


Flagi bitowe


    Wyobraźmy sobie własną interpretację funkcji strtol, której zadaniem jest "wydobyć" liczbę z łańcucha tekstowego (przetworzyć liczbę z postaci łańcuchowej na numeryczną). Nie chciałbym się tutaj dogłębniej rozpisywać, jednak na potrzeby tego artykułu warto poznać choć częściową istotę działania tej funkcji.
    Przede wszystkim funkcja najpierw musi pominąć tzw. białe znaki w łańcuchu (spacje, tabulatory etc.), o ile takie istnieją. Następnym krokiem będzie sprawdzenie, czy liczba posiada znak, a także jakiego jest systemu liczbowego (podstawę systemu liczbowego podaje się poprzez argument base, jednak może się zdarzyć, że nie wiemy, jakiego systemu liczbowego będzie liczba. Wtedy funkcja musi to sprawdzić za nas). Na koniec pozostaje spisać wszystkie wartości, aż do napotkania końca łańcucha, lub symbolu nieoznaczającego wartości liczbowej.

    Zapewne spytasz szanowny czytelniku, dlaczego wspominam tutaj o funkcji strtol, kiedy artykuł powinien traktować o polach bitowych. Otóż nie bez powodu. Warto zauważyć jedną rzecz: między sprawdzeniem znaku liczby, a spisywaniem wartości oraz między sprawdzeniem, czy liczba nie przekracza zakresu, a zwróceniem gotowej liczby jest masa kodu.

A jednak musimy na końcu uwzględnić, że liczba była ujemna, dodając minus do wyniku, albo gdy przekraczała zakres, wówczas obcinając ją do maksymalnego dozwolonego rozmiaru. Użycie instrukcji warunkowych nie byłoby tu dobrym rozwiązaniem, bo i bez tego kod jest dość skomplikowany. Moglibyśmy użyć zmiennych typu bool znanych z C++, używając liczby całkowitej i przypisując jej wartość 1, oznaczającą prawdę, lub 0 oznaczającą fałsz.

Mogłoby to wyglądać następująco:

int main(int argc, char* argv[])
{
  long liczba = -887425254251524128424;   /* liczba typu long, o nieprawidłowej wartości */
  int liczba_ujemna = 0;
  int liczba_pozazakresem = 0;
 
  if ( liczba < 0)  /* sprawdzenie, czy liczba jest ujemna */
    liczba_ujemna = 1;
  else
    liczba_ujemna = 0;
 
  if ( liczba < LONG_MIN )  /* sprawdzenie, czy liczba nie przekracza zakresu */
    liczba_pozazakresem = 1;
  else
    liczba_pozazakresem = 0;
 
  if ( liczba_pozazakresem )  /* jeżeli liczba przekracza zakres, to jest obcinana do maksymalnej wartości */
    liczba = LONG_MIN;
 
  printf("Prawidłowa wartosc tej liczby %s to: %ld", (liczba_ujemna == 1 ? "ujemnej" : "dodatniej"), liczba);
  return 0;
}

    Jak widać, kod jest pozbawiony głębszego sensu, ale dobrze obrazuje, na czym polega problem. Mamy kilka warunków, które musimy sprawdzić, a następnie, na ich podstawie wygenerować jakiś wynik. Problem w tym, że między sprawdzeniem, a wykorzystaniem wyników sprawdzenia, występuje jeszcze jakiś kod, dlatego musimy wspomniane wyniki gdzieś przechować, zanim ich użyjemy.

Wykorzystanie wielu zmiennych, jak w poniższym przykładzie, nie jest dobrym rozwiązaniem. Dużo lepszym za to byłoby wykorzystanie jednej zmiennej, w której możnaby zmieścić wszystkie warunki. Taką możliwość dają nam tzw. flagi bitowe:
 
#define NIEOZNACZONA  01  /* flaga oznaczająca liczbę bez znaku */
#define POZAZAKRESEM 02  /* flaga oznaczająca liczbę poza zakresem */
#define UJEMNA   04  /* flaga oznaczająca liczbę ujemną */

albo, wykorzystując typ wyliczeniowy:

enum { NIEOZNACZONA = 01, POZAZAKRESEM = 02, UJEMNA = 04 };

    Flagi bitowe to nic innego, jak pewne stałe liczbowe. Ważne jest jednak to, że nie są to jakiekolwiek liczby. Każda z nich musi być potęgą dwójki. Nietrudno zauważyć, że jeśli w grę wchodzą potęgi dwójki, to wykonywane na tych liczbach operacje będą miały charakter operacji bitowych, co wiąże się z użyciem odpowiednich operatorów przesuwania, maskowania i dopełniania (zobacz artykuł o operatorach bitowych).
Pewne zwroty pojawiają się bardzo często, np.:

  flaga |= UJEMNA | POZAZAKRESEM;  /* ustawia bity UJEMNA i POZAZAKRESEM w zmiennej flaga */
  flaga &= ~( UJEMNA | POZAZAKRESEM );  /* kasuje te bity */
  if ( (flaga & (UJEMNA | POZAZAKRESEM)) == 0 ) { }  /* warunek jest prawdziwy, kiedy oba bity są skasowane */

Warto zauważyć, że w powyższym przykładzie używane są operatory binarne, a nie logiczne!
Więcej na temat operatorów znajdziesz we wspomnianym artykule.

    Cała idea polega na tym, że np. w pierwszym punkcie powyższego przykładu, pod zmienną flaga podstawiona zostanie suma logiczna flag UJEMNA oraz POZAZAKRESEM. Gdyby teraz przeprowadzić iloczyn logiczny (flaga & UJEMNA), otrzymamy wartość prawdziwą, jeżeli flaga UJEMNA została ustawiona w zmiennej flaga, albo wartość fałszywą, w przypadku, gdy flaga UJEMNA nie została ustawiona.
    Z pewnością brzmi to dość skomplikowanie, jednak sprawa jest banalna. Jeżeli nie wiesz, na czym polegają operacje bitowe, warto zaznajomić się z podstawami algebry Boole'a. Z pewnością nieco rozjaśni to pojęcia flag bitowych.

Oto poprzedni przykład, tym razem z użyciem flagi bitowej:

int main(int argc, char* argv[])
{
  long liczba = -887425254251524128424;   /* liczba typu long, o nieprawidłowej wartości */
  int flaga = 0;  
 
  if ( liczba < 0)  /* sprawdzenie, czy liczba jest ujemna */
    flaga |= UJEMNA;
 
  if ( liczba < LONG_MIN )  /* sprawdzenie, czy liczba nie przekracza zakresu */
    flaga |= POZAZAKRESEM;
 
  if ( wartosc & POZAZAKRESEM )  /* jeżeli liczba przekracza zakres, to jest obcinana do maksymalnej wartości */
    liczba = LONG_MIN;
 
  printf("Prawidłowa wartosc tej liczby %s to: %ld", ((wartosc & UJEMNA) ? "ujemnej" : "dodatniej"), liczba);
  return 0;
}

Być może nie widać dużej różnicy, ale użycie flag niesamowicie zwiększa czytelność oraz intuicyjność kodu. Z pewnością, kto raz nauczy się korzystać z flag bitowych, będzie z nich korzystał przy niemal każdej okazji.

Mimo, że, wspomniane flagi bitowe są bardzo chętnie stosowane, język C oferuje alternatywne rozwiązanie, chwilami stosowane nawet częściej.

Pole bitowe


Definicja pola bitowego został podana na samym wstępie. Samo pojęcie oznacza mniej więcej tyle, że zestaw symboli zdefiniowanych przez nas wcześniej, przy omawianiu flag bitowych za pomocą #define można zastąpić definicją struktury o trzech polach:

struct {
   unsigned int jest_nieoznaczona : 1;
   unsigned int jest_pozazakresem : 1;
   unsigned int jest_ujemna  : 1;
} flaga;

Powyższy przykład pokazuje definicję struktury o nazwie flaga, zawierającą trzy jednobitowe pola. Liczba występująca po dwukropku oznacza rozmiar pola w bitach. Pola zadeklarowano jako unsigned int, ponieważ bity są wartością bez znaku.

    Odwołanie do każdego pola jest identyczne z tym, w jaki sposób odwołuje się do elementu struktury: flaga.jest_ujemna, flaga.jest_pozazakresem itp. Pola zachowują się jak małe (w naszym przypadku 1-bitowe) zmienne całkowite i mogą występować w wyrażeniach arytmetycznych na równi z innymi obiektami całkowitymi. Zatem poprzednie przykłady można teraz napisać w sposób bardziej naturalny:

   flaga.jest_ujemna = flaga.jest_pozazakresem = 1;  /* ustawia bity */
   flaga. jest_ujemna = flaga.jest_pozazakresem = 0;  /* kasuje te bity */
   if (flaga.jest_ujemna == 0 && flaga.jest_pozazakresem == 0) {}  /* warunek sprawdza, czy oba bity są skasowane */

Warto pamiętać, że prawie wszystko, co wiąże się z polami bitowymi, zależy od implementacji. Trzeba mieć na uwadze przenośność programu, czyli jak dany program będzie zachowywał się na innej konfiguracji, niż ta, na której został stworzony.
   Elementy pola bitowego nie muszą mieć nazw. Elementy te (posiadające jedynie tylko dwukropek i rozmiar) są używane do "zapychania dziur" (nie wykorzystanych bitów między polami). Specjalny rozmiar 0 służy do wymuszenia przesunięcia kolejnych pól w granice następnego pola.

Uwaga!
W standardzie języka C zdefiniowano, że pola można deklarować jedynie z typem int. Ważne jest także określenie, że dana wartość nie posiada znaku, poprzez użycie kwalifikatora unsigned.
Pola nie są tablicami i nie mają adresów, zatem nie można stosować do nich operatora adresu &.


Na koniec przykład naszego programu z użyciem pola bitowego:

  struct stPoleBitowe {
     unsigned int jest_nieoznaczona : 1;
     unsigned int jest_pozazakresem : 1;
     unsigned int jest_ujemna  : 1;
  } flaga;
 
int main(int argc, char* argv[])
{
  long liczba = -887425254251524128424;   /* liczba typu long, o nieprawidłowej wartości */
 
  flaga.jest_ujemna = ( liczba < 0);  /* sprawdzenie, czy liczba jest ujemna */
  flaga.jest_pozazakresem = ( liczba < LONG_MIN );  /* sprawdzenie, czy liczba nie przekracza zakresu */
 
  if ( flaga.jest_pozazakresem )  /* jeżeli liczba przekracza zakres, to jest obcinana do maksymalnej wartości */
    liczba = LONG_MIN;
 
  printf("Prawidłowa wartosc tej liczby %s to: %ld", ( flaga.jest_ujemna ? "ujemnej" : "dodatniej"), liczba);
  return 0;
}

Można by rzec, że powyższy przykład nie różni się niczym od tego pierwszego, z użyciem wielu zwykłych zmiennych. Tutaj różnica miałaby jakoby polegać na tym, że te wiele zwykłych zmiennych spakowano do jednej struktury. Niestety nie do końca. Warto wziąć pod uwagę parę kwestii:
  • Nic nie stoi na przeszkodzie, by zdefiniować więcej zmiennych typu stPoleBitowe i używać ich w wielu funkcjach, albo nawet w obrębie jednej funkcji, jeśli to konieczne. Trochę trudniej byłoby wtedy, gdybyśmy używali wielu zwykłych zmiennych. Zresztą, chyba nie trzeba tłumaczyć wyższości stosowania struktur.
  • Dzięki temu, że rozmiar danego pola jest ograniczony np. do jednego bita, może on przyjmować jedynie określone wartości, np. 0/1. W przypadku użycia zwykłej zmiennej, wartość 0 będzie oznaczała fałsz, za to dowolna wartość dodatnia będzie oznaczała prawdę. Nietrudno sobie to zobrazować:
    #include <ctype.h>
      {...}
      int jest_cyfra = 0;
      jest_cyfra = isdigit('0');  /* funkcja isdigit() zwraca wartość większą od zera, jeśli podany znak jest cyfrą */
      if ( jest_cyfra ) {}   /* ten warunek jak najbardziej zadziała */
     
      if ( jest_cyfra == 1 ) {}  /* z kolei ten warunek niekoniecznie /* 
    Mimo, że zmienna jest_cyfra przyjmie wartość prawdziwą, wcale nie musi oznaczać, że jest ona równa 1!

  • Pole bitowe zajmuje określoną liczbę bitów (zazwyczaj jeden). Zmienna całkowita zajmuje miejsce 4 bajtów...

  • Reasumując użycie pola bitowego jest bardziej wskazane, niż użycie wielu zwykłych zmiennych logicznych, np. typu bool.

Pojęcie pola bitowego w języku C++


W języku C++ samo pojęcie pola bitowego się nie zmienia. Każde pole deklaruje się tak samo: podając nazwę (którą można zaniechać), następnie dwukropek oraz rozmiar w bitach. Różnicą jest natomiast chociażby to, że zamiast struktur korzysta się z klas.
Bardzo istotną zmiana w stosunku do języka C jest możliwość deklarowanie typu pola jako dowolną liczbę całkowitą, a więc char, short, int, long - w obu wariantach: signed albo unsigned, a także bool, a nawet typ wyliczeniowy enum.

  class liczba {
    char jest_nieoznaczona : 1;
    unsigned int mantysa :  4;
    unsigned int podstawa : 12;
    bool jest_ujemna : 1;
  };

3 komentarze

Future Knight 2009-06-08 02:42

Imho używanie makr tam gdzie jest to nie potrzebne utrudnia kodowanie. Po jaką cholerę w ogóle je stosować jeśli nie chcemy tylko sterować kompilacją? :)

ceer 2008-04-27 23:59

@Coldpeer: przepisałem cały artykuł od nowa, wszystkie przykłady są moje. Mam nadzieję, że teraz jest jak należy;)

Coldpeer 2008-04-27 18:59

<quote>fragment książki The C Programming Language, B.W. Kernighan D.M. Ritchie</quote>
No i jest ten mankament - czy to na pewno legalne?