Topics › Bit Manipulation › Learn Bit Manipulation

Check if a Number is Power of 2 or Not

Easy TUF ID 172 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an integer n. Return true if there is an integer k ≥ 0 with n = 2^k, and false otherwise. So 1, 2, 4, 8, 16, ... are powers of two; 0, every negative number and everything in between are not.

Constraints: -2^31 ≤ n ≤ 2^31 - 1.

Example 1

n = 16
answer = true        // 16 = 2^4, binary 10000

Example 2

n = 12
answer = false       // 12 = 1100 has two set bits

Example 3

n = 0
answer = false       // no power of two is zero; this is the input that breaks careless solutions

Approach 1: Brute force, divide by 2 while even

Intuition. If n is a power of two, halving it repeatedly gives smaller powers of two all the way down to 1. If at any point the number is odd and not 1, some odd factor other than 1 is present and n cannot be a power of two. Zero and negatives are rejected up front because the loop would never terminate on 0 and the question is meaningless for negatives.

Algorithm.

1. If n ≤ 0, return false.
2. While n is even, replace n by n / 2.
3. Return whether n == 1.

static boolean bruteForce(int n) {
    if (n <= 0) return false;
    while (n % 2 == 0) n /= 2;
    return n == 1;
}

Complexity. Time O(log n): each iteration halves n, at most 31 times. Space O(1).

This is already fast; the interest in the later approaches is that they are branch-free one-liners, and that the reasoning behind them is reused by many other bit problems.

Approach 2: Better, count the set bits

Intuition. In binary a power of two is a single 1 followed by zeros: 1, 10, 100, 1000, .... So n is a power of two exactly when it is positive and has exactly one set bit. Counting set bits with Brian Kernighan’s loop (n &= n - 1 removes the lowest set bit each round) gives the answer in as many steps as there are ones.

Algorithm.

1. If n ≤ 0, return false.
2. Count the set bits: while n != 0, do n &= n - 1 and increment a counter.
3. Return whether the counter is 1.

static boolean better(int n) {
    if (n <= 0) return false;
    int count = 0;
    while (n != 0) {
        n &= n - 1;
        count++;
    }
    return count == 1;
}

Complexity. Time O(number of set bits), at most 31 rounds. Space O(1).

Seeing this written out exposes the shortcut: we only care whether the count is exactly one, so after the first removal the question is “is anything left?”. That observation is Approach 3.

Approach 3: Optimal, n & (n - 1)

Intuition. Subtracting 1 from n flips the lowest set bit to 0 and every 0 below it to 1, leaving all higher bits untouched. For n = 16 = 10000, n - 1 = 01111. For n = 12 = 1100, n - 1 = 1011. AND the two: for a power of two the single 1 was flipped off and nothing above it exists, so the result is 0. For any other positive number the bits above the lowest set bit survive in both operands, so the result is non-zero.

The guard n > 0 is essential. For n = 0, n - 1 is -1 (all ones) and 0 & -1 = 0, which would wrongly say true. For Integer.MIN_VALUE, which is a single 1 in the sign position, the AND is also 0, but a negative number is not a power of two.

Algorithm.

1. Return n > 0 && (n & (n - 1)) == 0.

static boolean optimal(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Dry run.

Complexity. Time O(1): a subtraction, an AND and two comparisons. Space O(1).

Two other constant-time formulations are worth knowing. n & -n isolates the lowest set bit (because -n = ~n + 1 agrees with n only at that bit), so n is a power of two when the isolated bit is all of n:

static boolean optimalLowestBit(int n) {
    return n > 0 && (n & -n) == n;
}

And a purely arithmetic one: 2^30 is the largest power of two that fits in an int, and the divisors of 2^30 are exactly 2^0, 2^1, ..., 2^30. So a positive n is a power of two if and only if it divides 2^30:

static boolean optimalDivisor(int n) {
    return n > 0 && (1 << 30) % n == 0;
}

The Java file checks all five methods against Integer.bitCount(n) == 1 for every n from -64 to 5000 plus the extremes, and they agree everywhere.

Edge cases and pitfalls

• n = 0. The most common wrong answer. 0 & (0 - 1) is 0, so the bit trick says true without the n > 0 guard. The brute force would loop forever on 0 % 2 == 0.
• n = 1. 2^0 = 1 is a power of two; 1 & 0 = 0 and the loop in Approach 1 exits immediately with n == 1.
• Negative numbers. Never powers of two. Integer.MIN_VALUE has exactly one set bit (the sign bit), so a solution that only counts bits without checking the sign returns true for it.
• Integer.MAX_VALUE. 2^31 - 1 is all ones below the sign bit; n & (n - 1) is 2^31 - 2, non-zero, correctly false.
• 1 << 30. The largest power of two representable as a positive int; 1 << 31 is Integer.MIN_VALUE, so there is no int equal to 2^31.
• Powers of two in a long. The same n > 0 && (n & (n - 1)) == 0 works unchanged for long; the divisor trick would need 1L << 62.

Related problems

• Introduction to Bits and Tricks derives the n - 1 flip that this problem relies on.
• Set/Unset the rightmost unset bit uses the same n & (n - 1) as an operation rather than a test.
• Count the Number of Set Bits is Approach 2 done in full.
• Check if a Number is Odd or Not is the sibling one-bit test.