Ceo broj je u računaru niz bitova (nula i jedinica). Bitovske operacije rade direktno nad tim bitovima i izuzetno su brze. Najvažnija primena na takmičenjima: podskup skupa od n ≤ 20 elemenata zapisuje se jednim brojem – maskom – pa se svi podskupovi obilaze običnom petljom.
| Operator | Značenje | Primer (5 = 101₂, 3 = 011₂) |
|---|---|---|
a & b | I – bit je 1 ako je 1 u oba | 5 & 3 = 001₂ = 1 |
a | b | ILI – bit je 1 ako je 1 u bar jednom | 5 | 3 = 111₂ = 7 |
a ^ b | isključivo ILI – bit je 1 ako su različiti | 5 ^ 3 = 110₂ = 6 |
~a | negacija svih bitova | |
a << k | pomeranje ulevo = množenje sa 2k | 5 << 1 = 1010₂ = 10 |
a >> k | pomeranje udesno = deljenje sa 2k | 5 >> 1 = 10₂ = 2 |
| Zadatak | Izraz |
|---|---|
| da li je bit i postavljen? | (x >> i) & 1 |
| postavi bit i | x | (1 << i) |
| obriši bit i | x & ~(1 << i) |
| promeni bit i | x ^ (1 << i) |
| da li je x paran? | (x & 1) == 0 |
| da li je x stepen dvojke? | x > 0 && (x & (x − 1)) == 0 |
| broj jedinica u zapisu | __builtin_popcount(x) |
#include <iostream>
using namespace std;
int main() {
int x;
cin >> x;
// binarni zapis broja x (8 bitova), od najvišeg ka najnižem
for (int i = 7; i >= 0; i--) cout << ((x >> i) & 1);
cout << endl;
cout << "jedinica: " << __builtin_popcount(x) << endl;
cout << "stepen dvojke: " << ((x > 0 && (x & (x - 1)) == 0) ? "da" : "ne") << endl;
return 0;
}
&, | i ^ imaju niži prioritet od ==. x & 1 == 0 znači x & (1 == 0)! Uvek piši zagrade: (x & 1) == 0. Za pomeranje preko 31 bita koristi 1LL << i.Elementima skupa dodelimo pozicije 0, 1, …, n − 1. Podskup zapisujemo brojem čiji je bit i jednak 1 ako je element i u podskupu. Na primer, za n = 3 maska 5 = 101₂ označava podskup {element 0, element 2}. Svi podskupovi su brojevi od 0 do 2n − 1:
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
long long S;
cin >> n >> S;
vector<long long> a(n);
for (auto &x : a) cin >> x;
int broj = 0;
for (int maska = 0; maska < (1 << n); maska++) { // svih 2^n podskupova
long long zbir = 0;
for (int i = 0; i < n; i++)
if ((maska >> i) & 1) zbir += a[i]; // element i je u podskupu
if (zbir == S) broj++;
}
cout << broj << endl;
return 0;
}
Složenost O(2n · n) – za n = 20 to je oko 2·107 koraka. Isto se može i rekurzijom, ali maske su kraće za pisanje i lako se kombinuju sa DP-om.
Za n = 40 je 240 ≈ 1012 podskupova – previše. Ali niz se može podeliti na dve polovine od po 20: za svaku izračunamo sve zbirove podskupova (2·220 ≈ 2·106), sortiramo jednu listu i za svaki zbir iz druge binarnom pretragom brojimo odgovarajuće. Složenost pada sa 2n na oko 2n/2 · n.
Važi x ^ x = 0 i x ^ 0 = x, a redosled nije bitan. Zato XOR svih elemenata niza u kome se svi brojevi javljaju po dva puta, osim jednog, daje upravo taj jedan broj – u O(n) i bez dodatne memorije.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int x = 0;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
x ^= a; // parovi se poništavaju
}
cout << x << endl;
return 0;
}
Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.
Ima n ≤ 20 predmeta sa težinom i vrednošću i ranac nosivosti W. Ispiši najveću ukupnu vrednost predmeta čija ukupna težina nije veća od W.
Ulaz: n W, zatim n parova težina vrednost.
4 7
3 4
4 5
2 3
5 811n ≤ 20 jabuka treba podeliti na dve grupe tako da razlika ukupnih težina bude što manja. Ispiši najmanju razliku.
5
3 2 7 4 11((m >> i) & 1) == 1.1 << n je int; za n ≥ 31 koristi 1LL << n.1. Koliko je 6 & 3?
2. Koji podskup skupa {a0, a1, a2} označava maska 6 (110₂)?
3. Koliko podskupova ima skup od 20 elemenata?