Bitové triky
============

Cíl: složit různé zajímavější operace ze základních strojových instrukcí
reprezentovaných céčkovými aritemetickými a bitovými operátory (primárně
+, -, ~, &, |, ^, výjimečně se může hodit *, /, %), případně i relačními
(>, <, ==, <=, >=, !=).

Ideálně za použití co nejméně instrukcí/operací a bez použití podmínek či
smyček.

Proč? Podmínky a smyčky jsou strašně pomalé.


Zadání úloh
-----------

1. Bitová rotace... jako bitový posun, ale co přeteče, objeví se na
   druhé straně.
2. Násobení konstantou (např. x*20)
3. Zaokrouhlení čísla na násobek 16 (nebo obecně nějaké mocniny dvojky)
    - nahoru / dolů / nejbližší
4. Test, zda číslo je mocnina dvojky
     4a: Návodná úloha: najít nejpravější jedničku v x
         (např. nejpravejsi(0b10100) == 0b100)
5. Zaokrouhlit číslo na nejbližší vyšší/nižší mocninu dvojky
6. Zrcadlení čísla (převrácení pořadí bajtů/bitů)
7. Absolutní hodnota
8. Signum
9. Parita, tedy XOR všech bitů čísla. Parita je 1 <=> číslo obsahuje
   lichý počet jedniček.

Můžeš se nad nimi zkusit zamyslet, níže jsou řešení.

Obvykle chceme ideálně konstantní počet operací, pokud to jde, případně
logaritmický v šířce slova.





------ spoiler --------


1. Bitová rotace - např. 64b doprava

     (x >> k) | (x << (64-k));


     ... ale může se rozbít pro k=0, protože << 64 je nedefinované chování

     potenciální oprava
     (x >> k) | (x << ((64-k)&63));

2. Násobení 20: 

     x * 20 == x * (16 + 4) == x*16 + x*4 == (x << 4) + (x << 2)

3. Zaokrouhlení na násobek 16:

     dolů:   (x / 16) * 16 == (x >> 4) << 4
     nahoru: ((x+15) >> 4) << 4
     nejbližší ((x+8) >> 4) << 4

4a. Nalezení nejpravějšího bitu:

       x & ~(x-1)

   Rozmysleme si, jak čísla vypadají:

                    .--------- část před první jedničkou (může být cokoli, označíme 'p')
                   v  v------- nejpravější jednička, za ní nuly
       x:        [ p ]100000
       x-1:      [ p ]011111
       ~(x-1):   [~p ]100000
       x&~(x-1): 00000100000

   Tedy x&~(x-1) dá přesně nejpravější jedničku v x.

4. Test mocniny dvojky: mocnina dvojky obsahuje právě jednu jedničku,
   je tedy rovna své nejpravější jedničce:

       x == x&~(x-1)

   Mohli bychom taky použít řešení 5, ale to je logaritmické, kdežto 4
   jde konstantní.

5. Zaokrouhlení na mocniny dvojky (logaritmický počet instrukcí)

   Nejdřív si rozmyslíme, jak z čísla udělat řetězec jedniček stejné
   délky, jako původní číslo:

      // Např. jednicky(0b10110) == 0b11111
      uint64_t jednicky(uint64_t x) {
          x |= x >> 32;
          x |= x >> 16;
          x |= x >> 8;
          x |= x >> 4;
          x |= x >> 2;
          x |= x >> 1;
      }

    Nyní si snadno rozmyslíme, že nejbližší ostře větší mocnina dvojky
    než x je přesně jednicky(x) + 1. Pokud chceme nejbližší neostře
    větší (což většinou chceme), pak triviálně upravíme na
    jednicky(x-1) + 1. Nejbližší nižší pak podobně nahlédneme, že je
    (jednicky(x) >> 1) + 1 nebo (jednicky(x) + 1) >> 1 (vyjde stejně).

6. Zrcadlení - rekurzivně prohazujeme půlky (logaritmický počet
   operací). Např. bajtové zrcadlení 64b čísla:

       x = (x >> 32) | (x << 32);
       x = ((x & 0xFFFF0000FFFF0000) >> 16) | ((x & 0x0000FFFF0000FFFF) << 16);
       x = ((x & 0xFF00FF00FF00FF00) >> 8) | ((x & 0x00FF00FF00FF00FF) << 8);

    Pro bitové zrcadlení bychom pokračovali dál analogicky.

8. Signum:

   S porovnávacími operátory:

       Např. (x > 0) - (x < 0)
       (porovnávací operátory se dají používat nejen v podmínkách, ale
       normálně vrací 0/1)

   Bez porovnávacích operátorů:
       Zamysleme se nad výrazem

           x >> 63 (pro 64b čísla; bitový posun je aritmetický)

       Všechny jeho bity budou kopií nejvyššího (znaménkového) bitu x. Tedy
       pro záporné x samé jedničky, jinak samé nuly. Nyní můžeme definovat:

           Z(x) = (x >> 63) & 1

       Nyní si snadno rozmyslíme, že platí:

           Z(x) = x < 0
           Z(-x) = x > 0

       Tedy: sgn(x) = Z(-x) - Z(x)