Power of Two

Share

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 == 2^x.

Example 1
Input: n = 1
Output: true
Explanation: 2^0 = 1.
Example 2
Input: n = 3
Output: false
Explanation: 3 is not expressible as 2^x for any integer x.

Solution Approach

A power of two has exactly one bit set in its binary representation (e.g., 1=001, 2=010, 4=100, 8=1000). The expression n & (n-1) clears the lowest set bit of n. If n is a power of two, this results in 0.

  • n must be greater than 0 (powers of two are positive).
  • n & (n-1) must equal 0: this is true only when n has exactly one set bit.
  • Combine both conditions: n > 0 && (n & (n-1)) == 0.
Java
class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}
Complexity Analysis:

Time complexity: O(1). Single bit operation.
Space complexity: O(1). Constant extra space.