Power of Two

Problem#

Return true iff n is a positive integer power of two.

Examples#

• n=1 → true; n=16 → true.
• n=3 → false; n=0 → false; n=-1 → false.

Constraints#

• -2^31 <= n <= 2^31 - 1.

Approach#

A positive power of two has a single 1 bit. n & (n - 1) clears the lowest set bit; if the result is 0 and n > 0, it had exactly one set bit.

Solution#

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

func isPowerOfTwo(n int) bool {
    return n > 0 && (n&(n-1)) == 0
}

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0

function isPowerOfTwo(n) {
    return n > 0 && (n & (n - 1)) === 0;
}

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

function isPowerOfTwo(n: number): boolean {
    return n > 0 && (n & (n - 1)) === 0;
}

Editorial#

n - 1 flips all bits below the lowest set bit of n and clears that bit’s value to 0 above. ANDing removes it; if the rest was zero, the original had a unique set bit. The n > 0 guard rejects 0 and negative numbers.

Complexity#

• Time: O(1).
• Space: O(1).

Concept revision#

Related#

• Number of 1 Bits
• Power of Three