Putere a lui 2

Uneori trebuie să verificăm dacă un număr întreg este sau nu putere a lui 2. Avem la dispoziție o mulțime de variante:

• putem împărți numărul la 2 până când ajungem la valoarea 1 și, dacă tot timpul împărțirea a fost exactă, tragem concluzia că numărul este putere a lui 2;
• putem începe de la 1 și înmulți repetat cu 2 până când ajungem la un număr mai mare sau egal cu numărul dat; dacă am ajuns exact la numărul dat, acesta este putere a lui 2;
• putem număra biții numărului care au valoarea 1; dacă există un singur astfel de bit, numărul este putere a lui 2.

Mai sunt și alte variante, majoritatea având ordinul de complexitate O(log n).

Dar, există și o variantă în timp constant, chiar foarte simplă. Dacă scădem 1 dintr-un număr, cel mai nesemnificativ bit al său care are valoarea 1 devine 0 și toți biții mai nesemnificativi (care aveau valoarea 0) primesc valoarea 1.

Dacă numărul este putere a lui 2, atunci al are un singur bit cu valoarea 1 și acest bit s-ar modifica. Putem spune că niciun bit care avea înainte valoarea 1 nu și-o păstrează. Pentru numerele care nu sunt puteri ale lui 2, există cel puțin doi biți cu valoarea 1 și doar valoarea unuia se pierde.

Pentru a verifica dacă, după scădere, vreun bit și-a păstrat valoarea 1, putem efectua o conjuncție binară între valoarea dată și valoarea cu 1 mai mică.

Așadar, dacă valoarea inițială ar fi n, n este putere a lui 2 dacă:

Mai trebuie tratat cazul special n = 0; am presupus că n este un număr pozitiv.