{x}
blog image

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

 

Example 1:

Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:

Input: n = 16
Output: true
Explanation: 24 = 16

Example 3:

Input: n = 3
Output: false

 

Constraints:

  • -231 <= n <= 231 - 1

 

Follow up: Could you solve it without loops/recursion?

Solution Explanation for Power of Two

The problem asks to determine if a given integer n is a power of two. The solutions leverage bit manipulation for efficient computation.

Understanding the Core Idea:

A power of two has only one bit set to 1 in its binary representation. For example:

  • 1 (20) = 0001
  • 2 (21) = 0010
  • 4 (22) = 0100
  • 8 (23) = 1000

If we subtract 1 from a power of two, all bits to the right of the single set bit become 1s. Then, performing a bitwise AND operation (&) between the original number and its predecessor will result in 0.

Solution 1: Using n & (n - 1)

This solution is concise and efficient. It leverages the observation described above.

  • n > 0: This condition handles the case where n is zero or negative, which cannot be a power of two.
  • (n & (n - 1)) == 0: This is the core check. If n is a power of two, this expression will evaluate to true; otherwise, it will be false.

Time Complexity: O(1) - Constant time. Bitwise operations are extremely fast and take constant time regardless of the input size. Space Complexity: O(1) - Constant space. No extra space is used beyond a few variables.

Solution 2: Using n & (-n)

This solution is a variation that uses the two's complement representation of numbers. The expression -n is equivalent to the bitwise NOT of n plus 1. For a power of two, n & (-n) will equal n itself.

  • n > 0: Again, handles non-positive inputs.
  • n == (n & (-n)): The core check. If n is a power of two, this condition holds true.

Time Complexity: O(1) - Constant time, same as Solution 1. Space Complexity: O(1) - Constant space, same as Solution 1.

Code Examples (Python):

Both solutions are presented in Python for clarity. The other languages provided in the original response use the same logic with minor syntax changes.

Solution 1 (Python):

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

Solution 2 (Python):

def isPowerOfTwo(n: int) -> bool:
    return n > 0 and n == (n & (-n))

Both solutions are highly efficient and elegant ways to solve this problem using bit manipulation. They avoid loops and recursion, fulfilling the follow-up requirement. Solution 1 is generally preferred for its slightly better readability, but both are equally efficient in terms of time and space complexity.