Check if a given number is power of 2
Given a number N, we will have to check if N is a power of 2. Powers of 2 include 1,2,4,8,16,32… and so on. Following are FIVE different approaches to solve the problem.
I. This is the shortest method. We perform bitwise AND operation on the given number N and N-1. If the result is 0, then N is a power of 2. If the result is non-zero, it’s not a power of two.
int power_of_two(int n)
{
return !(n&(n-1));
}
II. This method uses the basic definition of a logarithmic function. For N to be a power of 2,(log N to the base 2) must be a whole number and not a fraction.
int power_of_two(int n)
{
float x;
x=log(n)/log(2);
if(x-(int)x==0.0) return 1;
else return 0;
}
III. This method makes use of the fact that any number that is a power of 2, has exactly ONE 1s in its binary representation. Hence the above code just counts the no. of ones in the binary representation of the given number.
int power_of_two(int n)
{
int count=0,rem;
while(n>0)
{
rem=n%2;
if(rem==1||n==1) count++;
if(count>=2) break;
n=n/2;
}
if(count==1) return 1;
else return 0;
}
IV. This is a brute-force method which generates powers of two and checks if it is equal to the given number N.
int power_of_two(int n)
{
int count=0,temp;
do
{
temp=(int)pow(2,count);
if(temp==n) return 1;
count++;
}while( temp < n );
return 0;
}
V. This is a recursive implementation. When a number N which is a power of two is divided by 2, the quotient obtained will also be a power of two.
int power_of_two(int n)
{
if(n==1) return 1;
if(n%2!=0) return 0;
if(!(power_of_two(n/2))) return 0;
}
