Clasa VII/VIII lecția 31 - 10 iun 2014

Lecție

Vom vorbi despre operațiuni pe biți.

Operațiuni pe biți

• Operatorii pe biți: &, |, ~, ^, <<, >>. Atenție: shift este mult mai rapid decît împărțirea!
• Testare paritate întreg.
• Extragerea unui bit. Ideea de mască. Constante hexa în C (care încep cu 0x, ex: 0xFF12).
• Setarea unui bit pe 0.
• Setarea unui bit pe 1.
• Toggle bit.
• Compunerea mai multor valori într-un întreg. Aplicație: reprezentarea zecimal împachetat.
• Aplicație: operații pe mulțimi mari, reuniune, intersecție, etc. De menționat că reuniunea și intersecția se fac mai rapid, deoarece reunim cîte 32 (sau 64) elemente deodată.

Numărul de biți 1 ai unui întreg

Să se numere biții 1 ai unui întreg.

• Soluția clasică, shift and mask
• Soluție bazată pe resetarea ultimului bit 1
• Soluție mai rapidă, logaritmică
• Soluție cu precalculare

Codul Gray

Definiție și proprietăți.

Generare al n-lea cod Gray

Linkuri utile

• Low Level Bit Hacks, calcule de bază pe biți
• Bit Hacks, diverse calcule pe biți implementate foarte eficient

Temă

• Operațiuni pe vector de biți:
  • int get(int i, unsigned int v[]) returnează valoarea bitului pe poziția i.
  • void set(int i, unsigned int v[], int e) setează elementul pe poziția i la valoarea e, unde e este 0 sau 1.
• Implementați numărarea biților folosind algoritmul logaritmic.