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ć.
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.
// 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++;
#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.
#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;
}
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.
#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
#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";
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.
#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;
}
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ń.
| Zapis | Co robi | Uwaga |
|---|---|---|
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.
count() da liczbę różnych.Pokaż rozwiązanie
#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;
}
Pokaż rozwiązanie
#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;
}
bitset<32> b(s);. Potem wystarczy b.flip() bez argumentu — odwraca wszystko naraz.Pokaż rozwiązanie
#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;
}
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ń.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
#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;
}
n (gdzie n może sięgać miliona), a potem dziesięć największych z nich.main, z rozmiarem miliona — tego nie da się zrobić wewnątrz funkcji.Pokaż rozwiązanie
#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;
}
n liczb dodatnich (każda do 100, n do 100). Ile różnych sum można uzyskać, wybierając dowolny podzbiór tych liczb?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
#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
bitset<1000000> jest w porządku, bitset<n> ze zmienną n — nie. Deklaruj z zapasem albo weź vector<bool>.cout << b pokazuje bit numer 0 na samym końcu napisu. Przy odczycie b[0] numeracja jest już zwyczajna.bool zużywa bajt na wartość, bitset — jeden bit. Przy dziesięciu milionach to różnica 10 MB kontra 1,25 MB.b.count() policzy jedynki natychmiast, bez przechodzenia bit po bicie. Ręczna pętla robiłaby to samo wielokrotnie wolniej.main, tak jak duże tablice. W środku funkcji program może się wysypać przy starcie.set, gdy wartości są rozrzucone albo nieznane z góry.