Cvičení na práci s bitovou reprezentací čísel

(Tato cvičení byla převzata z minulého běhu, který vedl Filip Štedroňský. Díky!)

Implementujte následující operace pouze za použití elementárních operací:
+ - << >> ! ~ * / % | & < > <= >=.

Tato úloha nemá deadline (resp. deadline je konec LS).

- (1b) Rotace unsigned čísla vlevo a vpravo
  - Rotace 32-bit unsinged čísla doprava o 7: rotr(0xAABBCCDD, 7) = 0xBB557799
  - Pozor: aritmetický shift doleva o >= bitovou šířku typu je undefined behavior!

- (1b) Implementujte násobení a dělení mocninou dvojky
  - Bez operací dělení a násobení
  - Hint: jak vypadá libovolné číslo v binárním zápisu po vynásobení dvěma?

- (2b) Násobení 20
  - Bez operace násobení

- Implementujte dělení se zaokrouhlením:
  - (Dolu se zaokrouhluje by default, např. div\_round\_down(9, 4) = 9 / 4 == 2.)
  - (1b) Implementujte dělení se zaokrouhlením nahoru ("rounding up"): div_round_up(9, 4) == 3
  - (1b) Implementujte dělení se zaokrouhlením na nejbližší celé číslo ("rounding half up"): div_round_half_up(15, 10) == 2

- (2b) Test, zda je číslo mocnina dvojky
  - Hint: jak vypadá binární zápis čísla, které je mocnina dvojky?
  - Hint: může se vám hodit Kernighanův trik, který použil ve své verzi popcnt:

         int popcnt(unsigned u)
         {
                 int c = 0;
                 while (u) {
                         u &= u - 1;
                         c++;
                 }
                 return c;
         }

- (2b) Zrcadlení bajtů v čísle
  - Bez příslušných hardwarových instrukcí, jen pomocí základních operací
  - Např. mirror(0xAABBCCDD) == 0xDDCCBBAA
  - Hint: lze aplikovat podobný postup, jako v popcnt\_bitpara.

- (2b) Zrcadlení bitů v čísle:
  - Hint: rozšiřte předchozí cvičení

- (3b) Zaokrouhlení na nejbližší ostře větší mocninu dvojky
  - Krásný hack!
  - Hint:
    - Nejprve číslo převeďte na samé jedničky stejné délky:
      - Např. 000001001010010001 -> 000001111111111111
      - Opět lze použít rozděl a panuj jako v popcnt\_bitpara, zrcadlení
    - Potom si rozmyslete, jaký je binární zápis nejbližší ostře větší mocniny dvou

- (1b) Bonus: Zaokrouhlení na nejbližší neostře větší mocninu dvou
  - Hint: lze odvodit z předchozího cvičení