Power of Two

Problem Statement

Given an integer n, the task is to determine if n can be expressed as two raised to some integer power. In mathematical terms, this is stated as checking if there exists an integer x such that n equals 2^x. The function should return true if n is a power of two and false otherwise. Understanding whether a number can be represented as a power of two is fundamental in various areas of computer science, particularly when dealing with binary computations.

Examples

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

Approach and Intuition

Understanding the problem involves recognizing that powers of two have a unique property in binary representation: they are represented as a single '1' followed by any number of '0's. This peculiar characteristic allows us to devise multiple methods to solve the problem efficiently. The constraints (-2^31 <= n <= 2^31 - 1) guide us on the valid range of input values and clarify that negative numbers and zero cannot be powers of two.

Examples

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

Steps to Approach:

1. Initial Check for Edge Cases: First and foremost, if n is less than or equal to zero, it cannot be a power of two. Thus, we return false immediately.

• Example:
  • For n = 0: Directly return false as zero is not a power of two.

1. Binary Representation and Bitwise Operations: Utilize the characteristic property of powers of two in their binary form (only one bit is '1', and all others are '0'). By using a bitwise AND operation between n and n-1, if n is a power of two, the result should be zero. This is because subtracting one from a power of two flips all the bits after the last '1' bit.

• Example:
  • Consider n = 16 which is 10000 in binary. n-1 equals 15, which is 01111 in binary. The bitwise AND of 10000 (16) and 01111 (15) results in 00000, hence returning true.

1. Mathematical Logarithmic Check: Another method is to use logarithms to verify if the logarithm base two of n gives an integer. This approach, however, may involve floating-point computations which can be prone to precision errors.

Thus, by applying these methods, we can efficiently determine if a given number n is a power of two. The utilization of bitwise operations especially leverages lower-level characteristics of numbers making this check very efficient with a constant time complexity.

Solutions

class Solution {
  public:
  bool checkPowerOfTwo(int num) {
    if (num == 0) return false;
    long number = num;
    return (number & (number - 1)) == 0;
  }
};