Check if Number is Power of Two

Welcome to another exciting lesson on CodeYourCraft! Today, we're going to dive into the world of data structures and algorithms and learn how to check if a number is a power of two. Let's get started! 🎯

What is a Power of Two?

In mathematics, a number is called a power of two if it can be written as 2 raised to some positive integer power. For example, 2, 4, 8, 16, 32, 64, and so on, are powers of two.

Why Check if a Number is a Power of Two?

Knowing whether a number is a power of two is essential in various areas of computer science, such as programming, algorithms, and data structures. It is used in bit manipulation, optimization, and solving certain mathematical problems.

Algorithm to Check if a Number is a Power of Two

Here's a simple and efficient algorithm to check if a number is a power of two. We'll implement this algorithm using two different methods, so you can understand the concept better.

Method 1: Bitwise Operators

The bitwise operators allow us to perform operations on the individual bits of a number. We can use them to check if a number is a power of two. Let's see how!

python

def isPowerOfTwo(n):
    if n <= 0:
        return False

    # Check if the last bit (rightmost bit) is set
    return (n & 1) == 0

📝 Note: In Python, the bitwise AND operator is represented by &.

💡 Pro Tip: If you're not familiar with bitwise operators, take a moment to learn about them, as they are a powerful tool in programming.

How it Works

We first check if the number n is less than or equal to 0. If it is, we return False, as a power of two cannot be less than or equal to 0.
Next, we perform a bitwise AND operation between n and 1. This operation will set all the bits to 0 except for the rightmost bit. If the rightmost bit is 0, it means that n is not a power of two. If the rightmost bit is 1, it means that n is a power of two.
Finally, we check if the result of the bitwise AND operation is equal to 0. If it is, we return True, indicating that n is a power of two. Otherwise, we return False.

Method 2: Recursive Approach

We can also check if a number is a power of two using a recursive approach.

python

def isPowerOfTwo(n):
    if n <= 0:
        return False

    if n == 1:
        return True

    return isPowerOfTwo(n >> 1)

How it Works

We first check if n is less than or equal to 0. If it is, we return False, as a power of two cannot be less than or equal to 0.
If n is equal to 1, we return True, as 1 is a power of two.
If n is greater than 1, we recursively call the isPowerOfTwo function with the right-shifted version of n. Right shifting a number by one bit moves the rightmost bit to the leftmost bit and removes all other bits. This operation effectively halves the number. If n was a power of two, the right-shifted version will be 0 or 1, and the recursive call will return the correct result.

Quiz Time!

Wrapping Up

In this lesson, we learned about powers of two and how to check if a number is a power of two using bitwise operators and a recursive approach. You can use this knowledge to optimize your code and solve various mathematical problems.

We hope you found this lesson informative and engaging. Stay tuned for more exciting topics on CodeYourCraft! ✅

In addition to these two methods, you can also implement the algorithm using loops, but the bitwise operator and recursive methods are more efficient and practical for real-world projects.

The types related to this topic are integers, bitwise operators, and recursion. Make sure to study these topics in-depth to master the concept of checking if a number is a power of two.

Happy coding! 💡🎯