Note de curs, clasele 9-10, 6 martie 2014
Calculul unor proprietăți ale numerelor pe 32 / 64 de biți
Uneori veți avea nevoie să calculați proprietăți ca
- numărul de biți 1 din reprezentarea binară a lui x (popcount).
- logaritmul în baza 2 al lui x (care este totuna cu numărul de ordine al celui mai din stânga bit 1)
- dacă x este putere al lui 2
Este bine de știut că există metode și metode de a face aceste calcule, din care unele pot fi de 10-20 de ori mai rapide decât celelalte. Dacă aceste calcule sunt o componentă critică a programului vostru, este bine să știți ce merge și ce nu merge. Experimentați din timp.
Includ ca exemplu Media:popcount.cpp, unde am experimentat cu 5 metode de a calcula popcount. Timpii obținuți pentru 100.000.000 de evaluări sunt:
metoda | timp (ms) |
---|---|
naiv | 5.000 |
Kernighan | 3.265 |
lookup table 1 | 355 |
lookup table 2 | 460 |
în paralel | 270 |
Se vede că există diferențe notabile între ultimele trei metode, dar oricare dintre ele mătură pe jos cu metodele naive.
Aceste calcule și multe altele le puteți găsi la http://graphics.stanford.edu/~seander/bithacks.html
Programare dinamică
Vom urma notele de la clasele 11-12, dar vom insista mai mult pe probleme. Vom sta două lecții pe acest subiect și abia spre sfârșitul lecției a doua vom extrage niște principii teoretice.