Problem Statement

Given an integer number, check whether it is a power of 2 or not. A number is considered a power of 2 if it can be expressed as 2^k, where k is a non-negative integer.

Input:

• number: An integer.

Output:

• Return true if the number is a power of 2, otherwise return false.

Constraints:

• 0 ≤ number ≤ 2^31 - 1 (32-bit unsigned integer)

Consider the task of determining whether a given positive integer is a power of 2. Traditionally, one might approach this problem using conditional statements or loops. However, the challenge is to devise a solution that avoids the use of any branching or looping constructs, enhancing efficiency and maintaining simplicity.

Understanding the Problem

The goal is to create an algorithm that can swiftly verify if a given positive integer is a power of 2. A positive integer is considered power of 2 if it can be expressed as 2 to the power of non-negative integer. For instance, 1, 2, 3, 8, 16, and so on, are powers of 2.

Examples

Example 1:

Input: number = 16
Output: true

Explanation: 16 can be expressed as 2^4, so it is a power of 2.

Example 2:

Input: number = 18
Output: false

Explanation: 18 cannot be expressed as 2^k, so it is not a power of 2.

Observation

A number is a power of 2 if it has exactly one set  bit (1) in its binary representation. For example:

2^0 = 1 (Binary: 0001)
2^1 = 2 (Binary: 0010)
2^2 = 4 (Binary: 0100)
2^4 = 8 (Binary: 1000)
.
.
.

For a number to be a power of 2:

1. It must have only one (1) bits in its binary representation.
2. The rest of the bits should be 0.

Different Approaches

1️⃣ Counting Set Bits

Intuition:

A number is a power of 2 if it contains exactly one set bit (1) in its binary representation. By counting the number of 1s, we can determine if the number is a power of 2.

Steps:

1. Initialize a count variable to 0.
2. Use a loop to count the number of set bits.
3. If the number of set bits is exactly 1, then it is a power of 2.

Code:

bool isPowerOfTwo(int number) {
    if (number <= 0) return false;
    int count = 0;
    while (number > 0) {
        count += (number & 1);  // Add the least significant bit
        number >>= 1;  // Right shift by 1 to move to the next bit
    }
    return count == 1;  // A power of 2 has exactly 1 set bit
}

Complexity Analysis:

• Time Complexity:O(log N), where N is the value of the number (logarithmic because of shifting).
• Space Complexity:O(1)

2️⃣ Division by 2

Intuition:

A number is a power of 2 if it can be divided by 2 repeatedly until it becomes 1. If, during this division process, the number becomes odd at any point (other than 1), it is not a power of 2.

Steps:

1. Continuously divide the number by 2.
2. If at any point the remainder is non-zero (i.e., the number is odd), return false.
3. If the number eventually becomes 1, return true.

Code:

bool isPowerOfTwo(int number) {
    if (number <= 0) return false;
    while (number > 1) {
        if (number % 2 != 0) return false;  // If number is odd and not 1, it's not a power of 2
        number /= 2;  // Divide by 2
    }
    return true;  // If number becomes 1, it is a power of 2
}

Complexity Analysis:

• Time Complexity:O(log N), where N is the value of the number (logarithmic because of division).
• Space Complexity:O(1)

3️⃣ Using Bitwise AND

Intuition:

A number that is a power of 2 has exactly one 1 bit in its binary representation. If we subtract 1 from a power of 2, all bits to the right of the only 1 bit become 1, and the only 1 bit becomes 0. The bitwise AND of the original number and the result of subtracting 1 will yield 0.

Steps:

1. Ensure the number is positive (number > 0).
2. Check the condition: number & (number - 1) == 0.

Code:

#include <iostream>

bool isPowerOf2(int num) {
    return number > 0 && (number & (number - 1)) == 0;
}

int main() {
    // Example usage
    int exampleNumber = 16;
    if (isPowerOf2(exampleNumber)) {
        std::cout << exampleNumber << " is a power of 2." << std::endl;
    } else {
        std::cout << exampleNumber << " is not a power of 2." << std::endl;
    }

    return 0;
}

// Output
16 is a power of 2.

Complexity Analysis:

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