Find Wether a Given Number is Power of 2.

Determining if a number is a power of 2 is a common problem in computer science and programming. A number is considered a power of 2 if it can be expressed as 2^n, where n is a non-negative integer. For example, the numbers 1, 2, 4, 8, 16, and so on are all powers of 2.

In this post, we will explore two approaches to solve this problem: the normal approach and the bitwise approach.

Problem: Given an integer n, determine whether it is a power of two.

Example:

Input:  8  
Output: true  
Explanation: 8 = 2^3 → It is a power of 2

Input:  6  
Output: false  
Explanation: 6 is not a power of 2

Approach 1: Brute Force Loop.

Keep dividing the number by 2. If at the end, you reach 1, then it's a power of 2.

If at any point, it's not divisible by 2, return false.

Steps:

If n == 0, return false
While n % 2 == 0, divide n by 2
If n == 1 after loop → power of 2

Example Code:


        // C++ Example: Find Power of 2
#include <iostream>
using namespace std;

bool isPowerOfTwoLoop(int n) {
    if (n <= 0) return false; 
    while (n % 2 == 0) { 
        n = n / 2; 
    }
    return n == 1; 
}

int main() {
    int number;
    cout << "Enter a number: ";
    cin >> number;

    if (isPowerOfTwoLoop(number)) {
        cout << number << " is a power of 2." << endl;
    } else {
        cout << number << " is not a power of 2." << endl;
    }

    return 0;
}


        #Python Example: Find Power of 2
def is_power_of_two_loop(n: int) -> bool:
    if n <= 0:
        return False
    while n % 2 == 0:
        n = n // 2
    return n == 1

# Example usage
if __name__ == "__main__":
    number = int(input("Enter a number: "))
    if is_power_of_two_loop(number):
        print(f"{number} is a power of 2.")
    else:
        print(f"{number} is not a power of 2.")


        //Java Example: Find Power of 2
import java.util.Scanner;

public class PowerOfTwo {
    public static boolean isPowerOfTwoLoop(int n) {
        if (n <= 0) return false;
        while (n % 2 == 0) {
            n = n / 2;
        }
        return n == 1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int number = scanner.nextInt();

        if (isPowerOfTwoLoop(number)) {
            System.out.println(number + " is a power of 2.");
        } else {
            System.out.println(number + " is not a power of 2.");
        }

        scanner.close();
    }
}

Output:

8 is a power of 2.

Time Complexity: O(log n)
Space Complexity: O(1)

Approach 2: Bit Manipulation Approach.

A number is a power of two if it can be expressed as 2^n, where n is a non-negative integer. In binary representation, powers of two have a unique property: they have exactly one bit set to 1.

For example:

1 = 0001 → 2^0

2 = 0010 → 2^1

4 = 0100 → 2^2

8 = 1000 → 2^3

16 = 10000 → 2^4

This property allows us to efficiently check if a number is a power of two using bit manipulation.

To determine if a number n is a power of two using bit manipulation, we can use the following approach:

1. Check if n is greater than zero: Powers of two are positive numbers.

2. Use the expression (n&(n-1): This expression will be zero if n is a power of two. The reason behind this is that subtracting 1 from a power of two flips all the bits after the rightmost set bit (the only 1 in the binary representation). For example:

For n = 4 (0100), n-1 = 3 (0011)
The bitwise AND operation: 0100 & 0011 = 0000

Now, let's implement this logic in C++, Python, and Java.

Example Code:


        #include <iostream>

bool isPowerOfTwo(int n) {
    return (n > 0) && ((n & (n - 1)) == 0);
}

int main() {
    int number = 8;
    if (isPowerOfTwo(number)) {
        std::cout << number << " is a power of two." << std::endl;
    } else {
        std::cout << number << " is not a power of two." << std::endl;
    }
    return 0;
}


        # Find Wether a number is Power of 2 Using Bitwise Operator
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

number = 8
if is_power_of_two(number):
    print(f"{number} is a power of two.")
else:
    print(f"{number} is not a power of two.")


        // Java Code to Find if a number is power of 2 using bitwise Operator
public class PowerOfTwo {
    public static boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }

    public static void main(String[] args) {
        int number = 8;
        if (isPowerOfTwo(number)) {
            System.out.println(number + " is a power of two.");
        } else {
            System.out.println(number + " is not a power of two.");
        }
    }
}

Output:

8 is a power of two.

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

Find Wether a Given Number is Power of 2.

Approach 1: Brute Force Loop.

Approach 2: Bit Manipulation Approach.

No comments:

Post a Comment