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 = 4
Input: n = 32 Output: Yes Explanation: 25 = 32
To solve the problem follow the below idea:
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
Example: Below is the implementation of the above approach:
Javascript
<script>     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))         console.log("Yes");     else        console.log("No");       if (isPowerOfTwo(64))         console.log("Yes");     else        console.log("No"); </script> |
Output:
No Yes
Time Complexity: O(1).
Auxiliary Space: O(1).
Find whether a given number is a power of 2 using the division operator:
To solve the problem follow the below idea:
Another solution is to 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.
Example 1: Below is the implementation of the above approach:
Javascript
<script> Â Â Â Â function isPowerOfTwo(n) { Â Â Â Â Â Â Â Â if (n == 0) Â Â Â Â Â Â Â Â Â Â Â Â return 0; Â Â Â Â Â Â Â Â while (n != 1) { Â Â Â Â Â Â Â Â Â Â Â Â if (n % 2 != 0) Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â return 0; Â Â Â Â Â Â Â Â Â Â Â Â n = n / 2; Â Â Â Â Â Â Â Â } Â Â Â Â Â Â Â Â return 1; Â Â Â Â } Â Â Â Â Â Â isPowerOfTwo(31) ? console.log("Yes") : console.log("No"); Â Â Â Â isPowerOfTwo(64) ? console.log("Yes") : console.log("No"); </script> |
Output:
No Yes
Time Complexity: O(log N).
Auxiliary Space: O(1).
Example 2: Below is the recursive implementation of the above approach:
Javascript
<script>     function powerOf2(n) {         // base cases         // '1' is the only odd number         // which is a power of 2(2^0)         if (n == 1)             return true;           // all other odd numbers are         // not powers of 2         else if (n % 2 != 0 ||             n == 0)             return false;           // recursive function call         return powerOf2(n / 2);     }       // Driver Code     //True     var n = 64;       //False     var m = 12;       if (powerOf2(n) == true)         console.log("True" + "\n");     else console.log("False" + "\n");       if (powerOf2(m) == true)         console.log("True" + "\n");     else        console.log("False" + "\n"); </script> |
Output:
True False
Time Complexity: O(log N).
Auxiliary Space: O(log N).
Find 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.
Example: Below is the implementation of the above approach:
Javascript
<script>     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)         console.log("Yes");     else        console.log("No");       if (isPowerofTwo(128) == true)         console.log("Yes");     else        console.log("No"); </script> |
Output:
No Yes
Time Complexity: O(N).
Auxiliary Space: O(1).
Find 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))
Example: Below is the implementation of the above approach:
Javascript
<script>     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 method     console.log(isPowerOfTwo(31) ? "Yes" : "No");     console.log((isPowerOfTwo(64) ? "Yes" : "No")); </script> |
Output:
No Yes
Time Complexity: O(1).
Auxiliary Space: O(1).
Find whether a given number is a power of 2 using the AND(&) and NOT(~) operators:
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
Example: Below is the implementation of the above approach:
Javascript
<script>     function isPowerofTwo(n) {         if (n == 0)             return false;         if ((n & (~(n - 1))) == n)             return true;         return false;     }       if (isPowerofTwo(30) == true)         console.log("Yes");     else        console.log("No");       if (isPowerofTwo(128) == true)         console.log("Yes");     else        console.log("No");</script> |
Output:
No Yes
Time Complexity: O(1).
Auxiliary Space: O(1).
Find whether a given number is a power of 2 using Brian Kernighan’s algorithm:
To solve the problem follow the below idea:
As we know that the number which will be the power of two have only one set bit, therefore when we do bitwise AND with the number which is just less than the number which can be represented as the power of (2) then the result will be 0.
Example: 4 can be represented as (2^2 ),
(4 & 3)=0 or in binary (100 & 011=0)
Example: Below is the implementation of the above approach:
Javascript
<script> Â Â Â Â function isPowerofTwo(n) { Â Â Â Â Â Â Â Â return (n != 0) && ((n & (n - 1)) == 0); Â Â Â Â } Â Â Â Â Â Â /* Function to check if x is power of 2*/Â Â Â Â if (isPowerofTwo(30)) { Â Â Â Â Â Â Â Â console.log("Yes"); Â Â Â Â } Â Â Â Â else { Â Â Â Â Â Â Â Â console.log("No"); Â Â Â Â } Â Â Â Â Â Â if (isPowerofTwo(128)) { Â Â Â Â Â Â Â Â console.log("Yes"); Â Â Â Â } Â Â Â Â else { Â Â Â Â Â Â Â Â console.log("No"); Â Â Â Â } |
Output:
No Yes
Time Complexity: O(1).
Auxiliary Space: O(1).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
