Checking for a power of 2

Original: Verificarea unei puteri a lui 2

O(1)C++1736 lines2 examples

The idea

A power of 2 has a single 1 bit in base 2 (for example 64 = 1000000). Subtracting 1 turns that bit into 0 and all the bits to its right into 1 (63 = 0111111), so n & (n - 1) is 0 exactly for powers of 2. The & operator is the bitwise AND.

Original description (Romanian)

O putere a lui 2 are în baza 2 un singur bit de 1 (de exemplu 64 = 1000000). Scăzând 1, acel bit devine 0 și toți biții din dreapta lui devin 1 (63 = 0111111), deci n & (n - 1) este 0 exact pentru puterile lui 2. Operatorul & face „și” bit cu bit.

Complexity: O(1)
Grade: Grade 9 (Clasa a IX-a)
Chapter: Number bases

Examples

Example 1

Input

Expected output

DA

Example 2

Input

Expected output

NU

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

putere-a-lui-2.cpp

/*
 * Titlu: Verificarea unei puteri a lui 2
 * Clasa: 9
 * Capitol: Baze de numerație
 * Descriere: O putere a lui 2 are în baza 2 un singur bit de 1 (de exemplu
 *            64 = 1000000). Scăzând 1, acel bit devine 0 și toți biții din dreapta
 *            lui devin 1 (63 = 0111111), deci n & (n - 1) este 0 exact pentru
 *            puterile lui 2. Operatorul & face „și” bit cu bit.
 * Complexitate: O(1)
 *
 * Exemplu
 * Intrare: 64
 * Ieșire: DA
 *
 * Exemplu
 * Intrare: 48
 * Ieșire: NU
 */
#include <iostream>
using namespace std;

int main()
{
    long long n;
    cin >> n;
    if (n > 0 && (n & (n - 1)) == 0)
    {
        cout << "DA" << '\n';
    }
    else
    {
        cout << "NU" << '\n';
    }
    return 0;
}

Input (stdin)

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.