Clasa VII/VIII lecția 32 - 12 mai 2015

Lecție

Operațiuni pe biți

• Operatorii pe biți: &, |, ~, ^, <<, >>. Atenție: shift este mult mai rapid decît împărțirea!
• Atenție: acești operatori au prioritate mai mică decît cei aritmetici. Exemplu greșit: a = b << 1 + 1. De asemenea, operatorul de shift este mai puternic decît cei logici pe biți, cu excepția operatorului ~ (not) care este cel mai puternic. Pentru a fi siguri de codul vostru este bine să folosiți parantezele, deoarece astfel de greșeli sînt greu de găsit și reparat.
• Atenție: ca regulă generală este bine să folosiți întregi de tip unsigned cu operațiile de deplasare, altfel deplasarea dreapta se face cu semn.
• Constantele unsigned se vor termina cu U. Exemplu: 123U.
• 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: vector de biti
• 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

Studiu suplimentar

Pentru doritori puteți afla mai multe despre operațiuni pe biți aici:

• Lecția de operațiuni pe biți, cercul de liceu (secțiunea de operațiuni pe biți)
• Low Level Bit Hacks, calcule de bază pe biți
• Bit Hacks, diverse calcule pe biți implementate foarte eficient

Temă

• Folosiți operațiuni pe vector de biți pentru a rezolva tema:
  • int getbit(int i, unsigned int v[]) returnează valoarea bitului pe poziția i.
  • void setbit(int i, unsigned int v[]) setează elementul pe poziția i la valoarea 1.
• Tema 32 clasele 7/8
• Opțional: implementați numărarea biților folosind algoritmul logaritmic.

Rezolvări aici [1]