Thanks pentru idee. O sa incerc sa o pun in practica pe un exemplu concret. Sunt sigur ca o sa-mi foloseasca intr-un anume moment

Okay, inca o problemutza de data asta mai simpla dar indeajuns de interesanta incat sa ai un "a - ha". Se da un numar x, sa se determine daca este putere a lui doi sau nu(de exemplu 1,2,4,8,16). 5 nu este putere a lui doi . Cine poate gasi o solutzie in O(1)?!!!

Parca se faceau niste operatii pe biti (cred ca sau) cu numarul respectiv si cu nr-1 dar nu mai stiu exact.

Asa, da.. Ideea e ca un numar care este putere a lui doi are un singur bit de 1 si restul de 0. Sa luam un numar putere a lui 2 numit x. El are urmatoarea reprezentare:

1 . . . . 0 -> x
011 . . . 1 -> x-1

Punctele reprezinta sirul de biti(de 0). Acest numar e scris in little endian adica cel mai reprezentativ(important) bit este cel din stanga. Interesant este ca daca scadem 1 unitate din x, rezultatul va arata astfel:

Daca facem & pe biti intre aceste doua numere atunci obtinem 0. Mai exista cazuri cand putem obtine 0? Sigur ca da. De exemplu:

1110 &
0001
= 0
sau
1010 &
0101
= 0

O intrebare interesanta este: mai putem obtine 0, cand x nu este putere a lui 2 facand SI logic intre x si x-1? Nu chiar. Scazand 1 dintr-un numar anulam cel mai nesemnificativ bit. Exemplu x=5;
in baza 2: 5 = 101
in baza 2: 4 = 100
Este evident ca nu vom obtine 0 decat daca x este putere a lui 2. So there you have it !

Doua linkuri pentru cei interesati de perversiuni cu biti: Bit Twiddling Hacks si Advanced bit manipulation-fu.

What's the "condition" so that the following code snippet prints both HelloWorld !

if "condition"
printf ("Hello");
else
printf("World");

Maltratand un pic cerinta:

if(1);
#define else ;
printf ("Hello");
else
printf("World");