Tehete AND, OR ja XOR tegemiseks kirjutame need arvud kahendsüsteemis kohakuti (nagu arve "kirjalikult" liites). Vastuses iga bitt sõltub temaga samas veerus olevatest bittidest järgmiselt:
a & b
, a | b
, a ^ b
.
Teeme need tehted läbi näiteks arvude $21 = 10101_2$ ja $12 = 1100_2$ peal: $$ \begin{array}{ccccccc} &&1&0&1&0&1\\ \& && &1&1&0&0\\ \hline &&0&0&1&0&0 \end{array} \qquad \begin{array}{ccccccc} &&1&0&1&0&1\\ \mid && &1&1&0&0\\ \hline &&1&1&1&0&1 \end{array} \qquad \begin{array}{ccccccc} &&1&0&1&0&1\\ \oplus && &1&1&0&0\\ \hline &&1&1&0&0&1 \end{array} $$ Saame, et $21 \& 12 = 100_2 = 4$, $21 \mid 12 = 11101_2 = 29$, $21 \oplus 12 = 11001_2 = 25$.
Olgu antud arvud $a$ ja $k$. Siis $a \ll k$ on arv $a$, kuhu on kahendsüsteemis $k$
nulli juurde pandud. Näiteks $13 \ll 2 = 1101_2 \ll 2 = 110100$. Programmeerimiskeeltes
kasutatakse tähistust a << k
. Kehtib
$a \ll k = a \cdot 2^k$. Seetõttu kirjutatakse mõnikord programmides $2^k$ arvutamiseks
1 << k
.
Olgu antud arvud $a$ ja $k$, siis $a \gg k$ on arv $a$, kust on kahendsüsteemis $k$
parempoolset bitti "ära lõigatud". Näiteks $109 \gg 3 = 1101101_2 \gg 3 = 1101$.
Programmeerimiskeeltes kasutatakse tähistust a >> k
.
Oletame, et on antud arv $a$ ja vaja kontrollida, kas tema $k$-s bitt (paremalt) on 1. Selleks piisab kontrollida, kas $a \& 1 \ll k = a \& (1 \ll k)$ on nullist erinev.
Olgu $a$ ja $b$ arvud. Kui $a \& b = b$ ehk $a \mid b = a$, siis ütleme, et $b$ on $a$ alamhulk ja tähistame $b \subseteq a$. Teisisõnu on $b$ arvu $a$ alamhulk, kui $b$ kahendesituses on ühed vaid seal, kus arvul $a$.
Millest selline mõiste? Sageli kasutatakse bitimaske/kahendarve selleks, et tähistada naturaalarvude hulga lõplikke alamhulki. Arvule $a$ vastab hulk $A$, kus $n \in A$ parajasti siis, kui $a$ $n$-s kahendkoht (paremalt) on 1. Näiteks $197 = 11000101_2$ tähistab hulka $\{0, 2, 6, 7\}$. Niisuguses käsitluses vastab tehe AND ühisosa võtmisele, tehe OR ühendi võtmisele ja alamhulga mõiste alamhulga mõistele.
Olgu meil antud massiiv $A$ pikkusega $n = 2^k$. Vaja on leida ja välja trükkida massiiv $B$, pikkusega samuti $2^k$, kus $$B[i] = \sum_{j \subseteq i} A[j].$$ Nõutav keerukus on $O(kn) = O(k 2^k) = O(n \log n)$. Seda ülesannet (ja selle lahendusvõtet) nimetatakse mõnikord SOS-DP (sum-over-subsets DP, summa-üle-alamhulkade DP).
See on üks klassikalisemaid võistlusprogrammeerimise ülesandeid.
B = A for (int i = 1; i < n; i++) { B[i] += B[i - 1]; } print(B)
B = A for (int i = 0; i < n; i++) { for (int j = 1; j < n; j++) { B[i][j] += B[i][j - 1]; } } for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { B[i][j] += B[i - 1][j]; } } print(B)
Veendume selle korrektsuses. Eesmärk on, et programmi töö lõpuks oleks $B[i][j]$ võrdne nurkadega $(0, 0)$ ja $(i, j)$ ristküliku elementide summaga. On lihtne veenduda, et kui jõuame reale 7, siis mistahes $i$ ja $j$ korral $$B[i][j] = B[i][0] + B[i][1] + \cdots B[i][j].$$ Oletame, et me oleme mingite konkreetsete arvudega $i$ ja $j$ real 10. Tol hetkel:
B = A for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 1; k < n; k++) { B[i][j][k] = B[i][j][k - 1]; } } } for (int i = 0; i < n; i++) { for (int j = 1; j < n; j++) { for (int k = 0; k < n; k++) { B[i][j][k] = B[i][j - 1][k]; } } } for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { B[i][j][k] = B[i - 1][j][k]; } } } print(B)
Idee on sama, mis enne. Iga $i$ korral on $B[i]$ üks $n \times n$ massiiv. Kui jõuame reale 17, siis on iga $i$ jaoks lahendatud massiivis $B[i]$ "ülesanne 2". Teisisõnu, iga $(i, j, k)$ korral on $B[i][j][k]$ tippudega $(i, 0, 0)$ ja $(i, j, k)$ risttahuka summa.
Oletame, et oleme mingite konkreetsete arvudega $i, j, k$ real 21. Sellel hetkel:
Siin on koordinaadid nummerdatud paremalt vasakule: hiljem tegeleme bitimaskidega, kus just nii on kombeks.
Praeguseks on lugeja loodetavasti (eelmiste näidete varal) võimeline näiteks 4-, 5-, 6-dimensionaalse juhu jaoks programmi kirjutama. Anname siinkohal üldise skeemi.
B = A for (ik - 1 = 0; ik - 1 < n; ik - 1++) { ................................ for (i1 = 0; i1 < n; i1++) { for (i0 = 1; i0 < n; i0++) { B[ik - 1]...[i1][i0] += B[ik - 1]...[i1][i0 - 1] } } ................................ } ................................ // j-s iteratsioon for (ik - 1 = 0; ik - 1 < n; ik - 1++) { ................................ for (ij + 1 = 0; ij + 1 < n; ij + 1++) { for (ij = 1; ij < n; ij++) { for (ij - 1 = 0; ij - 1 < n; ij - 1++) { ................................ for (i0 = 0; i0 < n; i0++) { B[ik - 1]...[ij + 1][ij][ij - 1]...[i0] += B[ik - 1]...[ij + 1][ij - 1][ij - 1]...[i0]; } ................................ } } } } } ................................ for (ik - 1 = 1; ik - 1 < n; ik - 1++) { ................................ for (i1 = 0; i1 < n; i1++) { for (i0 = 1; i0 < n; i0++) { B[ik - 1]...[i1][i0] += B[ik - 1 - 1]...[i1][i0] } } ................................ } print(B)
Korrektsust on võimalik tõestada (induktsiooniga) analoogiliselt 2D ja 3D juhtudega. Selline kood iseenesest töötab, aga kirjapanek on tohutult tülikas. Pealegi, kõikide nende punktiiride kirjutamine päris koodis ei oleks võimalik. Tahaksime, et dimensioonide arvu $k$ oleks samamoodi võimalik anda parameetrina koodile ette. Sama idee kirja panekuks on vaja välja mõelda parem moodus.
Kujutame ette, et $A$ ja $B$ ei ole mitte massiivid, vaid hoopis map
id, mis
võtavad sisendiks $k$-elemendilisi täisarvude vektoreid ja tagastavad täisarve.
Sellisel juhul on eelmise koodi idee võimalik kirja panna järgnevalt.
B = A for (int j = 0; j < k; j++) { E = vektor, mis koosneb nullidest, aga paremalt j-ndal kohal on 1 for (üle kõigi vektorite i leksikograafilises järjestuses) { if (i[j] != 0) { B[i] += B[i - E]; } } } print(B)
Kolmandal real itereerime täpsemalt öeldes üle kõigi $k$-elemendiliste täisarvude vektorite, mille kõik elemendid on $0, 1, \ldots, n - 1$ seas. Vektorite $i$ ja $E$ lahutamine käib koordinaaditi.
Veendume, et tegu on sisuliselt eelmise ülesande erijuhuga, kus võetakse $n = 2$. Kirjutame arvu $i$ lahti kahendsüsteemis: $$i = i_{k - 1} 2^{k - 1} + \cdots + i_1 2^1 + i_0 2^0 = \overline{i_{k - 1} \cdots i_1 i_0}.$$ Paneme tähele, et $$\overline{i'_{k - 1} \cdots i'_1 i'_0} \subseteq \overline{i_{k - 1} \cdots i_1 i_0} \iff i'_{k - 1} \le i_{k - 1}, \ldots, i'_1 \le i_1, i'_0 \le i_0.$$ Nüüd on massiivi $B$ definitsioon muutunud järgmiseks: $$B\left[\overline{i_{k - 1} \cdots i_1 i_0}\right] = \sum_{i'_{k - 1} \le i_{k - 1}, \ldots, i'_1 \le i_1, i'_0 \le i_0} B\left[\overline{i'_{k - 1} \cdots i'_1 i'_0}\right].$$ Nüüd on näha, et see ülesanne on sisuliselt sama, mis eelmine.
Kirjutame eelmise ülesande lahenduskoodi bitimaskide kujule.
B = A for (int j = 0; j < k; j++) { E = 1 << j; for (int i = 0; i < 1 << k; i++) { if (i & 1 << j) { B[i] += B[i - E]; } } } print(B)
Olgu kohe alguses öeldud, et lahenduskäik ei kasuta mingeid erilisi liitmise omadusi. Kasutasime nendest ainult kahte (kuigi üsna varjatud kujul): liitmise assotsiatiivsus (see, et $a + (b + c) = (a + b) + c$) ja kommutatiivsus (see, et $a + b = b + a$). See tähendab, et sama ülesannet saab täpselt samal moel lahendada ka igasuguste muude tehete jaoks. Näiteks (ja ülesannetes võib seda vaja minna) võime arvutada samal moel massiivi $B$, kus $$B[i] = \max_{i' \subseteq i} A[i']; \qquad B[i] = \bigoplus_{i' \subseteq i} A[i']$$ või ka mõni muu tehe.
Esiteks otsime hoopis massiivi $C$, kus $$C[k] = \max_{i \mid j \subseteq k, i \ne j} (A[i] + A[j]) = \max_{i \subseteq k, j \subseteq k, i \ne j} (A[i] + A[j]).$$ Selleks piisab teada (iga $k$ jaoks), mis on kaks kõige suuremat $A[i]$ nii, et $i \subseteq k$.
Defineerime tehte $\odot$, kus $(a, b) \odot (c, d) = (u, v)$, kus $u, v$ on arvude $a, b, c, d$ seast kaks suurimat. Veel defineerime massiivi $$D[i] = (A[i], -\infty)$$ ja arvutame massiivi $$F[k] = \bigodot_{i \subseteq k} D[i].$$ Nüüd on $F[k]$ iga $k$ korral paar $(A[i], A[j])$, kus $A[i]$ ja $A[j]$ on kaks kõige suuremat sellist arvu, et $i$ ja $j$ on $k$ alamhulgad. Võtame $$C[k] = A[i] + A[j], \qquad \text{ kus } F[k] = (A[i], A[j]).$$ Viimaks arvutame $B$ kui $C$ prefiksimaksimumi: $$B[k] = \max(C[0], C[1], \ldots, C[k]).$$ Koodis näeb see välja nii:
pair<int, int> merge (pair<int, int> p, pair<int, int> q) { // tagastab paari, kus on kaks paaride p ja q kõige suuremat elementi } for (int i = 0; i < 1 << n; i++) { D[i] = make_pair(A[i], -INF); } F = D for (int j = 0; j < n; j++) { E = 1 << j; for (int i = 0; i < 1 << n; i++) { if (i & 1 << j) { F[i] = merge(F[i], F[i - E]); } } } for (int i = 0; i < 1 << n; i++) { C[i] = F[i].first + F[i].second; } B[0] = C[0]; for (int i = 1; i < 1 << n; i++) { B[i] = max(B[i - 1], C[i]); } print(B)