Power of Two — Editorial

Opening the reading…

Intuitionthe binary pattern behind powers of two

A power of two is formed by placing one 1 in a binary number and filling every other position with 0. For example, 1 is 0001, 2 is 0010, 4 is 0100, and 16 is 10000. Every positive power of two therefore has exactly one set bit.

Subtracting 1 from a number with one set bit clears that bit and turns every bit to its right into 1. Thus n and n - 1 have no set bit in the same position when n is a power of two, so their bitwise AND is zero. Any positive number with at least two set bits shares one of them with n - 1, making the AND nonzero.

Approach

Reject n <= 0 first, because zero has no set bit and negative integers are not powers of two under the problem's definition; this guard also prevents the bit test from accepting an invalid value.

Compute n & (n - 1), which removes the lowest set bit from n while leaving all higher bits unchanged; this is the operation that exposes whether another set bit remains.

Return true exactly when the AND result is zero, because a positive number reaches zero after clearing its only set bit only when it started with exactly one set bit.

Use short-circuit evaluation in n > 0 && ..., so n - 1 is evaluated only for positive n; this keeps the invalid cases out of the bit manipulation and avoids signed boundary trouble.

Complexityone bit operation and no auxiliary structure

MEASURE	BOUND	WHY
Time	O(1)	The expression performs one subtraction and one bitwise AND, regardless of how many binary positions n has. There is no loop or repeated scan.
Space	O(1) extra	The solution stores only the input and a constant number of intermediate values. The returned boolean is required output and is excluded from the extra-space bound; the bound does not degrade for any allowed input shape.

Here n is the input integer; output storage for the returned boolean is excluded from extra space.

Annotated solutionC++ · bit test · the constant-time version

CPPTest positivity, then check whether clearing the lowest set bit leaves zero.

#include <vector>

using namespace std;

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

The order of the two conditions matters. C++ evaluates && from left to right and stops when the left side is false, so zero and negative inputs never reach n - 1. For a positive n, the second condition is exactly a one-set-bit check: removing that bit leaves zero only if no other 1 remains.

The arithmetic alternativea readable division loop, at the cost of logarithmic time

CPPRepeatedly divide by two and accept only when the remaining factor is one.

#include <vector>

using namespace std;

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;

        while (n % 2 == 0) {
            n /= 2;
        }

        return n == 1;
    }
};

This is a different arrangement, not an optimisation. It repeatedly removes factors of two, so it takes O(log n) iterations in the largest positive case, while the bit test takes O(1) time. It uses O(1) extra space and can be easier to justify without bitwise knowledge, but the bit identity is the more direct fit for this problem.