Verifică dacă un număr dat este o putere de 2 în C++

Dându-se un număr natural n, să se verifice dacă este sau nu o putere de a lui 2.

Exemplu. Pentru n = 16, răspunsul este DA. În schimb, pentru n = 3, răsunsul este NU.

Explicarea algoritmului

Pentru a verifica dacă un număr este sau nu o putere de 2, ne vom folosi de proprietățile biților. Mai precis, un număr putere de 2 are un singur bit de 1 în reprezentarea sa binară, restul cifrelor fiind de 0 (similar cum o putere de a lui 10 în baza 10 are o singură cifră de 1, restul de 0: 1, 10, 100, 1000, …). Așadar, vom căuta un bit de 1 din numărul n, și vom verifica dacă acel bit este egal sau nu cu n. Dacă acel bit este egal cu n, atunci n nu mai are alți biți de 1, așadar n este putere de 2. În caz contrar, n nu va fi putere de 2.

Poți citi acest articol pentru mai multe detalii despre parcurgerea biților.

Implementare în C++

Metoda 1 (parcurgerea biților pe rând)

Parcurgem cu o structură repetitivă de tip for biții lui n, de la ultimul bit către primul, iar primul bit de 1 întâlnit îl vom verifica dacă este egal cu n (după cum am menționat mai sus).

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim numărul nostru, n
    int n;
    cin >> n;

    //Căutăm primul bit de 1 din n
    int amGasit = 0;
    for(int i = 1; i <= n; i *= 2) {
        if(i & n) { //Am găsit un bit de 1
            if(i == n) { //Numărul n nu mai are alți biți de 1
                amGasit = 1;
                cout << "DA";
            }
            break; //Ne oprim după primul bit de 1 întâlnit
        }
    }
    if(amGasit == 0) { //Dacă nu am găsit o soluție (ori n = 0, ori n are mai mulți biți de 1)
        cout << "NU";
    }
    return 0;
}

Metoda 2 (instant)

Vom folosi o proprietate interesantă: dacă n este puterea 2^k, atunci n - 1 va avea ultimii k biți egali cu 1, restul egali cu 0. Astfel, aplicând AND între n și n - 1, vom obține 0, dacă și numai dacă n este o putere de a lui 2.

Există un caz particular, când n = 0. Îl vom trata separat.

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim numărul nostru, n
    int n;
    cin >> n;

    //Determinăm dacă n este o putere de a lui 2
    if(n == 0) { //Caz particular, când nu putem calcula n - 1
        cout << "NU"; 
    } else if(n & (n - 1)) { 
        cout << "NU";
    } else {
        cout << "DA";
    }
    return 0;
}

Alte resurse și bibliografie

• InfoGenius
• Gazeta de informatică
• Campion.edu.ro
• PbInfo