Vzpomenme si, jak overit, zda je dane cislo 2^k:

	!(x & (x - 1))

Zkusme vymyslet nekolik dalsich operaci:

(i) Jak najit nejpravejsi jednickovy bit? (Tzn. maska odpovidajici
tomuto bitu.)

(ii) Jak prohodit dve cisla "in-place", tedy bez pomocne
promenne?

(iii) Jak zaokrouhlit cislo na nejblizsi nizsi mocninu dvojky?
Hint: Ted uz nas algoritmus (nebo cyklus) bude zavisly na sirce
slova, univerzalni zpusob nezname. Predpokladejte w=8 bitu.
Nestaci ale slozitost O(w), lze snadno vymyslet O(log w).
Take je dulezite se v cyklu vyhnout testum - podminene skoky
jsou nakladne operace, ktere nas mohou stat mnoho cyklu navic.

(iv) Jak zmirrorovat bity cisla? Tedy otocit slovo tak, aby
z nejlevejsiho bitu byl nejpravejsi atd. Opet predpokladejte
w=8 bitu a existuje O(log w) "rozdel a panuj" algoritmus.

(v-a) Jak spocitat pocet jednickovych bitu v cislu ("population
count", popcount)?
Hint: Podobna myslenka "rozdel a panuj" jako (iii).

(v-b) Jak spocitat pocet nul vlevo od prvni jednicky?  (w=8)

(v-c) Jak spocitat dvojkovy logaritmus cisla?  (w=8)

(vi) Jak spocitat absolutni hodnotu cisla? (Toto jde opet
snadno zakladnimi operacemi, univerzalne k velikosti slova.)

(vii) Linus Torvalds nedavno navrhl rychly zpusob, jak pocitat
hashe polozek cesty pri vyhledavani souboru podle jmena:

	http://article.gmane.org/gmane.linux.kernel/1260888

Rozmyslete si, jak vypada hashovaci funkce a jakym zpusobem
se ve vyse predlozene implementaci pocita.



---- Hinty a reseni

Nejdrive se divejte pouze na hint, na implementaci pouze, kdyz ani
pomoci hintu s resenim nepohnete.



(i) Hint: Rozdelme si reseni na dve faze:

	(i-0) Vyrobime masku, ktera se bude skladat z praveho
	bloku samych jednicek, ktery pokryva vsechny prave nulove bity
	puvodniho cisla a nejnizsi jednickovy bit, a zbytku nuloveho:

	10010100 -> 00000111

	(i-1) Z bloku z (i-0) vybereme nejvyssi jednickovy bit
	a ten preneseme do vysledne hodnoty.


Implementace:

	(i-0) y = (x ^ (x-1))
	(i-1) (y + 1) >> 1


(i') Alternativni zpusob: x & (-x) (vzpomente, ze -x = ~(x-1)).
Rozmyslete si.


(ii) Hint: Xor je kouzelna operace.


Implementace:
	swap(a,b): a ^= b; b ^= a; a ^= b;
Je operace xor komutativni?  Zkuste rigorozne dokazat, ze swap()
funguje.


(iii) Hint: Pretransformujme cislo tak, aby po nejlevejsi jednicce
uz melo v sobe same jednicky (tedy nejlevejsi jednicku "rozmazme"
doprava) a pak staci aplikovat (i-1) box.


Implementace:

	Naivne: x | (x >> 1) | (x >> 2) | ...
	Logaritmicky: x |= (x >> 4); x |= (x >> 2); x |= (x >> 1);


(iv) Hint: Nejdrive prohodime ctverice, pak vzajemne sousedni dvojice,
pak sousedni bity v kazde dvojici. Pro sirsi slova snadno naopak
rozsirime.


Implementace:

	Prohozeni ctveric: x = (x << 4) | (x >> 4)
	Prohozeni dvojic: Vymaskujeme vzdy "leve" dvojice a "prave"
	dvojice a pak vzajemne posuneme a slozime zpet.
		x = ((x & 0b11001100) >> 2) | ((x & 0b00110011) << 2)
	Cele dohromady jiz slozite snadno.


(v-a) K rozmysleni na doma.


(v-b), (v-c) jsou vpodstate ekvivalentni. Zkusme ukazat treba (v-c),
opet pomoci "rozdel a panuj" algoritmu - pokud umime spocitat index
nejlevejsi jednicky v n/2 bitovem cisle, jak pomoci jedine iterace
navic spocitame index nejlevejsi jednicky v n bitovem cisle?


Implementace:

	int i = 0;
	if (x & 0b11110000) { x >>= 4; i += 4; }
	if (x & 0b00001100) { x >>= 2; i += 2; }
	if (x & 0b00000010) { x >>= 1; i += 1; }
	return i;


(vi), (vii) K rozmysleni na doma.