C++ · Kontenery · bitset

Bitset — tablica zer i jedynek

Gdy potrzebujesz tylko odpowiedzi „tak albo nie” dla miliona rzeczy, tablica bool jest rozrzutna. Bitset robi to samo, zajmując osiem razy mniej miejsca.

Filmy z OKI

Wolisz obejrzeć?

Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Poniżej 2 odcinki o tym temacie — dobre uzupełnienie, jeśli wolisz obejrzeć niż przeczytać.

Materiały Olimpijskiego Koła Informatycznego — kanał zewnętrzny. Kliknięcie odtwarza film tutaj, bez opuszczania strony.

Po co komu bitset

Czasem dla każdej liczby potrzebujesz zapamiętać jedną rzecz: „czy już była?”, „czy jest pierwsza?”, „czy pole jest zajęte?”. Do tego wystarcza jeden bit — zero albo jeden.

Problem w tym, że bool w tablicy zajmuje cały bajt, czyli osiem bitów — siedem z nich się marnuje. Przy dziesięciu milionach pozycji to różnica między 10 MB a 1,25 MB. bitset upakowuje bity ciasno, bez marnowania.

tablica_bool.cpp
// 10 milionow pozycji = okolo 10 MB
bool jest[10000000];

jest[42] = true;
jest[100] = true;

if (jest[42]) cout << "42 zaznaczone\n";

// liczenie zaznaczonych - petla
int ile = 0;
for (int i = 0; i < 10000000; i++)
    if (jest[i]) ile++;
bitset.cpp
#include <bitset>

// te same 10 milionow = okolo 1,25 MB
bitset<10000000> jest;

jest[42] = 1;
jest[100] = 1;

if (jest[42]) cout << "42 zaznaczone\n";

// liczenie zaznaczonych - jedno wywolanie
int ile = jest.count();

Druga zaleta jest ciekawsza od oszczędności pamięci: bitset ma gotowe operacje na całości. count() liczy jedynki bez pisania pętli, a znaki & i | porównują dwa bitsety naraz.

📦

bitset<N> b;

Ciąg N bitów, wszystkie na start zerowe. N musi być stałą liczbą, nie zmienną.

✅

b[i] = 1

Ustawia bit numer i. Czytasz tak samo: if (b[i]).

🔢

b.count()

Ile jedynek jest w środku — bez pętli, natychmiast.

🔄

b.flip(i)

Odwraca bit: zero na jeden, jeden na zero.

❓

b.any() / b.none()

Czy jest choć jedna jedynka / czy wszystko jest zerem.

🌍

duże bitsety

Przy milionach bitów deklaruj poza main, tak jak duże tablice.

podstawy.cpp
#include <iostream>
#include <bitset>
using namespace std;

int main() {
    bitset<16> b;              // 16 bitow, same zera

    b[0] = 1;
    b[3] = 1;
    b[7] = 1;

    cout << b << "\n";         // wypisuje sie caly
    cout << b.count() << "\n"; // ile jedynek
    cout << b.any() << "\n";   // czy cokolwiek ustawione

    b.flip(3);                 // odwracamy bit 3
    cout << b.count() << "\n";

    b.reset();                 // czyscimy wszystko
    cout << b.none() << "\n";  // czy same zera

    return 0;
}
▶ Wyjście programu
0000000010001001 3 1 2 1

Uwaga na kolejność przy wypisywaniu: bitset pokazuje bity od najwyższego numeru do najniższego, czyli od prawej do lewej. Bit numer 0 jest na samym końcu napisu. To myli przy pierwszym spotkaniu, ale przy odczycie przez b[i] numeracja jest już zwyczajna.

Dwa bitsety naraz

Bitsety można porównywać i łączyć w całości, jednym znakiem. To ta sama logika, którą znasz z warunków if — tylko wykonywana na wszystkich bitach jednocześnie.

laczenie.cpp
#include <bitset>

bitset<8> a("00001111");
bitset<8> b("00111100");

cout << (a & b) << "\n";   // ORAZ - wspolne
cout << (a | b) << "\n";   // LUB  - razem
cout << (a ^ b) << "\n";   // tylko w jednym
cout << (~a)    << "\n";   // odwrocone
▶ Wyjście programu
00001100 00111111 00110011 11110000
zastosowanie.cpp
#include <bitset>

// kto zna ktory jezyk (bit = jezyk)
bitset<5> ala("10110");
bitset<5> bartek("00111");

bitset<5> wspolne = ala & bartek;

cout << "Wspolnych: " << wspolne.count() << "\n";
cout << "Razem:     " << (ala | bartek).count() << "\n";
▶ Wyjście programu
Wspolnych: 2 Razem: 4

Prawy przykład pokazuje typowe zastosowanie: bitset jako zbiór cech. Każdy bit odpowiada jednej rzeczy (języku, przedmiotowi, zainteresowaniu), a operacje & i | odpowiadają na pytania „co mamy wspólnego?” i „co mamy razem?” — bez żadnej pętli.

Największa praktyczna zaleta: te operacje wykonują się na wielu bitach naraz, więc porównanie dwóch bitsetów po milion bitów jest wielokrotnie szybsze niż pętla po milionie elementów tablicy.

Sito Eratostenesa

Najbardziej znane użycie bitseta to znajdowanie liczb pierwszych. Pomysł jest bardzo stary i bardzo prosty: wykreślaj wielokrotności. Zaczynasz od dwójki, wykreślasz 4, 6, 8… potem bierzesz trójkę i wykreślasz 6, 9, 12… i tak dalej. Co zostanie niewykreślone, jest pierwsze.

sito.cpp
#include <iostream>
#include <bitset>
using namespace std;

const int N = 1000000;
bitset<N + 1> zlozona;          // globalnie, bo duze

int main() {
    zlozona[0] = 1;             // 0 nie jest pierwsza
    zlozona[1] = 1;             // 1 tez nie

    for (int i = 2; i * i <= N; i++) {
        if (!zlozona[i]) {
            // wykreslamy wielokrotnosci i
            for (int j = i * i; j <= N; j += i) {
                zlozona[j] = 1;
            }
        }
    }

    // ile liczb pierwszych do miliona
    int ile = 0;
    for (int i = 2; i <= N; i++) {
        if (!zlozona[i]) ile++;
    }

    cout << "Pierwszych do miliona: " << ile;
    return 0;
}
▶ Wyjście programu
Pierwszych do miliona: 78498

Dwa szczegóły warte uwagi. Pętla zewnętrzna idzie tylko do pierwiastka — bo gdyby liczba miała dzielnik większy od pierwiastka, to miałaby też mniejszy, a ten już byśmy wykreślili. Pętla wewnętrzna zaczyna od i * i, bo wszystko mniejsze wykreśliły już mniejsze liczby.

I najważniejsze ograniczenie bitseta: rozmiar musi być znany podczas pisania programu. Nie napiszesz bitset<n> z n wczytanym od użytkownika. Deklarujesz z zapasem — tak samo jak zwykłe tablice. Gdy rozmiar naprawdę zależy od danych, sięgnij po vector<bool>.

Wszystko, co robi się z bitsetem

Dwanaście zapisów — w praktyce cały bitset. Pierwsze sześć wystarcza do zdecydowanej większości zadań.

ZapisCo robiUwaga
bitset<N> b; Ciąg N bitów, same zera. N musi być stałą
bitset<N> b("1011"); Bitset z napisu. Od prawej do lewej
b[i] = 1 Ustawia bit i. To samo co b.set(i)
b[i] Odczytuje bit i. Zwraca 0 albo 1
b.count() Ile jedynek. Natychmiast, bez pętli
b.reset() Zeruje wszystko. b.reset(i) zeruje jeden bit
b.set() Ustawia wszystkie bity na jedynki. b.set(i) ustawia jeden
b.flip(i) Odwraca bit. Bez argumentu — odwraca wszystkie
b.any() / b.none() Czy jest choć jedna jedynka / same zera. —
a & b Bity wspólne dla obu. Część wspólna zbiorów
a | b Bity z któregokolwiek. Suma zbiorów
a ^ b Bity z dokładnie jednego. Różnica symetryczna

Trzy ostatnie wiersze to powód, dla którego bitset bywa szybszy od wszystkiego innego. Porównanie dwóch bitsetów po milion bitów wykonuje się na wielu bitach naraz, podczas gdy pętla po tablicy musiałaby przejść element po elemencie.

Sprawdź się na zadaniach

Sześć zadań od najprostszego. Wszystkie opierają się na tym samym pomyśle: jedna informacja „tak albo nie” na pozycję. Najpierw spróbuj sam.

Łatwe Zaznacz i policz
Wczytuj liczby z zakresu 0–99 aż do końca danych. Wypisz, ile było wśród nich różnych wartości oraz które konkretnie (rosnąco).
Jak to ugryźć: Bitset stu bitów, a w nim jedynka na pozycji każdej wczytanej liczby. Powtórzenia same się zlewają. count() da liczbę różnych.
Pokaż rozwiązanie
zaznacz.cpp
#include <iostream>
#include <bitset>
using namespace std;

int main() {
    bitset<100> b;

    int x;
    while (cin >> x) {
        b[x] = 1;
    }

    cout << "Roznych: " << b.count() << "\n";

    for (int i = 0; i < 100; i++) {
        if (b[i]) cout << i << " ";
    }

    return 0;
}
Łatwe Brakujące liczby
Wczytaj liczby z zakresu 1–100 i wypisz te z tego zakresu, których nie było wśród danych.
Jak to ugryźć: Zaznacz obecne, a potem przejdź od 1 do 100 i wypisz te pozycje, na których bit jest zerem.
Pokaż rozwiązanie
brakujace.cpp
#include <iostream>
#include <bitset>
using namespace std;

int main() {
    bitset<101> b;

    int x;
    while (cin >> x) b[x] = 1;

    for (int i = 1; i <= 100; i++) {
        if (!b[i]) cout << i << " ";
    }

    return 0;
}
Łatwe Odwróć wszystkie bity
Wczytaj napis złożony z zer i jedynek (do 32 znaków). Wypisz go odwrócony (zera na jedynki i odwrotnie) oraz liczbę jedynek przed i po.
Jak to ugryźć: Bitset da się utworzyć wprost z napisu: bitset<32> b(s);. Potem wystarczy b.flip() bez argumentu — odwraca wszystko naraz.
Pokaż rozwiązanie
odwroc.cpp
#include <iostream>
#include <bitset>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;

    bitset<32> b(s);

    cout << "Przed: " << b.count() << "\n";
    b.flip();
    cout << "Po:    " << b.count() << "\n";
    cout << b;

    return 0;
}
Średnie Wspólne zainteresowania
Każda z n osób ma listę zainteresowań opisaną napisem zer i jedynek o długości 20. Znajdź parę osób, które mają najwięcej wspólnych zainteresowań.
Jak to ugryźć: Wspólne zainteresowania dwóch osób to a & b, a ich liczba to (a & b).count(). Sprawdź każdą parę — przy kilkuset osobach to w zupełności wystarczy.
Pokaż rozwiązanie
zainteresowania.cpp
#include <iostream>
#include <bitset>
#include <vector>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<bitset<20>> osoby(n);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        osoby[i] = bitset<20>(s);
    }

    int najlepsze = -1, a = 0, b = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int wspolne = (osoby[i] & osoby[j]).count();
            if (wspolne > najlepsze) {
                najlepsze = wspolne;
                a = i; b = j;
            }
        }
    }

    cout << "Osoby " << a << " i " << b
         << ": " << najlepsze << " wspolnych";

    return 0;
}
Średnie Liczby pierwsze do miliona
Wypisz, ile jest liczb pierwszych mniejszych lub równych n (gdzie n może sięgać miliona), a potem dziesięć największych z nich.
Jak to ugryźć: Sito Eratostenesa z sekcji trzeciej. Bitset deklaruj przed main, z rozmiarem miliona — tego nie da się zrobić wewnątrz funkcji.
Pokaż rozwiązanie
sito.cpp
#include <iostream>
#include <bitset>
#include <vector>
using namespace std;

const int MAX = 1000001;
bitset<MAX> zlozona;

int main() {
    int n;
    cin >> n;

    zlozona[0] = zlozona[1] = 1;

    for (int i = 2; i * i <= n; i++) {
        if (!zlozona[i]) {
            for (int j = i * i; j <= n; j += i) zlozona[j] = 1;
        }
    }

    vector<int> pierwsze;
    for (int i = 2; i <= n; i++) {
        if (!zlozona[i]) pierwsze.push_back(i);
    }

    cout << "Pierwszych: " << pierwsze.size() << "\n";

    int od = max(0, (int)pierwsze.size() - 10);
    for (int i = od; i < pierwsze.size(); i++) {
        cout << pierwsze[i] << " ";
    }

    return 0;
}
Trudne Ile różnych sum
Masz n liczb dodatnich (każda do 100, n do 100). Ile różnych sum można uzyskać, wybierając dowolny podzbiór tych liczb?
Jak to ugryźć: Sprawdzanie wszystkich podzbiorów odpada — jest ich astronomicznie wiele. Sztuczka: bitset, w którym bit s znaczy „sumę s da się uzyskać”. Na start ustaw bit 0. Dla każdej nowej liczby x wszystkie dotychczasowe sumy powiększają się o x — a to jest po prostu przesunięcie całego bitseta o x pozycji.
Pokaż rozwiązanie
sumy.cpp
#include <iostream>
#include <bitset>
using namespace std;

const int MAX = 10001;

int main() {
    int n;
    cin >> n;

    bitset<MAX> mozliwe;
    mozliwe[0] = 1;            // sume 0 zawsze da sie uzyskac

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        // kazda dotychczasowa suma + x
        mozliwe |= (mozliwe << x);
    }

    cout << mozliwe.count();
    return 0;
}

Częste błędy i dobre praktyki

📏
Rozmiar musi być stały
bitset<1000000> jest w porządku, bitset<n> ze zmienną n — nie. Deklaruj z zapasem albo weź vector<bool>.
↔️
Bity wypisują się od prawej
cout << b pokazuje bit numer 0 na samym końcu napisu. Przy odczycie b[0] numeracja jest już zwyczajna.
💾
Osiem razy mniej pamięci
Tablica bool zużywa bajt na wartość, bitset — jeden bit. Przy dziesięciu milionach to różnica 10 MB kontra 1,25 MB.
⚡
count() bez pętli
b.count() policzy jedynki natychmiast, bez przechodzenia bit po bicie. Ręczna pętla robiłaby to samo wielokrotnie wolniej.
🌍
Duże bitsety poza main
Bitset na milion bitów deklaruj przed main, tak jak duże tablice. W środku funkcji program może się wysypać przy starcie.
🤔
Kiedy bitset, a kiedy set?
Bitset, gdy pozycje są małymi liczbami i jest ich dużo. set, gdy wartości są rozrzucone albo nieznane z góry.

Gotowy na więcej?

Dołącz do T-Olimpians i trenuj z doświadczonymi mentorami. Zbuduj bazę, która prowadzi do finałów OI.