Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Power of Two

Power of Two

Master this topic with zero to advance depth.

Power of Two

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two if there exists an integer x such that n==2xn == 2^x.

Easy

Examples

Input: n = 1
Output: true
Input: n = 16
Output: true
Input: n = 3
Output: false
Approach 1

Level I: Brute Force (Division)

Intuition

Keep dividing the number by 2 until it hits 1. If at any point the remainder is not 0, it's not a power of two.

⏱ $O(\\log N)$💾 $O(1)$
java
class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        while (n % 2 == 0) n /= 2;
        return n == 1;
    }
}
Approach 2

Level II: Math (Max Power of Two)

Intuition

Since the input is a 32-bit signed integer, the largest power of two is 230=10737418242^{30} = 1073741824. If n is a power of two, it must be a divisor of 2302^{30}.

⏱ $O(1)$💾 $O(1)$
java
class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && 1073741824 % n == 0;
    }
}
Approach 3

Level III: Optimal (Bit Manipulation)

Intuition

A power of two in binary has exactly one bit set. The expression n & (n - 1) clears the rightmost set bit. If n is a power of two, clearing its only set bit should result in 0.

⏱ $O(1)$💾 $O(1)$
java
class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}
← Previous QuestionSingle Number
Next Question →Single Number II