(Categoria _Algoritmi_, Autor _Cosmin Negruşeri_)

(toc){width: 25em}*{text-align:center} *Conţinut:*
* 'Aplicaţia 1':operatii-pe-biti#aplicatia-1
* 'Aplicaţia 2':operatii-pe-biti#aplicatia-2
* 'Aplicaţia 3':operatii-pe-biti#aplicatia-3
* 'Aplicaţia 4':operatii-pe-biti#aplicatia-4
* 'Aplicaţia 5':operatii-pe-biti#aplicatia-5
* 'Aplicaţia 6':operatii-pe-biti#aplicatia-6
* 'Preprocesare':operatii-pe-biti#preprocesare
* 'Preprocesare aplicatia 1':operatii-pe-biti#aplicatia-p1
* 'Preprocesare aplicatia 2':operatii-pe-biti#aplicatia-p2
* 'Preprocesare aplicatia 3':operatii-pe-biti#aplicatia-p3
* 'Preprocesare aplicatia 4':operatii-pe-biti#aplicatia-p4
* 'Preprocesare aplicatia 5':operatii-pe-biti#aplicatia-p5
* 'Algoritmi mai seriosi':operatii-pe-biti#algoritmi
* 'Ciurul lui Eratostene':operatii-pe-biti#ciur
* 'Bibliografie':operatii-pe-biti#bibliografie
 
 

În cadrul acestui articol vă vom prezenta câteva metode prin care programele se pot optimiza dacă utilizăm eficient operaţiile pe biţi sau folosim operaţii pe biţi în locuri în care, la prima vedere, nu s-ar părea că ar fi necesare.
De cele mai multe ori, atât în concursuri cât şi în viaţa de zi cu zi a programatorului, atunci când implementăm o metodă care este folosită de o aplicaţie şi vrem să facem această metodă eficientă ca timp de execuţie, suntem învăţaţi din şcoală (sau ar trebui sã fim învăţaţi, chiar dacă unii dintre profesori consideră că cel mai important algoritm învăţat în liceu este _backtraking_-ul, soluţia tuturor problemelor) să ne uităm la complexitatea algoritmului implementat şi dacă observăm că în practică algoritmul este mai încet decât ne dorim noi să fie să încercăm să găsim un algoritm cu un ordin de complexitate mai mic.

În continuare vom încerca să găsim soluţii mai rapide decât cele naive pentru unele operaţii de bază (toate operaţiile vor fi implementate pentru întregi pozitivi reprezentaţi pe 32 de biţi).

h2(#aplicatia-1). Aplicaţia #1

h2. Aplicaţia #1

bq. Să se determine numărul de biţi de 1 din reprezentarea binară a lui $n$.

Dar este acest algoritm mai rapid? Am testat pentru toate numerele de la $1$ la $2^24^$ şi rezultatele au fost $2,654$ secunde folosind metoda naivă şi $0.821$ folosind a doua metodă.
Rezultatul mult mai bun al celei de-a doua metode se bazează în principal pe faptul că ea execută un număr de paşi egali cu numărul de biţi cu valoarea 1 din număr, deci în medie jumătate din numărul de paşi efectuaţi de prima metodă.

h2(#aplicatia-2). Aplicaţia #2

h2. Aplicaţia #2

bq. Să se determine paritatea numărului de biţi de 1 din reprezentarea binară a unui număr $n$.

Deşi constanta multiplicativa este mai mare, numărul de operaţii are ordin logaritmic faţă de numărul de biţi ai unui cuvânt al calculatorului.

h2(#aplicatia-3). Aplicaţia #3

h2. Aplicaţia #3

bq. Să se determine cel mai puţin semnificativ bit de 1 din reprezentarea binară a lui n.

Această funcţie este foarte importantă pentru structura de date 'Arbori Indexaţi Binar':problema/aib prezentată într-un un articol mai vechi din 'GInfo':http://www.ginfo.ro/revista/13_1/focus.pdf.

h2(#aplicatia-4). Aplicaţia #4

h2. Aplicaţia #4

bq. Să se determine cel mai semnificativ bit cu valoarea 1 din reprezentarea binară a lui n.

}
==

h2(#aplicatia-5). Aplicaţia #5

h2. Aplicaţia #5

bq. Să se determine indexul celui mai semnificativ bit de 1 din reprezentarea binară a lui $n$.

Pentru ca această metodă să fie eficientă ne trebuie o metodă *count* eficientă.

h2(#aplicatia-6). Aplicaţia #6

h2. Aplicaţia #6

bq. Să se determine dacă $n$ este o putere a lui 2 (întrebare interviu Microsoft).

==

h2(#preprocesare). O altă abordare: preprocesarea

h2. O altă abordare: preprocesarea

Operaţiile prezentate mai sus sunt implementate în limbajele de asamblare, dar câteodată se folosesc algoritmi naivi şi atunci o implementare inteligentă ajunge să fie mai rapidă decât instrucţiunea din limbajul de asamblare. Pentru unele supercalculatoare aceste instrucţiuni sunt instrucţiuni ale procesorului.
Se pot găsi alţi algoritmi mai rapizi decât cei de mai sus, dar de obicei găsirea unui algoritm mai inteligent este mai grea decât folosirea unei abordări banale care aduce un câştig foarte mare: preprocesarea.
În continuare vom rezolva problemele prezentate anterior folosindu-ne de preprocesarea datelor.

h3(#aplicatia-p1). Aplicaţia #1

h3. Aplicaţia #1

bq. Determinăm, pentru numerele de la 0 la $2^16^ - 1$, un tablou $num$, în care $num[i]$ este egal cu numărul de biţi de 1 din reprezentarea binară a lui $i$.

}
==

h3(#aplicatia-p2). Aplicaţia #2

h3. Aplicaţia #2

bq. Determinăm, pentru numerele de la 0 la $2^16^ - 1$, un tablou $par$, în care $par[i]$ este egal cu paritatea numărului de biţi de 1 din reprezentarea binară a lui $i$.

}
==

h3(#aplicatia-p3). Aplicaţia #3

h3. Aplicaţia #3

bq. Determinăm, pentru numerele de la 0 la $2^16^ - 1$, un tablou $l$, în care $l[i]$ este egal cu cel mai nesemnificativ bit de 1 din reprezentarea binară a lui $i$.

}
==

h3(#aplicatia-p4). Aplicaţia #4

h3. Aplicaţia #4

bq. Determinăm, pentru numerele de la 0 la $2^16^ - 1$, un tablou $h$, în care $h[i]$ este egal cu cel mai semnificativ bit de 1 din reprezentarea binară a lui i.

}
==

h3(#aplicatia-p5). Aplicaţia #5

h3. Aplicaţia #5

bq. Determinăm, pentru numerele de la 0 la $2^16^ - 1$, un tablou $iH$, în care $iH[i]$ este egal cu indexul celui mai semnificativ bit de 1 din reprezentarea binară a lui $i$ şi este egal cu -1 pentru 0.

}
==

h2(#algoritmi). Algoritmi mai serioşi

h2. Algoritmi mai serioşi

Deşi ceea ce am prezentat mai sus sunt mai degrabă trucuri de implementare decât algoritmi serioşi şi în general nu se acordă aşa mare importanţă detaliilor de genul acesta, câteodată asemenea trucuri se pot dovedi importante mai ales în timpul concursurilor.
Un exemplu ar fi problema rundei 12 de la concursul de programare Bursele Agora. Acolo se cerea găsirea numărului de dreptunghiuri conţinute de o matrice binară $a$ care au în colţuri 1. Un algoritm de complexitate $O(n^2^ · m)$ ar fi fost următorul: se consideră fiecare pereche formată din două linii şi se numãrã câte perechi ( $a{~i,k~}$, $a{~j,k~}$ ) pentru care $a{~i,k~}$ = 1 şi $a{~j,k~}$ = 1 există. Fie acest număr $x$. Atunci numărul de dreptunghiuri care au colţurile pe aceste două linii va fi $x · (x - 1)$ / 2.

Să încercăm acum rezolvarea unei probleme în care eficienţa este cea mai importantă, mai importantă decât lizibilitatea codului obţinut. Problema are următorul enunţ:

bq(#ciur). Se consideră un număr $n$. Să se determine numerele prime mai mici sau egale cu $n$, unde $n$ ≤ 10.000.000.

bq. Se consideră un număr $n$. Să se determine numerele prime mai mici sau egale cu $n$, unde $n$ ≤ 10.000.000.

Practic această problemă ne va fi utilă în testarea rapidă a primalităţii numerelor mai mici sau egale cu $n$.

programul ilizibil, tocmai din acest motiv, asemenea trucuri trebuie aplicate numai în locurile critice ale codurilor sursă pentru a
duce la o creştere semnificativă de viteză a aplicaţiilor şi trebuie documentate foarte bine, mai ales dacă se doreşte sau este necesar ca alt programator să poată lucra cu codul respectiv mai târziu.

h3(#bibliografie). Bibliografie

h3. Bibliografie

# James A. Storer, An Introduction to Data Structures and Algorithms, Springer Verlag, 2001
# T. H. Cormen, C. E. Leiserson, R. R. Rivest, Introducere în algoritmi, Editura Computer Libris Agora, 2000