Do you think IIT Guwahati certified course can help you in your career?
Introduction
Have you ever wondered how interesting the ‘numbers’ are? They have tons of properties that aid in predicting a pattern or the development of an algorithm. Because of their multi-dimensional characteristics of being prime, composite, odd, even, etc., they are one of the favourite topics of interviewers to play with.
This blog will look at a famous interview problem, ‘Check if a Number Is Not a Power of 2?’ Intrigued? Let’s jump right on it.
Problem Statement
Given a number, say k, check if it is not a power of two. Print the result on the screen.
Explanation
A number ‘N’ can be called a power of 2 if it can be written as 2M, where "M" is an integer.
The most basic way to find if a number can be written in this form is to find its prime factors. If two is the only prime factor, then that number is a power of two.
Consider the examples that follow to understand it better.
Example
Let N = 32
Its prime factors will be 2*2*2*2*2 = 25
So, 32 is a power of 2.
Let's look at another example.
Let N = 42
Its prime factors will be 2*3*7
So, 42 is NOT a power of 2.
Now that we understand the problem, let us see how we can code it. We will start with the brute-force approach and gradually move to more optimized solutions.
Bruteforce Approach
The brute force approach repeatedly divides the number "N" by 2 until either n becomes 1 (which means n is a power of 2) or n is no longer divisible by 2 (which means n is not a power of 2).
Let us look at the algorithm we will use to code this approach.
Algorithm
The algorithm for this approach is as follows:
Start.
Take an integer n as the input and call the function to check if n is not a power of two.
Check if n is less than 1. If n is less than 1, return true. That is because any number less than 1 is not a power of two.
Use a loop to continuously divide n by 2 until n is either greater than 1 with an odd remainder or n is equal to 1.
If the result of n divided by 2 has an odd remainder, return true. The reason is if n%2 is odd, n is not divisible by two and hence is not a power of two.
If the result of n divided by 2 equals 1, return false. The reason is if n/2 = 1, n is divisible by two and hence is a power of two.
If the result is true, n is not a power of two. If the result is false, n is a power of two.
End.
Look at the following dry run for a better understanding.
Dry Run
Consider the following example.
Let us now see how we can code this approach.
Implementation in C++
#include<iostream>
using namespace std;
/*
Function to check if a
number is not a power of two.
*/
bool isNotPowerOfTwo(int n) {
/*
Negative or zero is not
considered a power of 2.
*/
if (n < 1) {
return true;
}
while (n > 1) {
// Odd numbers are not a power of 2.
if (n % 2 != 0) {
return true;
}
/*
Dividing by two until the
remainder is odd or zero.
*/
n /= 2;
}
/*
The number is a power of
two if the remainder is zero.
*/
return false;
}
int main() {
int n = 14;
/*
If the function returns true,
the number isn’t a power of two.
*/
if (isNotPowerOfTwo(n)) {
cout << n << " is not a power of two." << endl;
}
else {
cout << n << " is a power of two." << endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
Reason: The “isNotPowerOfTwo” function divides the input number N by 2 in each iteration of the while loop until n is no longer divisible by 2. The number of times N can be divided by 2 before it becomes less than or equal to one is log(n). Hence, the time complexity of the function is O(log n).
Space Complexity
O(1) is the space complexity of this code.
Reason: The “isNotPowerOfTwo” function only uses a constant amount of extra space to store the intermediate values of n and the return value. The rest of the code uses the standard input and output streams, which are part of the standard library and use a constant amount of space. Hence, the space complexity of the code is O(1).
We can also use recursion to implement this logic. Let’s find out how.
Recursive Approach
The second approach implements the same logic using recursion instead of loops. However, it will not improve the time complexity.
Algorithm
The algorithm for this approach is as follows:
Start
Call the function to check if the number is not a power of two with the input value n.
Check if n is less than 1. If it is, return true, as any number less than 1 cannot be a power of 2.
Check if n is equal to 1. If it is, return false as 1 is a power of 2.
Check if n modulo 2 equals 0. If it is, return false as the number is divisible by 2 and therefore is a power of 2.
Divide n by 2 and recursively call the function with the new value of n until it returns either true or false.
If the function returns true, n is not a power of two. If it returns false, n is a power of two.
End.
Look at the following dry run to understand the algorithm better.
Dry Run
Following is the implementation of this approach.
Implementation in C++
#include <iostream>
using namespace std;
/*
Function to check whether
a number is a power of two.
*/
bool isNotPowerOfTwo(int n) {
if (n == 1) {
return false;
}
else if (n < 1 || n % 2 != 0) {
return true;
}
return isNotPowerOfTwo(n / 2);
}
int main() {
int n = 14;
/*
If the function returns true,
the number isn’t a power of two.
*/
if (isNotPowerOfTwo(n)) {
cout << n << " is not a power of two." << endl;
}
else {
cout << n << " is a power of two." << endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
Reason: This is because, in each recursive call, the input number n is divided by 2. Therefore, the number of recursive calls is proportional to the number of times n can be divided by 2, which is log(n).
Since the time taken in each recursive call is constant, the overall time complexity of the code is O(log n).
Space Complexity
O(log n) is the space complexity of this code.
Reason: This is because, with each recursive call, a new stack frame is created, which requires a constant amount of memory. The number of recursive calls is proportional to the number of times n can be divided by 2, which is log(n).
Therefore, the overall space complexity of the code is O(log n).
The idea is to take log2() of the given number. If it is an integer, it is a power of 2; otherwise, not.
Algorithm
We will check whether a number is not a power of 2 by first calculating its log base 2 and checking if it is a whole number or not. If the log base 2 is not a whole number, the number is not a power of 2. The algorithm is as follows:
Take an integer n as input and call the function to check if the n is not a power of two.
Check if n is less than or equal to 0. If it is, return true. This is because a number less than or equal to 0 cannot be a power of 2.
Calculate the log base 2of n and store the result in a variable of data type double (here, logValue ) using the log2 function from the cmath library.
Convert the log value of the integer and store the result in an integer variable (here, integerValue) using type casting.
Compare the log value and the integer value. If they are not equal, return true. This is because if n is a power of 2, the log base 2 of n should be a whole number.
If they are equal, return false.
If the function returns true, n is not a power of two. If the function returns false, n is a power of two.
Look at the following dry run to understand better.
Dry Run
Consider the following dry run for the above approach.
Let us now look at the implementation of this logic.
Implementation in C++
#include <iostream>
#include <cmath>
using namespace std;
bool isNotPowerOfTwo(int n) {
if (n < 1) return true;
double logValue = log2(n);
int integerValue = (int) logValue;
if (logValue != integerValue) {
return true;
}
else {
return false;
}
}
int main() {
int n = 14;
/*
If the function returns true,
the number isn’t a power of two.
*/
if (isNotPowerOfTwo(n)) {
cout << n << " is not a power of two." << endl;
}
else {
cout << n << " is a power of two." << endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
Reason: The logarithmic function log2(n) is a mathematical function with a constant time complexity for a given input. The rest of the code is simple conditional statements and input/output operations that have a constant time complexity as well.
So, the overall time complexity of the code is O(1), which means it will take the same amount of time to run for any input value.
Space Complexity
O(1) is the space complexity of this code.
Reason: This code only requires a constant amount of memory regardless of the input size. Memory usage includes the memory for the variables n and any additional memory used by the standard library functions. It doesn't require any data structures or dynamic memory allocation. So, the space complexity remains constant.
Another solution to this problem can be obtained using the Brian Kerninghan algorithm.
Solution Using Brian Kernighan Algorithm
Before we get into the approach, let us first look at the binary representation of some numbers that are powers of 2.
N = 2 = 21 = 00. . .000001
N = 8 = 23 = 00. . .001000
N = 32 = 25 = 00. . .100000
We can observe that all numbers that are powers of 2 have only one set bit. Can you use this idea to implement the solution?
The basic idea is to count the number of set bits. If the number of set bits is 1, "N" is a power of 2; otherwise, it is not. You can refer to this blog to learn more about counting set bits in a number.
In this approach, we will use Brian Kernighan’s algorithm for counting the number of set bits. Before moving on to the implementation, let us first discuss Brian Kernighan’s algorithm.
Brian Kernighan’s algorithm
This algorithm is a simple and efficient algorithm for counting the number of 1 bit (also known as set bits) in the binary representation of an integer. The algorithm works by repeatedly dividing the number by 2 and counting the number of times this division results in an odd number. This count represents the number of set bits in the binary representation of the number.
The algorithm is based on the property that when an odd number is divided by 2, its least significant bit is lost, and its remaining bits are shifted to the right. We can determine the least significant by performing a Bitwise AND operation with 1.
Returning to our original problem, let’s now look at the algorithm to implement the above-discussed approach.
Algorithm
The algorithm to check if a number is not a power of 2 using Brian Kernighan’s algorithm is as follows:
Start
Take an integer n as input and call the function to check whether the number is not a power of two.
Check if the input integer "n" is less than 1 and, if so, return true. This is because a power of two should be greater than zero.
Initialize a count variable to 0.
Use a loop to keep checking the number "n."
In each iteration, perform a bitwise AND operation between "n" and (n-1). This operation unsets the rightmost set bit in the number "n."
After each iteration, increment the count by 1.
If the count is greater than 1, return true. This indicates that the number is not a power of two.
Repeat steps 4 to 6 until "n" becomes zero.
If the loop terminates, it means that only one set bit is present in the binary representation of "n." Hence, return false, indicating that "n" is a power of two.
If the function returns true, n is not a power of two. If the function returns false, n is a power of two.
Let's look at the dry run for a better understanding.
Dry Run
Consider the following dry run for the above-discussed approach.
Following is the implementation of this approach.
Implementation in C++
#include <iostream>
using namespace std;
bool isNotPowerOfTwo(int n) {
/*
If 'N' is zero, it is
not a power of two.
*/
if (n < 1) {
return true;
}
/*
The 'COUNT' variable will keep
track of the number of set bits.
*/
int count = 0;
while (n) {
n &= (n - 1);
count++;
/*
If the number of set bits exceeds 1,
"N" is not a power of two.
*/
if (count > 1) {
return true;
}
}
return false;
}
int main() {
int n = 14;
/*
If the function returns true,
the number is not a power of two.
*/
if (isNotPowerOfTwo(n)) {
cout << n << " is not a power of two." << endl;
}
else {
cout << n << " is a power of two." << endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
Reason: The bitwise operation (&) and comparison (!=) are constant-time operations, so the overall time complexity is O(1).
Space Complexity
O(1) is the space complexity of this code.
Reason: No extra data structures are used. Only a constant amount of memory is required to store temporary variables, such as the input n and the result of the bitwise operation.
Solution Using Bitwise AND Operation
If we look closely at the previous approach, whenever we do bitwise & of number ‘N’ with ‘N - 1’, we are essentially unsetting the rightmost bit of ‘N’. That is because numbers with powers of two have only one fixed bit. We can simply unset the last bit and see if the number reduces to zero. If yes, then the number is a power of 2; otherwise, it is not.
We will use the bitwise operator “&” to perform a bitwise AND operation on n and n - 1. If the result is not 0, then n is not a power of 2.
Let us look at the algorithm for this approach.
Algorithm
The algorithm for the above-stated approach is as follows:
Start
Take an integer n as input and call the function to check if the number is a power of two.
Calculate "n & (n-1)," which will perform a bitwise AND operation on "n" and "n-1." This operation will unset the least significant bit of "n" if it is set and set all bits to zero if there is only one set bit.
If the result of the expression is non-zero, the function returns true.
If the result of the expression is zero, the function returns false.
If the function returns true, n is not a power of two. Otherwise, n is a power of two.
End
Look at the following dry run for a better understanding.
Dry Run
Consider the following dry run.
Following is the implementation of this approach.
Implementation in C++
#include <iostream>
using namespace std;
bool isNotPowerOfTwo(int n) {
return ((n & (n - 1)) != 0);
}
int main() {
int n = 14;
/*
If the function returns true,
the number isn’t a power of two.
*/
if (isNotPowerOfTwo(n)) {
cout << n << " is not a power of two." << endl;
}
else {
cout << n << " is a power of two." << endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
Reason: The bitwise operation “&” and comparison != are constant-time operations, so the overall time complexity is O(1).
Space Complexity
O(1) is the space complexity of this code.
Reason: No extra data structures are used. Only a constant amount of memory is required to store temporary variables, such as the input n and the result of the bitwise operation.
Frequently Asked Questions
What is meant by the power of a number?
A number's power tells how many times it has been multiplied. Exponents are another name for powers.
How can I tell if a number is a power of two?
A number ‘N’ can be called a power of 2 if it can be written as "2M," where "M" is an integer.
How do the bitwise AND operator work?
Each bit of the first operand is compared to the corresponding bit of the second one by the bitwise AND operator (&). If both bits are 1, the result bit is also set to 1.
What is time complexity?
The amount of time an algorithm or code takes to execute each instruction is known as its time complexity.
What is space complexity?
The total memory space used by an algorithm or code, including the space of input values, is referred to as "space complexity."
Conclusion
This blog discussed different approaches to checking whether a given number is not a power of 2. We have also seen how to use the properties of the binary representation of an integer to improve the efficiency of our algorithm.
You can follow these links for more such problems.
568+ registered 
