Easy–medium · Number theory

Is It a Power of Two?

Decide whether a number is a power of two (1, 2, 4, 8, ...). A short problem with a beautiful bit trick inside.

At a glanceA positive n is a power of two exactly when n & (n - 1) is 0 — handle 0 separately, since 0 & -1 is also 0 but 0 is not a power of two.

Problem

Input: One integer n (0 <= n <= 1000000).

Output: yes if it is a power of two, otherwise no.

Sample:

Input	Output
`8`	`yes`

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Watch out for 0

0 is not a power of two, and while (n % 2 == 0) n /= 2; never terminates on 0. Handle n < 1 first.

Hint 2 — The bit trick (bonus)

A power of two has exactly one 1-bit, so (n & (n - 1)) == 0 for n > 0. Check on paper: 8 = 1000, 7 = 0111, AND = 0000.

Solution (try it first!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n < 1) {
        cout << "no" << endl;
        return 0;
    }
    while (n % 2 == 0) n /= 2;
    if (n == 1) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}

The bit trick is O(1) instead of O(log n) — the same feeling as the square-root shortcut.

Deep dive

Why this works

A power of two has exactly one set bit, so n & (n-1) clears it and the answer is zero. A loop becomes one instruction.

The cost

O(1) versus O(log n) for repeated division — and this is what the compiler emits anyway.

Where it goes wrong

n & (n-1) == 0 parses as n & ((n-1) == 0) because == binds tighter than &. Parenthesise.
The trick reports that 0 is a power of two. Exclude n <= 0 explicitly.

Next step

Count the bits instead: Bit Count.

Two things to remember

n & (n-1) clears the lowest set bit.
== binds tighter than & — always parenthesise.

🐞 This version fails — open it and try

== binds tighter than &, so the test means nothing

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n & (n - 1) == 0) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}