DAY 67 - 231. Power of Two

Welcome to DAY 67. Today we will diverge once again into the Data Structures and look at some more questions. Today we are going to do a question on Bit Manipulation.

Question: 231. 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: 2^0 = 1

Example 2:

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

We are going to solve this problem using Bit Manipulation
Incase you don't know what's bit manipulation, It is the modification or manipulation of smallest form of data(a bit) and using their properties with bit operators to generate favorable results.

To read more about Bit Manipulation, I suggest reading it on : Bit Manipulation

Intuition:

• Let's see what the problem says. If we have to find the it's a power of 2.
• We can easily say that it should be divisible by 2 otherwise , it won't make sense.
• If we assume that it's a power of 2 and if we constantly divided it by 2. If it comes to be 1(the last thing we get) , we can say that it's divisible by 2 otherwise not.
• But I am going to tell you an easier approach than this. At least in writing efficient code.
• We must know what a binary representation looks like. For a number n say 4 it's binary representation is 0 0 1 0 0. The binary representation of (x - 1) can be simply obtained from the binary representation of x by flipping all the bits to the right of the rightmost set bit including spaces the rightmost set bit itself, so if x has only one-bit set, then x & (x-1) must be equal to 0.
• If we do their and operation , it should come out to be zero as they must have same bits now.

Algorithm Analysis and Code:

Algorithm

The algorithm uses a bitwise approach to efficiently determine whether an integer is a power of two. Here's how the provided code works:

1. isPowerOfTwo Function: The isPowerOfTwo function takes an integer n as input and returns a boolean value.
   • A long long variable ans is used to store the value of n. This is done to avoid potential integer overflow issues.
   • The expression ans & (ans - 1) is a bitwise operation that checks if ans has only a single bit set to 1.
   • If ans & (ans - 1) evaluates to 0, it means ans has only one bit set to 1, which implies that n is a power of two.
   • The ! operator is used to negate the result of (ans & (ans - 1)). So, if the result is 0 (indicating a power of two), the function returns true. Otherwise, it returns false.

Code:

class Solution {
public:
    bool isPowerOfTwo(int n) {
        long long ans = n;
        return (ans && ! (ans & (ans - 1)));
    }
};

Complexity Analysis

• The algorithm's time complexity is O(1), as it involves only a few bitwise operations that execute in constant time.
• The space complexity is O(1), as the algorithm uses only a few variables and does not depend on the input size.

Conclusion

In this article, we've analyzed an algorithm that determines whether a given integer is a power of two. By leveraging bitwise operations, the algorithm efficiently checks whether the input number has only one bit set to 1, which is a characteristic of power-of-two numbers.