Avansat · Olimpiadă · Lecția 11
Operații pe biți și mulțimi codificate pe biți (bitmask), DP pe submulțimi
80 minolimpiadă / informatică intensiv
Înainte de lecția asta: X.8 Tablouri bidimensionale (matrice): declarare, parcurgere pe linii și coloane, XI.16 Programare dinamică: idee, recurențe, probleme clasice, OL.5 Programare dinamică de concurs: LCS, distanța de editare, LIS rapid, rucsac 1D
Ce vei ști după lecție
- Folosești operatorii pe biți (&, |, ^, ~, <<, >>) și verifici, setezi, ștergi, comuți un bit.
- Reprezinți o mulțime mică (n ≤ 20) ca un număr întreg (mască de biți).
- Enumeri toate submulțimile și submulțimile unei măști.
- Rezolvi o problemă de programare dinamică pe submulțimi (comis-voiajorul, n ≤ 15).
Olimpiadă și concursuriLecția 11 din 12 · mai este 1Urmează: OL.12 · Strategie la concurs și simulare de olimpiadăVezi toate lecțiile
Fișiere PDF și de lucru
- Lecția în PDF
versiunea de printat
1. Numerele ca șiruri de biți
Un int este reținut ca 32 de biți (0 sau 1). Operatorii pe biți lucrează bit cu bit, foarte rapid (o instrucțiune de procesor), iar un număr mic poate reprezenta o mulțime întreagă. Ambele idei apar des la olimpiadă.
| Operator | Nume | Exemplu cu 4 biți |
|---|---|---|
a & b |
ȘI pe biți | 1100 & 1010 = 1000 |
a | b |
SAU pe biți | 1100 | 1010 = 1110 |
a ^ b |
XOR (sau exclusiv) | 1100 ^ 1010 = 0110 |
~a |
negare (inversează toți biții) | ~0101 = …1010 |
a << k |
deplasare la stânga cu k biți | 0011 << 2 = 1100 (înmulțire cu 2ᵏ) |
a >> k |
deplasare la dreapta cu k biți | 1100 >> 2 = 0011 (împărțire întreagă la 2ᵏ) |
Biții se numerotează de la dreapta, începând cu 0: bitul 0 are valoarea 1, bitul 1 are valoarea 2, bitul 2 are 4 etc.
Cele patru operații pe un bit
| Ce vrei | Cum | Exemplu (x = 5 = 0101, i = 1) |
|---|---|---|
| verifici bitul i | (x >> i) & 1 |
(5 >> 1) & 1 = 0 |
| setezi bitul i la 1 | x | (1 << i) |
5 | 2 = 7 (0111) |
| ștergi bitul i (îl pui 0) | x & ~(1 << i) |
7 & ~2 = 5 |
| comuți bitul i | x ^ (1 << i) |
5 ^ 2 = 7, apoi 7 ^ 2 = 5 |
De ce așa?
De ce 1 << i? Numărul 1 << i are un singur bit de 1, la poziția i. Cu & îl „citim”, cu | îl „aprindem”, cu & ~ îl „stingem”, cu ^ îl „comutăm”. Este o „mască” care selectează un bit. Atenție la tip: pentru i ≥ 31 folosește 1LL << i, altfel depășești int.
Trucuri utile
| Ce | Cum |
|---|---|
| număr par / impar | x & 1 (1 = impar) |
| 2ᵏ | 1 << k |
| x este putere a lui 2? | x > 0 && (x & (x - 1)) == 0 |
| cel mai din dreapta bit de 1 | x & -x (lowbit, lecția co-07) |
| numărul de biți de 1 | __builtin_popcount(x) (sau __builtin_popcountll pentru long long) |
| a și b diferă? | a ^ b != 0 |
| interschimbă a și b fără variabilă | a ^= b; b ^= a; a ^= b; (curiozitate) |
#include <iostream>
using namespace std;
int main()
{
int n, x = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
x ^= a; // a ^ a = 0, a ^ 0 = a
}
cout << x; // numărul care apare o singură dată
return 0;
}De știut
Problema clasică: într-un șir, fiecare număr apare de două ori, în afară de unul. XOR-ul tuturor elementelor este exact acel număr, pentru că a ^ a = 0, a ^ 0 = a, iar XOR este comutativ. Memorie O(1), timp O(n).
2. Mulțimi pe biți (mască)
Dacă universul are cel mult ~20 de elemente numerotate 0 … n − 1, o submulțime se reprezintă printr-un număr în care bitul i este 1 dacă elementul i este în mulțime. Exemplu: mulțimea {0, 2, 3} este 1101₂ = 13.
| Operația pe mulțimi | Cu mască |
|---|---|
| mulțimea vidă | 0 |
universul {0, …, n − 1} |
(1 << n) - 1 |
i ∈ M? |
(M >> i) & 1 |
adaugă i în M |
M | (1 << i) |
scoate i din M |
M & ~(1 << i) |
| reuniune A ∪ B | A | B |
| intersecție A ∩ B | A & B |
| complementul lui A | ((1 << n) - 1) ^ A |
| numărul de elemente al lui A | __builtin_popcount(A) |
| A ⊆ B? | (A & B) == A |
Enumerarea tuturor submulțimilor
O mulțime cu n elemente are 2ⁿ submulțimi, codificate chiar de numerele 0 … 2ⁿ − 1.
#include <iostream>
using namespace std;
int main()
{
int n, S, v[20];
cin >> n >> S;
for (int i = 0; i < n; i++) cin >> v[i];
int numar = 0;
for (int masca = 0; masca < (1 << n); masca++) // fiecare submulțime
{
int suma = 0;
for (int i = 0; i < n; i++)
if (masca >> i & 1) suma += v[i]; // elementul i este în submulțime
if (suma == S) numar++;
}
cout << numar; // câte submulțimi au suma S
return 0;
}Pentru v = {3, 4, 2, 5} și S = 7: submulțimile cu suma 7 sunt {3, 4} (masca 0011) și {2, 5} (masca 1100): 2. Costul este O(2ⁿ · n): rezonabil pentru n ≤ 20 (≈ 2·10⁷).
Submulțimile unei submulțimi
Pentru a enumera submăștile lui M (toate submulțimile mulțimii M):
#include <iostream>
using namespace std;
int main()
{
int M;
cin >> M;
for (int s = M; ; s = (s - 1) & M) // următoarea submască, în ordine descrescătoare
{
cout << s << ' ';
if (s == 0) break; // 0 (mulțimea vidă) este ultima
}
return 0;
}Pentru M = 13 = 1101₂, submăștile sunt (zecimal) 13, 12, 9, 8, 5, 4, 1, 0: câte 2^(popcount(M)) = 8.
De ce așa?
De ce (s − 1) & M? Scăderea lui 1 din s transformă ultimul bit de 1 în 0 și toți biții de la dreapta lui în 1. Prin & M păstrăm doar biții care sunt în M. Rezultatul este următoarea submască mai mică. Cost: suma, peste toate măștile M, a numărului de submăști este 3ⁿ (fiecare element este: în afara lui M, în M dar nu în s, sau în s).
3. DP pe submulțimi: comis-voiajorul
Problemă. Un comis-voiajor pornește din orașul 0, trebuie să viziteze toate cele n orașe (n ≤ 15), exact o dată fiecare, și să revină în 0. Se dau distanțele d[i][j]. Care este lungimea minimă a turului?
Încercarea tuturor ordinilor costă n! (pentru n = 15 sunt 10¹²). Observație: pentru viitor contează doar mulțimea orașelor deja vizitate și orașul în care ne aflăm, nu și ordinea în care am ajuns.
Stare: dp[masca][i] = lungimea minimă a unui drum care pornește din 0, vizitează exact orașele din masca și se termină în orașul i (care e în masca).
Pornire: dp[1][0] = 0 (masca {0}, suntem în 0).
Tranziție: din (masca, i) mergem într-un oraș nevizitat j: dp[masca | (1 << j)][j] = min(…, dp[masca][i] + d[i][j]).
Răspuns: min peste i ≠ 0 din dp[toate][i] + d[i][0].
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<int>> d(n, vector<int>(n));
for (auto &rand : d)
for (auto &x : rand) cin >> x;
const int INF = 1000000000;
vector<vector<int>> dp(1 << n, vector<int>(n, INF));
dp[1][0] = 0; // am vizitat doar orașul 0
for (int masca = 1; masca < (1 << n); masca++)
for (int i = 0; i < n; i++)
{
if (!(masca >> i & 1) || dp[masca][i] == INF) continue;
for (int j = 0; j < n; j++)
if (!(masca >> j & 1)) // j nevizitat
{
int nou = masca | (1 << j);
dp[nou][j] = min(dp[nou][j], dp[masca][i] + d[i][j]);
}
}
int rezultat = INF;
for (int i = 1; i < n; i++)
rezultat = min(rezultat, dp[(1 << n) - 1][i] + d[i][0]); // revenirea în 0
cout << rezultat;
return 0;
}Pentru cele 4 orașe din test, tururile sunt: 0→1→3→2→0 = 10 + 25 + 30 + 15 = 80; 0→1→2→3→0 = 10 + 35 + 30 + 20 = 95; 0→2→1→3→0 = 15 + 35 + 25 + 20 = 95; (și celelalte trei sunt inversele lor, cu aceleași lungimi). Minimul este 80.
De ce așa?
De ce masca este suficientă? DP-ul are „proprietatea fără memorie”: costul continuării depinde doar de orașele rămase și de orașul curent, nu de cum am ajuns aici. Astfel, 15! ≈ 10¹² ordini se reduc la 2¹⁵ · 15 stări cu 15 tranziții fiecare: 2¹⁵ · 15 · 15 ≈ 7,4 · 10⁶ operații. De ce parcurgem măștile crescător? Tranziția merge de la o mască mai mică la una mai mare (masca | (1 << j) > masca), deci dp[masca] este final când îl folosim. Memorie: 2ⁿ · n valori; pentru n = 20 înseamnă 20 milioane de int: 80 MB, deci limita practică este n ≈ 20.
4. Când se folosesc măștile?
| Semnal în enunț | Tehnica |
|---|---|
| n ≤ 20 și „toate submulțimile” | enumerare cu mască, O(2ⁿ · n) |
| „vizitează toate”, „fiecare o dată”, n ≤ 20 | DP pe submulțimi |
| „asignează n sarcini la n persoane”, n ≤ 20 | DP pe submulțimi (masca = sarcinile deja asignate) |
memorie mică pentru mulți bool |
bitset sau mască |
| XOR, paritate, „apare o singură dată” | ^ |
| „numărul de biți de 1”, „puterea lui 2” | __builtin_popcount, x & (x − 1) |
5. Greșeli frecvente
| Greșeala | Ce se întâmplă | Corect |
|---|---|---|
1 << i cu i ≥ 31 |
depășire (comportament nedefinit) | 1LL << i |
masca >> i & 1 fără paranteze la combinări |
prioritate surprinzătoare: & are prioritate mai mică decât == |
pune paranteze: ((masca >> i) & 1) == 1 |
x << 1 când x e deja mare |
depășire | long long sau verifică limita |
~x pe unsigned vs int |
rezultat neașteptat | rămâi pe același tip |
dp[1 << n][n] pentru n = 25 |
depășește memoria | n ≤ 20; altfel altă tehnică |
uitarea stării inițiale dp[1][0] = 0 |
totul rămâne INF | inițializează starea de pornire |
INF + d în int |
depășire | INF = 10⁹ și verifică dp != INF |
enumerarea submăștilor cu s − 1 fără & M |
iese din submulțime | (s − 1) & M |
6. La olimpiadă
Măștile apar în două forme: (1) ca unealtă de viteză (xor, __builtin_popcount, bitset pentru memorie sau pentru a „paraleliza” 64 de operații în una) și (2) ca DP cu stare de submulțime, de obicei când constrângerea este n ≤ 15–20. Dacă vezi n ≤ 20, gândește-te la 2ⁿ.
7. Exersează pe hârtie
1. Calculează în binar (4 biți): 0110 & 0101, 0110 | 0101, 0110 ^ 0101.
2. Care este valoarea lui 1 << 5? Dar 100 >> 2?
3. Cum verifici dacă bitul 3 din x este 1? Cum îl pui pe 0?
4. Reprezintă mulțimea {1, 3, 4} (elemente de la 0) ca număr.
5. Câte biți de 1 are 29 (11101₂)? Este 64 putere a lui 2? Dar 96?
6. Pentru M = 6 = 110₂, enumeră toate submăștile (în ordinea s = (s − 1) & M).
7. Câte submulțimi are o mulțime cu 12 elemente? Cât costă enumerarea cu verificare O(n) pe fiecare?
8. Șirul 5 3 5 8 3 : care număr apare o singură dată? (XOR.)
9. Pentru TSP cu n = 4: câte stări (masca, i) există și câte sunt posibile?
10. De ce nu merge DP-ul pe submulțimi la n = 30?
8. Mini-grile
1. x & (x − 1) șterge:
a) cel mai din stânga bit de 1 b) cel mai din dreapta bit de 1 c) toți biții d) niciun bit
2. Câte submulțimi are o mulțime cu n elemente? a) n b) n² c) 2ⁿ d) n!
3. 1 << 3 este:
a) 3 b) 6 c) 8 d) 9
4. Operatorul care „comută” un bit este:
a) & b) | c) ^ d) ~
9. Mai departe (pentru cine vrea mai mult)
- Gray code:
i ^ (i >> 1)produce o ordine în care numerele consecutive diferă printr-un singur bit. - Meet in the middle: pentru n ≈ 40, împarți în două jumătăți de câte 20 și combini.
- SOS DP (sum over subsets): sume peste submulțimi în O(2ⁿ · n).
bitset: operații pe 64 de biți odată; util pentru accesibilitate în grafuri și pentru DP de tip rucsac.- XOR-ul în jocuri (Nim): o poziție este pierzătoare dacă XOR-ul grămezilor este 0.
Rezumat
- Operatori:
&,|,^,~,<<,>>. Bitul i:(x >> i) & 1; setare| (1 << i); ștergere& ~(1 << i); comutare^ (1 << i). - Mulțime mică = număr;
__builtin_popcountnumără elementele; enumerarea tuturor submulțimilor estefor (m = 0; m < (1 << n); m++). - Submăștile lui M:
s = (s − 1) & M. - DP pe submulțimi:
dp[masca][ultimul]; n ≤ 15–20; TSP în O(2ⁿ · n²). - XOR găsește numărul care apare o singură dată.
Probleme de lucru (concurs)
Probleme de pe infoarena, CSES, Kilonova sau pbinfo, în ordinea dificultății. Trimite soluțiile pe platformă și bifează ce ai terminat.
- ușoară
ApplesCSES
împarte merele în două grupe cât mai echilibrat: enumerare de submulțimi
https://cses.fi/problemset/task/1623
- ușoară
- dificilă
DP pe submulțimi: numărarea drumurilor hamiltoniene
https://cses.fi/problemset/task/1690
- dificilă
Temă (concurs)
Mai grele: încearcă-le după ce le-ai terminat pe cele de mai sus.
- medie
Counting BitsCSES
biții de 1 de la 1 la n: număr pe fiecare poziție
https://cses.fi/problemset/task/1146
- dificilă
Citește și exersează în plus
- CP-Algorithms — Bit manipulation · cp-algorithms.com
trucuri cu biți (engleză)
https://cp-algorithms.com/algebra/bit-manipulation.html
- USACO Guide — Bitmasks · usaco.guide
măști și DP pe măști, probleme graduate (engleză)
https://usaco.guide/gold/bitmasks
- cppreference — std::bitset · en.cppreference.com
biți în loc de bool, pentru memorie mică (engleză)
https://en.cppreference.com/w/cpp/utility/bitset
Te-ai blocat la lecția asta?
Scrie-mi ce nu iese și vedem împreună de unde se blochează.
Răspunsuri
Exersează pe hârtie
1. 0110 & 0101 = 0100; 0110 | 0101 = 0111; 0110 ^ 0101 = 0011.
2. 1 << 5 = 32; 100 >> 2 = 25.
3. Verificare: (x >> 3) & 1. Ștergere: x & ~(1 << 3).
4. {1, 3, 4}: biții 1, 3, 4: 2 + 8 + 16 = 26 (11010₂).
5. 29 = 16 + 8 + 4 + 1: 4 biți de 1. 64 este putere a lui 2 (64 & 63 = 0); 96 = 64 + 32 nu este (96 & 95 = 64).
6. M = 110₂: s = 6, apoi (6 − 1) & 6 = 5 & 6 = 4, apoi (4 − 1) & 6 = 3 & 6 = 2, apoi (2 − 1) & 6 = 1 & 6 = 0. Submăștile: 6, 4, 2, 0.
7. 2¹² = 4096 submulțimi; cu verificare O(12) pe fiecare: 4096 · 12 ≈ 49 000 operații.
8. 5 ^ 3 ^ 5 ^ 8 ^ 3 = 8.
9. În total 2⁴ · 4 = 64 de perechi (masca, i). Se folosesc doar cele cu orașul 0 în mască și i în mască: starea de pornire este dp[1][0], iar pentru i ≠ 0 masca are cel puțin biții 0 și i, deci 2² = 4 măști pentru fiecare dintre cele 3 orașe, adică 12 stări, plus starea de pornire.
10. 2³⁰ ≈ 10⁹ măști, ori 30 de orașe: 3 · 10¹⁰ valori în memorie: imposibil.
Mini-grile
1. b) cel mai din dreapta bit de 1. 2. c) 2ⁿ. 3. c) 8. 4. c) ^.