O.1 — Flagi bitowe i manipulacja bitami poprzez std::bitset

W nowoczesnych architekturach komputerów najmniejszą adresowalną jednostką pamięci jest bajt. Ponieważ wszystkie obiekty muszą mieć unikalne adresy pamięci, oznacza to, że obiekty muszą mieć rozmiar co najmniej jednego bajta. W przypadku większości typów zmiennych jest to w porządku. Jednak w przypadku wartości logicznych jest to trochę marnotrawstwo (gra słów zamierzona). Typy logiczne mają tylko dwa stany: prawda (1) lub fałsz (0). Ten zestaw stanów wymaga przechowywania tylko jednego bitu. Jeśli jednak zmienna musi mieć co najmniej bajt, a bajt ma 8 bitów, oznacza to, że wartość logiczna wykorzystuje 1 bit, a pozostałych 7 pozostawia nieużywanych.

W większości przypadków jest to w porządku — zwykle nie mamy tak dużego obciążenia pamięcią, że musimy przejmować się 7 zmarnowanymi bitami (lepiej jest zoptymalizować pod kątem zrozumiałości i łatwości konserwacji). Jednakże w niektórych przypadkach wymagających dużej ilości pamięci przydatne może być „spakowanie” 8 indywidualnych wartości logicznych w jeden bajt w celu zwiększenia wydajności pamięci.

Wykonywanie tych czynności wymaga możliwości manipulowania obiektami na poziomie bitów. Na szczęście C++ daje nam narzędzia, które pozwalają nam to zrobić. Modyfikowanie poszczególnych bitów w obiekcie nazywa się manipulacją bitami.

Flagi bitowe

Do tego momentu używaliśmy zmiennych do przechowywania pojedynczych wartości:

int foo { 5 }; // assign foo the value 5 (probably uses 32 bits of storage)
std::cout << foo; // print the value 5

Jednak zamiast postrzegać obiekty jako posiadające pojedynczą wartość, możemy zamiast tego traktować każdy bit w obiekcie jako niezależną wartość logiczną. Kiedy pojedyncze bity obiektu są używane jako wartości logiczne, bity te nazywane są flagami bitowymi.

Aby zdefiniować zestaw flag bitowych, zazwyczaj używamy liczby całkowitej bez znaku o odpowiednim rozmiarze (8 bitów, 16 bitów, 32 bity itp.… w zależności od tego, ile mamy flag) lub std::bitset.

#include <bitset> // for std::bitset

std::bitset<8> mybitset {}; // 8 bits in size means room for 8 flags

W tej lekcji pokażemy, jak w prosty sposób manipulować bitami za pomocą std::bitset. W następnej serii lekcji odkryjemy, jak to zrobić w trudniejszy, ale uniwersalny sposób.

Numeracja bitów i pozycje bitów

Biorąc pod uwagę sekwencję bitów, zazwyczaj numerujemy bity od prawej do lewej, zaczynając od 0 (nie 1). Każda liczba oznacza pozycję bitu.

76543210  Bit position
00000101  Bit sequence

Biorąc pod uwagę sekwencję bitów 0000 0101, bity znajdujące się na pozycjach 0 i 2 mają wartość 1, a pozostałe bity mają wartość 0.

Manipulacja bitami za pomocą std::bitset

W lekcji 5.3 — Systemy liczbowe (dziesiętny, binarny, szesnastkowy i ósemkowy) pokazaliśmy już, jak używać std::bitset do drukowania wartości binarnych. Jednak nie jest to jedyna przydatna rzecz, jaką std::bitset można zrobić.

std::bitset zapewnia 4 kluczowe funkcje składowe, które są przydatne do manipulacji bitami:

• test() pozwala nam sprawdzić, czy bit ma wartość 0 czy 1.
• set() pozwala nam włączyć nieco (to nic nie da, jeśli bit jest już włączony).
• reset() pozwala nam wyłączyć bit (nie zrobi to nic, jeśli bit jest już włączony) off).
• flip() pozwala nam zamienić wartość bitu z 0 na 1 lub odwrotnie.

Każda z tych funkcji przyjmuje jako jedyny argument położenie bitu, na którym chcemy wykonać operację.

Oto przykład:

#include <bitset>
#include <iostream>

int main()
{
    std::bitset<8> bits{ 0b0000'0101 }; // we need 8 bits, start with bit pattern 0000 0101
    bits.set(3);   // set bit position 3 to 1 (now we have 0000 1101)
    bits.flip(4);  // flip bit 4 (now we have 0001 1101)
    bits.reset(4); // set bit 4 back to 0 (now we have 0000 1101)

    std::cout << "All the bits: " << bits<< '\n';
    std::cout << "Bit 3 has value: " << bits.test(3) << '\n';
    std::cout << "Bit 4 has value: " << bits.test(4) << '\n';

    return 0;
}

Wypisuje:

All the bits: 00001101
Bit 3 has value: 1
Bit 4 has value: 0

Nadanie nazw bitom może pomóc w udoskonaleniu naszego kodu czytelne:

#include <bitset>
#include <iostream>

int main()
{
    [[maybe_unused]] constexpr int  isHungry   { 0 };
    [[maybe_unused]] constexpr int  isSad      { 1 };
    [[maybe_unused]] constexpr int  isMad      { 2 };
    [[maybe_unused]] constexpr int  isHappy    { 3 };
    [[maybe_unused]] constexpr int  isLaughing { 4 };
    [[maybe_unused]] constexpr int  isAsleep   { 5 };
    [[maybe_unused]] constexpr int  isDead     { 6 };
    [[maybe_unused]] constexpr int  isCrying   { 7 };

    std::bitset<8> me{ 0b0000'0101 }; // we need 8 bits, start with bit pattern 0000 0101
    me.set(isHappy);      // set bit position 3 to 1 (now we have 0000 1101)
    me.flip(isLaughing);  // flip bit 4 (now we have 0001 1101)
    me.reset(isLaughing); // set bit 4 back to 0 (now we have 0000 1101)

    std::cout << "All the bits: " << me << '\n';
    std::cout << "I am happy: " << me.test(isHappy) << '\n';
    std::cout << "I am laughing: " << me.test(isLaughing) << '\n';

    return 0;
}

A co, jeśli chcemy uzyskać lub ustawić wiele bitów na raz

std::bitset nie da się tego zrobić łatwe. Aby to zrobić lub jeśli chcemy używać flag bitowych typu unsigned Integer zamiast std::bitset, musimy zwrócić się do bardziej tradycyjnych metod. Omówimy je w ciągu następnych kilku lekcji.

Rozmiar std::bitset

Jedną potencjalną niespodzianką jest to, że std::bitset jest zoptymalizowany pod kątem szybkości, a nie oszczędności pamięci. Rozmiar a std::bitset to zazwyczaj liczba bajtów potrzebnych do przechowywania bitów, zaokrąglona w górę do najbliższego sizeof(size_t), czyli 4 bajty na maszynach 32-bitowych i 8 bajtów na maszynach 64-bitowych.

Zatem a std::bitset<8> będzie zazwyczaj używać 4 lub 8 bajtów pamięci, chociaż technicznie rzecz biorąc, potrzebuje tylko 1 bajtu do przechowywania 8 bitów. Dlatego std::bitset jest najbardziej przydatna, gdy zależy nam na wygodzie, a nie na oszczędności pamięci.

Wykonywanie zapytań std::bitset

Istnieje kilka innych funkcji składowych, które są często przydatne:

• size() zwraca liczbę bitów w zestawie bitów.
• count() zwraca liczbę bitów w zestawie bitów, które są ustawione na true.
• all() zwraca wartość logiczną wskazującą, czy wszystkie bity są ustawione na true.
• any() zwraca wartość logiczną wskazującą, czy jakiekolwiek bity są ustawione na true.
• none() zwraca wartość logiczną wskazującą, czy żadne bity nie są ustawione na true.

#include <bitset>
#include <iostream>

int main()
{
    std::bitset<8> bits{ 0b0000'1101 };
    std::cout << bits.size() << " bits are in the bitset\n";
    std::cout << bits.count() << " bits are set to true\n";

    std::cout << std::boolalpha;
    std::cout << "All bits are true: " << bits.all() << '\n';
    std::cout << "Some bits are true: " << bits.any() << '\n';
    std::cout << "No bits are true: " << bits.none() << '\n';
    
    return 0;
}

Wypisuje:

8 bits are in the bitset
3 bits are set to true
All bits are true: false
Some bits are true: true
No bits are true: false