In this blog post, I will teach you how to write C Program to check whether a given number is power of two. After reading this post you able to check whether given number is power of two or not.
But before writing the C program to how to check given number is power of 2 first let’s understand power of two.
An integer n is a power of two, if there exists an integer x such that n == 2x.
For example,
Example 1:
Input: n = 1
Output: Yes
Explanation: 20 = 1
Example 2:
Input: n = 16
Output: YES
Explanation: 24 = 16
Example 3:
Input: n = 3
Output: No
Let’s see the problem statements and constraints for this question.
Problem Statement: Given an integer n, return 1 if it is a power of two. Otherwise, return 0.
Constraints:
➤ -231 <= n <= 231 -1
Disclaimer: Try to solve the problem yourself first otherwise it would be not worth solving this problem.
Ways to check whether a given number is power of two:
- Using Bitwise operators.
- Using math library function.
- Using while loop and if statements.
Let’s discuss each of them to find whether given number is power of two or not.
C Program to check whether a given number is power of two or not:
Using bit-wise Operator:
In the below C code using the bit-wise operator and if statement I have written a function to check whether given number is power of 2 or not. This function returns 1 if number is power of 2 otherwise returns 0.
#include <stdio.h>
int checkPowerOfTwo(int num)
{
int flag;
if (num <= 0)
{
/* Zero and negative numbers
are not powers of two*/
flag = 0;
}
else
{
//Check the power of 2
flag = ((num & (num - 1)) == 0);
}
return flag ;
}
int main()
{
int num;
printf("Enter a number: ");
scanf("%d", &num);
const int isPowerOfTwo = checkPowerOfTwo(num);
if (isPowerOfTwo != 0)
{
printf("%d is a power of two.\n", num);
}
else
{
printf("%d is not a power of two.\n", num);
}
return 0;
}
output1:
Enter a number: 8 8 is a power of two.
output2:
Enter a number: 5 5 is not a power of two.
Explanation:
Reason of (num -1):
When 1 is subtracted from every power of 2 number then MSB bit flips to 0 and all preceding bits flip to 1. For example,
Consider num = 8 (binary representation: 1000). Subtracting 1 gives 7 (binary: 0111).
Reason of num & (num -1):
Arithmetic operation (num -1) produces a number which inverse to the num (if num is power of 2). So, when AND-ing num and (num-1), you will get 0 as the result. That means if the result of this operation is 0, it implies that num has only one bit set to 1 (i.e., it is a power of two).
Let’s understand the operation in detail with below expression.
n = 8
decimal | 8 = 2*2*2 | 8 - 1 = 7 | 8 & 7 = 0
| ^ | |
binary | 1 0 0 0 | 0 1 1 1 | 1 0 0 0
| ^ | | & 0 1 1 1
index | 3 2 1 0 | | -------
0 0 0 0
-----------------------------------------------------
n = 5
decimal | 5 = 2*2 + 1 | 5 - 1 = 4 | 5 & 4 = 4
| | |
binary | 1 0 1 | 1 0 0 | 1 0 1
| | | & 1 0 0
index | 2 1 0 | | ------
1 0 0
If you want, you can also optimize your function to check power of two. But generally during the writing the code my primary focus is code readability. See the few optimize function to check power of 2 of a given number.
Way-1:
int checkPowerOfTwo(int num)
{
/* Zero and negative numbers
are not powers of two*/
const int ret = (num > 0)?
((num != 0)&&((num & (num-1)) == 0)):0;
return ret ;
}
Way-2:
int checkPowerOfTwo(int num)
{
/* Zero and negative numbers
are not powers of two*/
return ((num >! 0) && (!(num & (num - 1))));
}
Way-3:
int checkPowerOfTwo(int num)
{
/* Zero and negative numbers
are not powers of two*/
return (num > 0 && ((num & (num - 1)) == 0));
}
Way-4:
Using the AND(&) and NOT(~) operator you can also check whether a given number is a power of 2 or not.
int checkPowerOfTwo(int num)
{
/* Zero and negative numbers
are not powers of two*/
return (num > 0 && ((num & (~(num - 1))) == num));
}
Using math library function:
In the below C code, we find whether a given number is a power of 2 using Log operator. Below C function returns 1 if number is power of 2 otherwise returns 0. This is a simple way to check power of 2. In this function we simply take the log of the number on base 2 and if you get an integer then the number is the power of 2.
/**
C Program to find whether a given number
is power of two using Logarithm
*/
#include <stdio.h>
#include<math.h>
//C Function to check if num is power of 2
bool checkPowerOfTwo(int num)
{
/* Zero and negative numbers
are not powers of two*/
return ((num>0) && (ceil(log2(num)) == floor(log2(num))));
}
int main()
{
int num;
printf("Enter a number: ");
scanf("%d", &num);
const int isPowerOfTwo = checkPowerOfTwo(num);
if (isPowerOfTwo != 0)
{
printf("%d is a power of two.\n", num);
}
else
{
printf("%d is not a power of two.\n", num);
}
return 0;
}
Output1:
Enter a number: 8
8 is a power of two.
Output2:
Enter a number: 5
5 is not a power of two.
Using Bit Counting:
In this C code Finding we find whether a given number is a power of 2 by checking the count of set bits.
As you know all power of two numbers has only a one-bit set. So, we will use this concept here to find a number is power of two. In the below function we count the no. of set bits. If count is 1, then the number is a power of 2.
/**
C Program to find whether a given number
is power of two using count set bit
*/
#include <stdio.h>
//C Function to count set bits in an unsigned integer
int countSetBits(unsigned int num)
{
/* Zero and negative numbers
are not powers of two*/
int cnt = 0;
// Loop until n becomes 0
while (num)
{
// Increment cnt
cnt += num & 1;
//Shift num in right by 1 to check the next bit
num >>= 1;
}
return cnt;
}
int checkPowerOfTwo(int num)
{
const int cnt = (num>0)? countSetBits(num):0;
// if cnt = 1 only then it is power of 2
return (cnt == 1);
}
int main()
{
int num;
printf("Enter a number: ");
scanf("%d", &num);
const int isPowerOfTwo = checkPowerOfTwo(num);
if (isPowerOfTwo != 0)
{
printf("%d is a power of two.\n", num);
}
else
{
printf("%d is not a power of two.\n", num);
}
return 0;
}
Output1:
Enter a number: 8.
8 is a power of two.
Output2:
Enter a number: 5.
5 is not a power of two.
Using modulo & division operator:
In this C code Finding we find whether a given number is a power of 2 by using the modulo & division operator. As you know except the 1 modulo division by 2 of a number which is power of 2 gives 0. We use this concept here.
/**
C Program to find whether a given number
is power of two using modulo & division operator
*/
#include <stdio.h>
int checkPowerOfTwo(int num)
{
if(num>0)
{
while (num % 2 == 0)
{
num /= 2;
}
}
// if num = 1 only then it is power of 2
return (num == 1);
}
int main()
{
int num;
printf("Enter a number: ");
scanf("%d", &num);
const int isPowerOfTwo = checkPowerOfTwo(num);
if (isPowerOfTwo != 0)
{
printf("%d is a power of two.\n", num);
}
else
{
printf("%d is not a power of two.\n", num);
}
return 0;
}
Recommended Post:
- C program to calculate the power of a number.
- Pow function in C.
- sqrt function in C.
- C program to find all roots of a quadratic equation using switch case.
- C program to find the roots of a quadratic equation.
- How to find whether a given number is prime number in C?
- C Program to swap two nibbles in a byte
- C Program to find first and last digit of a given number
- C program to find even and odd numbers
- C Program to find the sum of natural numbers up to n terms
- C Program to find the sum of even natural numbers from 1 to n
