Given a positive integer n, write a function to find if it is a power of 2 or not
Examples:
Input : n = 4
Output : Yes
Explanation: 22 = 4Input : n = 32
Output : Yes
Explanation: 25 = 32
Finding whether a given number is a power of 2 using Log operator:
A simple method for this is to simply take the log of the number on base 2 and if you get an integer then the number is the power of 2
Below is the implementation of the above approach:
C++
// C++ Program to find whether a// no is a power of two#include <bits/stdc++.h>using namespace std;// Function to check if x is power of 2bool isPowerOfTwo(int n){ if (n == 0) return false; return (ceil(log2(n)) == floor(log2(n)));}// Driver codeint main(){ // Function call isPowerOfTwo(31) ? cout << "Yes" << endl : cout << "No" << endl; isPowerOfTwo(64) ? cout << "Yes" << endl : cout << "No" << endl; return 0;}// This code is contributed by Surendra_Gangwar |
C
// C Program to find whether a// no is power of two#include <math.h>#include <stdbool.h>#include <stdio.h>/* Function to check if x is power of 2*/bool isPowerOfTwo(int n){ if (n == 0) return false; return (ceil(log2(n)) == floor(log2(n)));}// Driver codeint main(){ // Function call isPowerOfTwo(31) ? printf("Yes\n") : printf("No\n"); isPowerOfTwo(64) ? printf("Yes\n") : printf("No\n"); return 0;}// This code is contributed by bibhudhendra |
Java
// Java Program to find whether a// no is power of twoimport java.lang.Math;class GFG { /* Function to check if x is power of 2*/ static boolean isPowerOfTwo(int n) { if (n == 0) return false; return (int)(Math.ceil((Math.log(n) / Math.log(2)))) == (int)(Math.floor( ((Math.log(n) / Math.log(2))))); } // Driver Code public static void main(String[] args) { // Function call if (isPowerOfTwo(31)) System.out.println("Yes"); else System.out.println("No"); if (isPowerOfTwo(64)) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by mits |
Python3
# Python3 Program to find# whether a no is# power of twoimport math# Function to check# Log base 2def Log2(x): if x == 0: return false return (math.log10(x) / math.log10(2))# Function to check# if x is power of 2def isPowerOfTwo(n): return (math.ceil(Log2(n)) == math.floor(Log2(n)))# Driver Codeif __name__ == "__main__": # Function call if(isPowerOfTwo(31)): print("Yes") else: print("No") if(isPowerOfTwo(64)): print("Yes") else: print("No")# This code is contributed# by mits |
C#
// C# Program to find whether// a no is power of twousing System;class GFG { /* Function to check if x is power of 2*/ static bool isPowerOfTwo(int n) { if (n == 0) return false; return (int)(Math.Ceiling( (Math.Log(n) / Math.Log(2)))) == (int)(Math.Floor( ((Math.Log(n) / Math.Log(2))))); } // Driver Code public static void Main() { // Function call if (isPowerOfTwo(31)) Console.WriteLine("Yes"); else Console.WriteLine("No"); if (isPowerOfTwo(64)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed// by Akanksha Rai(Abby_akku) |
Javascript
<script>// javascript Program to find whether a// no is power of two /* Function to check if x is power of 2 */ function isPowerOfTwo(n) { if (n == 0) return false; return parseInt( (Math.ceil((Math.log(n) / Math.log(2))))) == parseInt( (Math.floor(((Math.log(n) / Math.log(2)))))); } // Driver Code if (isPowerOfTwo(31)) document.write("Yes<br/>"); else document.write("No<br/>"); if (isPowerOfTwo(64)) document.write("Yes<br/>"); else document.write("No<br/>");// This code is contributed by shikhasingrajput. </script> |
PHP
<?php// PHP Program to find // whether a no is // power of two// Function to check// Log base 2function Log2($x){ return (log10($x) / log10(2));}// Function to check// if x is power of 2function isPowerOfTwo($n){ return (ceil(Log2($n)) == floor(Log2($n)));}// Driver Code// Function callif(isPowerOfTwo(31))echo "Yes\n";elseecho "No\n";if(isPowerOfTwo(64))echo "Yes\n";elseecho "No\n"; // This code is contributed // by Sam007?> |
Output
No Yes
Time Complexity: O(1)
Auxiliary Space: O(1)
Finding whether a given number is a power of 2 using the modulo & division operator:
Keep dividing the number by two, i.e, do n = n/2 iteratively. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes 1 then it is a power of 2.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;/* Function to check if x is power of 2*/bool isPowerOfTwo(int n){ if (n == 0) return 0; while (n != 1) { if (n % 2 != 0) return 0; n = n / 2; } return 1;}// Driver codeint main(){ // Function call isPowerOfTwo(31) ? cout << "Yes\n" : cout << "No\n"; isPowerOfTwo(64) ? cout << "Yes\n" : cout << "No\n"; return 0;}// This code is contributed by rathbhupendra |
C
// C program for the above approach#include <stdbool.h>#include <stdio.h>/* Function to check if x is power of 2*/bool isPowerOfTwo(int n){ if (n == 0) return 0; while (n != 1) { if (n % 2 != 0) return 0; n = n / 2; } return 1;}// Driver codeint main(){ // Function call isPowerOfTwo(31) ? printf("Yes\n") : printf("No\n"); isPowerOfTwo(64) ? printf("Yes\n") : printf("No\n"); return 0;} |
Java
// Java program to find whether// a no is power of twoimport java.io.*;class GFG { // Function to check if // x is power of 2 static boolean isPowerOfTwo(int n) { if (n == 0) return false; while (n != 1) { if (n % 2 != 0) return false; n = n / 2; } return true; } // Driver code public static void main(String args[]) { // Function call if (isPowerOfTwo(31)) System.out.println("Yes"); else System.out.println("No"); if (isPowerOfTwo(64)) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by Nikita tiwari. |
Python3
# Python program to check if given# number is power of 2 or not# Function to check if x is power of 2def isPowerOfTwo(n): if (n == 0): return False while (n != 1): if (n % 2 != 0): return False n = n // 2 return True# Driver codeif __name__ == "__main__": # Function call if(isPowerOfTwo(31)): print('Yes') else: print('No') if(isPowerOfTwo(64)): print('Yes') else: print('No')# This code is contributed by Danish Raza |
C#
// C# program to find whether// a no is power of twousing System;class GFG { // Function to check if // x is power of 2 static bool isPowerOfTwo(int n) { if (n == 0) return false; while (n != 1) { if (n % 2 != 0) return false; n = n / 2; } return true; } // Driver code public static void Main() { // Function call Console.WriteLine(isPowerOfTwo(31) ? "Yes" : "No"); Console.WriteLine(isPowerOfTwo(64) ? "Yes" : "No"); }}// This code is contributed by Sam007 |
Javascript
<script> /* Function to check if x is power of 2*/ function isPowerOfTwo(n) { if (n == 0) return 0; while (n != 1) { if (n%2 != 0) return 0; n = n/2; } return 1; } isPowerOfTwo(31)? document.write("Yes" + "</br>"): document.write("No" + "</br>"); isPowerOfTwo(64)? document.write("Yes"): document.write("No");</script> |
PHP
<?php// php program for the above approach// Function to check if// x is power of 2function isPowerOfTwo($n){if ($n == 0) return 0;while ($n != 1){ if ($n % 2 != 0) return 0; $n = $n / 2;}return 1;}// Driver Code// Function callif(isPowerOfTwo(31)) echo "Yes\n";else echo "No\n";if(isPowerOfTwo(64)) echo "Yes\n";else echo "No\n";// This code is contributed // by Sam007?> |
Output
No Yes
Time Complexity: O(log N)
Auxiliary Space: O(1)
Finding whether a given number is a power of 2 by checking the count of set bits:
To solve the problem follow the below idea:
All power of two numbers has only a one-bit set. So count the no. of set bits and if you get 1 then the number is a power of 2. Please see Count set bits in an integer for counting set bits.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;/* Function to check if x is power of 2*/bool isPowerOfTwo(int n){ /* First x in the below expression is for the case when * x is 0 */ int cnt = 0; while (n > 0) { if ((n & 1) == 1) { cnt++; } n = n >> 1; // keep dividing n by 2 using right // shift operator } if (cnt == 1) { // if cnt = 1 only then it is power of 2 return true; } return false;}// Driver codeint main(){ // Function call isPowerOfTwo(31) ? cout << "Yes\n" : cout << "No\n"; isPowerOfTwo(64) ? cout << "Yes\n" : cout << "No\n"; return 0;}// This code is contributed by devendra salunke |
Java
// Java program of the above approachimport java.io.*;class GFG { // Function to check if x is power of 2 static boolean isPowerofTwo(int n) { int cnt = 0; while (n > 0) { if ((n & 1) == 1) { cnt++; // if n&1 == 1 keep incrementing cnt // variable } n = n >> 1; // keep dividing n by 2 using right // shift operator } if (cnt == 1) { // if cnt = 1 only then it is power of 2 return true; } return false; } // Driver code public static void main(String[] args) { // Function call if (isPowerofTwo(30) == true) System.out.println("Yes"); else System.out.println("No"); if (isPowerofTwo(128) == true) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by devendra salunke. |
Python3
# Python3 program to check if given# number is power of 2 or not# Function to check if x is power of 2def isPowerOfTwo(n): cnt = 0 while n > 0: if n & 1 == 1: cnt = cnt + 1 n = n >> 1 if cnt == 1: return 1 return 0# Driver codeif __name__ == "__main__": # Function call if(isPowerOfTwo(31)): print('Yes') else: print('No') if(isPowerOfTwo(64)): print('Yes') else: print('No')# This code is contributed by devendra salunke |
C#
// C# program to check for power for 2using System;class GFG { // Method to check if x is power of 2 static bool isPowerOfTwo(int n) { int cnt = 0; // initialize count to 0 while (n > 0) { // run loop till n > 0 if ((n & 1) == 1) { // if n&1 == 1 keep incrementing cnt // variable cnt++; } n = n >> 1; // keep dividing n by 2 using right // shift operator } if (cnt == 1) // if cnt = 1 only then it is power of 2 return true; return false; } // Driver code public static void Main() { // Function call Console.WriteLine(isPowerOfTwo(31) ? "Yes" : "No"); Console.WriteLine(isPowerOfTwo(64) ? "Yes" : "No"); }}// This code is contributed by devendra salunke |
Javascript
<script> // JavaScript code for the above approach // Function to check if x is power of 2 function isPowerofTwo(n) { let cnt = 0; while (n > 0) { if ((n & 1) == 1) { cnt++; // if n&1 == 1 keep incrementing cnt // variable } n = n >> 1; // keep dividing n by 2 using right // shift operator } if (cnt == 1) { // if cnt = 1 only then it is power of 2 return true; } return false; } // Driver code if (isPowerofTwo(30) == true) document.write("Yes" + "<br/>"); else document.write("No" + "<br/>"); if (isPowerofTwo(128) == true) document.write("Yes" + "<br/>"); else document.write("No" + "<br/>"); // This code is contributed by sanjoy_62. </script> |
Output
No Yes
Time complexity: O(log N)
Auxiliary Space: O(1)
Finding whether a given number is a power of 2 using the AND(&) operator:
To solve the problem follow the below idea:
If we subtract a power of 2 numbers by 1 then all unset bits after the only set bit become set; and the set bit becomes unset.
For example for 4 ( 100) and 16(10000), we get the following after subtracting 1
3 –> 011
15 –> 01111So, if a number n is a power of 2 then bitwise & of n and n-1 will be zero. We can say n is a power of 2 or not based on the value of n&(n-1). The expression n&(n-1) will not work when n is 0. To handle this case also, our expression will become n& (!n&(n-1)) (thanks to https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/Mohammad for adding this case).
Note: With any method which involves subtraction by 1 (just as below, ‘n-1’), some online platforms may give an error if n is given the minimum value of integer or -2147483648. Subtraction by 1 gives integer overflow error in C++.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;/* Function to check if x is power of 2*/bool isPowerOfTwo(int x){ if(x<0) return false; /* First x in the below expression is for the case when * x is 0 */ return x && (!(x & (x - 1)));}// Driver codeint main(){ // Function call isPowerOfTwo(31) ? cout << "Yes\n" : cout << "No\n"; isPowerOfTwo(64) ? cout << "Yes\n" : cout << "No\n"; return 0;}// This code is contributed by rathbhupendra |
C
// C program for the above approach#include <stdio.h>#define bool int/* Function to check if x is power of 2*/bool isPowerOfTwo(int x){ /* First x in the below expression is for the case when * x is 0 */ return x && (!(x & (x - 1)));}// Driver codeint main(){ // Function call isPowerOfTwo(31) ? printf("Yes\n") : printf("No\n"); isPowerOfTwo(64) ? printf("Yes\n") : printf("No\n"); return 0;} |
Java
// Java program for the above approachclass Test { /* Method to check if x is power of 2*/ static boolean isPowerOfTwo(int x) { /* First x in the below expression is for the case when x is 0 */ return x != 0 && ((x & (x - 1)) == 0); } // Driver code public static void main(String[] args) { // Function call System.out.println(isPowerOfTwo(31) ? "Yes" : "No"); System.out.println(isPowerOfTwo(64) ? "Yes" : "No"); }}// This program is contributed by Gaurav Miglani |
Python3
# Python3 program for the above approach# Function to check if x is power of 2def isPowerOfTwo(x): # First x in the below expression # is for the case when x is 0 return (x and (not(x & (x - 1))))# Driver codeif __name__ == "__main__": # Function call if(isPowerOfTwo(31)): print('Yes') else: print('No') if(isPowerOfTwo(64)): print('Yes') else: print('No')# This code is contributed by Danish Raza |
C#
// C# program for the above approachusing System;class GFG { // Method to check if x is power of 2 static bool isPowerOfTwo(int x) { // First x in the below expression // is for the case when x is 0 return x != 0 && ((x & (x - 1)) == 0); } // Driver code public static void Main() { // Function call Console.WriteLine(isPowerOfTwo(31) ? "Yes" : "No"); Console.WriteLine(isPowerOfTwo(64) ? "Yes" : "No"); }}// This code is contributed by Sam007 |
Javascript
<script>// JavaScript program to efficiently // check for power for 2 /* Method to check if x is power of 2*/ function isPowerOfTwo (x) { /* First x in the below expression is for the case when x is 0 */ return x!=0 && ((x&(x-1)) == 0); } // Driver methoddocument.write(isPowerOfTwo(31) ? "Yes" : "No");document.write("<br>"+(isPowerOfTwo(64) ? "Yes" : "No")); // This code is contributed by 29AjayKumar </script> |
PHP
<?php// php program for the above approach// Function to check if// x is power of 2function isPowerOfTwo ($x){// First x in the below expression// is for the case when x is 0 return $x && (!($x & ($x - 1)));}// Driver Code// Function callif(isPowerOfTwo(31)) echo "Yes\n" ;else echo "No\n";if(isPowerOfTwo(64)) echo "Yes\n" ;else echo "No\n"; // This code is contributed by Sam007?> |
Output
No Yes
Time Complexity: O(1)
Auxiliary Space: O(1)
Finding whether a given number is a power of 2 using the AND(&) and NOT(~) operator:
To solve the problem follow the below idea:
Another way is to use the logic to find the rightmost bit set of a given number and then check if (n & (~(n-1))) is equal to n or not
Note: With any method which involves subtraction by 1 (just as below, ‘n-1’), some online platforms may give an error if n is given the minimum value of integer or -2147483648. Subtraction by 1 gives integer overflow error in C++.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;/* Function to check if x is power of 2*/bool isPowerofTwo(long long n){ if (n <= 0) return 0; if ((n & (~(n - 1))) == n) return 1; return 0;}// Driver codeint main(){ // Function call isPowerofTwo(30) ? cout << "Yes\n" : cout << "No\n"; isPowerofTwo(128) ? cout << "Yes\n" : cout << "No\n"; return 0;}// This code is contributed by Sachin |
Java
// Java program of the above approachimport java.io.*;class GFG { // Function to check if x is power of 2 static boolean isPowerofTwo(int n) { if (n == 0) return false; if ((n & (~(n - 1))) == n) return true; return false; } // Driver code public static void main(String[] args) { // Function call if (isPowerofTwo(30) == true) System.out.println("Yes"); else System.out.println("No"); if (isPowerofTwo(128) == true) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by rajsanghavi9. |
Python3
# Python program of the above approach# Function to check if x is power of 2*/def isPowerofTwo(n): if (n == 0): return 0 if ((n & (~(n - 1))) == n): return 1 return 0# Driver codeif __name__ == "__main__": # Function call if(isPowerofTwo(30)): print('Yes') else: print('No') if(isPowerofTwo(128)): print('Yes') else: print('No')# This code is contributed by shivanisinghss2110 |
C#
// C# program of the above approachusing System;public class GFG { // Function to check if x is power of 2 static bool isPowerofTwo(int n) { if (n == 0) return false; if ((n & (~(n - 1))) == n) return true; return false; } // Driver code public static void Main(String[] args) { // Function call if (isPowerofTwo(30) == true) Console.WriteLine("Yes"); else Console.WriteLine("No"); if (isPowerofTwo(128) == true) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code contributed by gauravrajput1 |
Javascript
<script>// javascript program of the above approach // Function to check if x is power of 2 function isPowerofTwo(n) { if (n == 0) return false; if ((n & (~(n - 1))) == n) return true; return false; } if (isPowerofTwo(30) == true) document.write("Yes<br/>"); else document.write("No<br/>"); if (isPowerofTwo(128) == true) document.write("Yes<br/>"); else document.write("No<br/>"); // This code is contributed by umadevi9616</script> |
Output
No Yes
Time complexity: O(1)
Auxiliary Space: O(1)
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
