How do you check if a no is power of 2 in python?

Question

Bit Manipulations

One approach would be to use bit manipulations:

Nội dung chính Show

Bit Manipulations
math functions
(Expanded) Timing
Find whether a given number is a power of 2 using logarithm:
Find whether a given number is a power of 2 using the division operator:
Find whether a given number is a power of 2 by checking the count of set bits:
Find whether a given number is a power of 2 using the AND(&) operator:
Find whether a given number is a power of 2 using the AND(&) and NOT(~) operator:
Find whether a given number is a power of 2 using Brian Kernighan’s algorithm:
How do you check if a number is a power of 2?
How do you write to the power of 2 in Python?
How do you evaluate a power in Python?
How do you check if a number is a power of 4 in Python?

(n & (n-1) == 0) and n != 0

Explanation: every power of 2 has exactly 1 bit set to 1 (the bit in that number's log base-2 index). So when subtracting 1 from it, that bit flips to 0 and all preceding bits flip to 1. That makes these 2 numbers the inverse of each other so when AND-ing them, we will get 0 as the result.

For example:

                    n = 8

decimal |   8 = 2**3   |  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

So, in conclusion, whenever we subtract one from a number, AND the result with the number itself, and that becomes 0 - that number is a power of 2!

Of course, AND-ing anything with 0 will give 0, so we add the check for n != 0.

math functions

You could always use math functions, but notice that using them without care could cause incorrect results:

math.log(x[, base]) with base=2:

import math

math.log(n, 2).is_integer()

math.log2(x):
```
math.log2(n).is_integer()
```

Worth noting that for any n <= 0, both functions will throw a ValueError as it is mathematically undefined (and therefore shouldn't present a logical problem).

math.frexp(x):
```
abs(math.frexp(n)[0]) == 0.5
```

As noted above, for some numbers these functions are not accurate and actually give FALSE RESULTS:

math.log(2**29, 2).is_integer() will give False
math.log2(2**49-1).is_integer() will give True
math.frexp(2**53+1)[0] == 0.5 will give True!!

This is because math functions use floats, and those have an inherent accuracy problem.

(Expanded) Timing

Some time has passed since this question was asked and some new answers came up with the years. I decided to expand the timing to include all of them.

According to the math docs, the log with a given base, actually calculates log(x)/log(base) which is obviously slow. log2 is said to be more accurate, and probably more efficient. Bit manipulations are simple operations, not calling any functions.

So the results are:

Ev: 0.28 sec
log with base=2: 0.26 sec
count_1: 0.21 sec
check_1: 0.2 sec
frexp: 0.19 sec
log2: 0.1 sec
bit ops: 0.08 sec

The code I used for these measures can be recreated in this REPL (forked from this one).

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

Find whether a given number is a power of 2 using logarithm:

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

Below is the implementation of the above approach:

C++

#include

using namespace std;

bool isPowerOfTwo(int n)

{

if (n == 0)

return false;

return (ceil(log2(n)) == floor(log2(n)));

}

int main()

{

isPowerOfTwo(31) ? cout << "Yes" << endl

: cout << "No" << endl;

isPowerOfTwo(64) ? cout << "Yes" << endl

: cout << "No" << endl;

return 0;

}

C

#include

bool isPowerOfTwo(int n)

{

if (n == 0)

return false;

return (ceil(log2(n)) == floor(log2(n)));

}

int main()

{

isPowerOfTwo(31) ? printf("Yes\n") : printf("No\n");

isPowerOfTwo(64) ? printf("Yes\n") : printf("No\n");

return 0;

}

Java

import java.lang.Math;

class GFG {

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)))));

}

public static void main(String[] args)

{

if (isPowerOfTwo(31))

System.out.println("Yes");

else

System.out.println("No");

if (isPowerOfTwo(64))

System.out.println("Yes");

else

System.out.println("No");

}

Python3

import math

def Log2(x):

if x == 0:

return false

return (math.log10(x) /

math.log10(2))

def isPowerOfTwo(n):

return (math.ceil(Log2(n)) ==

math.floor(Log2(n)))

if __name__ == "__main__":

if(isPowerOfTwo(31)):

print("Yes")

else:

print("No")

if(isPowerOfTwo(64)):

print("Yes")

else:

print("No")

C#

using System;

class GFG {

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)))));

}

public static void Main()

{

if (isPowerOfTwo(31))

Console.WriteLine("Yes");

else

Console.WriteLine("No");

if (isPowerOfTwo(64))

Console.WriteLine("Yes");

else

Console.WriteLine("No");

}

PHP

function Log2($x)

{

return (log10($x) /

log10(2));

}

function isPowerOfTwo($n)

{

return (ceil(Log2($n)) ==

floor(Log2($n)));

}

if(isPowerOfTwo(31))

echo "Yes\n";

else

echo "No\n";

if(isPowerOfTwo(64))

echo "Yes\n";

else

echo "No\n";

?>

`Javascript`

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.

Below is the implementation of the above approach:

`C++`

#include

using namespace std;

bool isPowerOfTwo(int n)

{

if (n == 0)

return 0;

while (n != 1) {

if (n % 2 != 0)

return 0;

n = n / 2;

}

return 1;

}

int main()

{

isPowerOfTwo(31) ? cout << "Yes\n" : cout << "No\n";

isPowerOfTwo(64) ? cout << "Yes\n" : cout << "No\n";

return 0;

}


C
#include 
#include 
bool isPowerOfTwo(int n)
{
    if (n == 0)
        return 0;
    while (n != 1) {
        if (n % 2 != 0)
            return 0;
        n = n / 2;
    }
    return 1;
}
int main()
{
    isPowerOfTwo(31) ? printf("Yes\n") : printf("No\n");
    isPowerOfTwo(64) ? printf("Yes\n") : printf("No\n");
    return 0;
}
Java
import java.io.*;
class GFG {
    static boolean isPowerOfTwo(int n)
    {
        if (n == 0)
            return false;
        while (n != 1) {
            if (n % 2
!= 0)



                return false;
            n = n / 2;
        }
        return true;
    }
    public static void main(String args[])
    {
        if (isPowerOfTwo(31))
            System.out.println("Yes");
        else
            System.out.println("No");
        if (isPowerOfTwo(64))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
Python3
def isPowerOfTwo(n):
    if (n == 0):
        return False
    while (n != 1):
        if (n % 2 != 0):
            return False
        n = n //
2
    return True
if __name__ == "__main__":
    if(isPowerOfTwo(31)):
        print('Yes')
    else:
        print('No')
    if(isPowerOfTwo(64)):
        print('Yes')
    else:
        print('No')
C#
using
System;
class GFG {
    static bool isPowerOfTwo(int n)
    {
        if (n == 0)
            return false;
        while (n != 1) {
            if (n % 2 != 0)
                return false;
            n = n / 2;
        }
        return true;
    }
    public static void Main()
    {
        Console.WriteLine(isPowerOfTwo(31) ? "Yes"
: "No");
        Console.WriteLine(isPowerOfTwo(64) ? "Yes" : "No");
    }
}
PHP
function isPowerOfTwo($n)
{
if ($n == 0)
    return 0;
while ($n != 1)
{
    if ($n % 2 != 0)
        return 0;
    $n = $n / 2;
}
return 1;
}
if(isPowerOfTwo(31))
    echo "Yes\n";
else
    echo "No\n";
if(isPowerOfTwo(64))
    echo "Yes\n";
else
    echo "No\n";
?>
Javascript
Time Complexity: O(log N)
Auxiliary Space: O(1)
Below is the recursive
implementation of the above approach:
C++
#include 
using namespace std;
bool powerOf2(int n)
{
    if (n == 1)
        return true;
    else if (n % 2 != 0 || n == 0)
        return false;
    return powerOf2(n / 2);
}
int main()
{
    int n = 64; 
    int m = 12; 
    if
(powerOf2(n) == 1)
        cout << "True" << endl;
    else
        cout << "False" << endl;
    if (powerOf2(m) == 1)
        cout << "True" << endl;
    else
        cout << "False" << endl;
}
C
#include 
#include 
bool powerOf2(int n)
{
    if (n == 1)
        return true;
    else if
(n % 2 != 0 || n == 0)
        return false;
    return powerOf2(n / 2);
}
int main()
{
    int n = 64; 
    int m = 12; 
    if (powerOf2(n) == 1)
        printf("True\n");
    else
        printf("False\n");
    if (powerOf2(m) == 1)
        printf("True\n");
    else
        printf("False\n");
}
Java
import java.util.*;
class GFG {
    static boolean powerOf2(int n)
    {
        if (n == 1)
            return true;
        else if (n % 2 != 0 || n == 0)
            return false;
        return powerOf2(n / 2);
    }
    public
static void main(String[] args)
    {
        int n = 64;
        int m = 12;
        if (powerOf2(n) == true)
            System.out.print("True"
                             + "\n");
        else
            System.out.print("False"
                             + "\n");
        if (powerOf2(m) == true)
            System.out.print("True"
                             + "\n");
        else
            System.out.print("False"
                             + "\n");
    }
}
Python3
def powerof2(n):
    if n == 1:
        return True
    elif n % 2 != 0 or n == 0:
        return False
    return powerof2(n/2)

if __name__ == "__main__":
    print(powerof2(64))  
    print(powerof2(12))  
C#
using System;
class GFG {
    static bool powerOf2(int n)
    {
        if (n == 1)
            return true;
        else if (n % 2 != 0 || n == 0)
            return false;
        return
powerOf2(n / 2);
    }
    static void Main()
    {
        int n = 64; 
        int m = 12; 
        if (powerOf2(n)) {
            Console.Write("True"
                          + "\n");
        }
        else {
            Console.Write("False"
                          + "\n");
        }
        if (powerOf2(m)) {
            Console.Write("True");
        }
        else {
            Console.Write("False");
        }
    }
}
Javascript

return true;

else if (n % 2 != 0 ||

n ==0)

return false;

return powerOf2(n / 2);

}

var n = 64;

var m = 12;

if (powerOf2(n) == true)

document.write("True" + "\n");

else document.write("False" + "\n");

if (powerOf2(m) == true)

document.write("True" + "\n");

else

document.write("False" + "\n");

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.

Below is the implementation of the above approach:

`C++`

#include

using namespace std;

bool isPowerOfTwo(int n)

{

int cnt = 0;

while (n > 0) {

if ((n & 1) == 1) {

cnt++;

}

n = n >> 1;

}

if (cnt == 1) {

return true;

}

return false;

}

int main()

{

isPowerOfTwo(31) ? cout << "Yes\n" : cout << "No\n";

isPowerOfTwo(64) ? cout << "Yes\n" : cout << "No\n";

return 0;

}

`Java`

import java.io.*;

class GFG {

static boolean isPowerofTwo(int n)

{

int cnt = 0;

while (n > 0) {

if ((n & 1) == 1) {


                cnt++; 
            }
            n = n >> 1; 
        }
        if (cnt == 1) {
            return true;
        }
        return false;
    }
    public static void main(String[] args)
    {
        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");
    }
}
C#
using System;
class GFG {
    static bool isPowerOfTwo(int n)
    {
        int cnt = 0; 
        while (n > 0) {
            if ((n & 1) == 1) {
                cnt++;
            }
            n = n >> 1; 
        }
        if (cnt
            == 1) 
            return true;
        return false;
    }
    public static void Main()
    {
        Console.WriteLine(isPowerOfTwo(31) ? "Yes" : "No");
        Console.WriteLine(isPowerOfTwo(64) ? "Yes" : "No");
    }
}
Python3

def isPowerOfTwo(n):
    cnt = 0
    while n > 0:
        if n & 1 == 1:
            cnt = cnt + 1
        n = n >> 1
    if cnt == 1:
        return 1
    return 0
if __name__ == "__main__":
    if(isPowerOfTwo(31)):
        print('Yes')
    else:
        print('No')
    if(isPowerOfTwo(64)):
        print('Yes')
    else:
        print('No')
Javascript
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 –> 01111
So, 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). 
Below is the implementation of the above approach:
C++
#include 
using namespace std;
bool isPowerOfTwo(int x)
{
    return x && (!(x & (x - 1)));
}
int
main()
{
    isPowerOfTwo(31) ? cout << "Yes\n" : cout << "No\n";
    isPowerOfTwo(64) ? cout << "Yes\n" : cout << "No\n";
    return 0;
}
C
#include 
#define bool int
bool isPowerOfTwo(int x)
{
    return x && (!(x & (x - 1)));
}
int main()
{
    isPowerOfTwo(31) ? printf("Yes\n") : printf("No\n");
    isPowerOfTwo(64) ? printf("Yes\n") : printf("No\n");
    return 0;
}
Java
class Test {
    static boolean isPowerOfTwo(int x)
    {
        return x != 0 && ((x & (x - 1)) == 0);
    }
    public static void main(String[] args)
    {
        System.out.println(isPowerOfTwo(31) ? "Yes" : "No");
        System.out.println(isPowerOfTwo(64) ? "Yes"
: "No");
    }
}
Python3
def isPowerOfTwo(x):
    return (x and (not(x & (x - 1))))
if __name__ == "__main__":
    if(isPowerOfTwo(31)):
        print('Yes')
    else:
        print('No')
    if(isPowerOfTwo(64)):
        print('Yes')
    else:
        print('No')
C#
using System;
class GFG {
    static bool isPowerOfTwo(int x)
    {
        return x != 0 && ((x & (x - 1)) == 0);
    }
    public static void Main()
    {
        Console.WriteLine(isPowerOfTwo(31) ? "Yes" : "No");
        Console.WriteLine(isPowerOfTwo(64) ? "Yes"
: "No");
    }
}
PHP
function isPowerOfTwo ($x)
{
return $x && (!($x & ($x - 1)));
}
if(isPowerOfTwo(31))
    echo "Yes\n" ;
else
    echo "No\n";
if(isPowerOfTwo(64))



    echo "Yes\n" ;
else
    echo
"No\n";
?>
Javascript
Time Complexity: O(1)
Auxiliary Space: O(1)
Find 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
Below is the implementation of the above approach:
C++
#include 
using namespace std;
bool isPowerofTwo(long long n)
{
    if (n == 0)
        return
0;
    if ((n & (~(n - 1))) == n)
        return 1;
    return 0;
}
int main()
{
    isPowerofTwo(30) ? cout << "Yes\n" : cout << "No\n";
    isPowerofTwo(128) ? cout << "Yes\n" : cout << "No\n";
    return 0;
}
Java
import java.io.*;
class GFG {
    static boolean isPowerofTwo(int n)
    {

        if (n == 0)
            return false;
        if ((n & (~(n - 1))) == n)
            return true;
        return false;
    }
    public static void main(String[] args)
    {
        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");
    }
}
Python3
def isPowerofTwo(n):
    if (n == 0):
        return 0
    if ((n & (~(n - 1))) == n):
        return 1
    return
0
if __name__ == "__main__":
    if(isPowerofTwo(30)):
        print('Yes')
    else:
        print('No')
    if(isPowerofTwo(128)):
        print('Yes')
    else:
        print('No')
C#
using System;
public
class GFG {
    static bool isPowerofTwo(int n)
    {
        if (n == 0)
            return false;
        if ((n & (~(n - 1))) == n)
            return true;
        return false;
    }
    public static void Main(String[] args)
    {
        if (isPowerofTwo(30) == true)
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
        if (isPowerofTwo(128) == true)
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
Javascript
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)
Below is the implementation of the above approach:
C++
#include 
using namespace std;
bool isPowerofTwo(long long n)
{
    return (n != 0) && ((n & (n - 1)) == 0);
}
int main()
{
    isPowerofTwo(30) ? cout << "Yes\n" : cout << "No\n";
    isPowerofTwo(128) ? cout << "Yes\n" : cout << "No\n";
    return
0;
}
Java
import java.io.*;
class GFG {
    public static boolean isPowerofTwo(long n)
    {
        return (n != 0) && ((n & (n - 1)) == 0);
    }
    public static void main(String[] args)
    {
        if (isPowerofTwo(30)) {
            System.out.println("Yes");
        }
        else {
            System.out.println("No");
        }
        if (isPowerofTwo(128)) {
            System.out.println("Yes");
        }
        else {
            System.out.println("No");
        }
    }
}
Python3
def isPowerofTwo(n):
    return (n != 0) and ((n & (n -
1)) == 0)
if __name__ == "__main__":
    if isPowerofTwo(30):
        print("Yes")
    else:
        print("No")
    if isPowerofTwo(128):
        print("Yes")
    else:
        print("No")
C#
using System;
public class GFG {
    static public bool isPowerofTwo(ulong n)
    {
        return (n != 0) && ((n & (n - 1)) == 0);
    }
    static public void Main()
    {
        if (isPowerofTwo(30)) {
            System.Console.WriteLine("Yes");
        }
        else {
            System.Console.WriteLine("No");
        }
        if
(isPowerofTwo(128)) {
            System.Console.WriteLine("Yes");
        }
        else {
            System.Console.WriteLine("No");
        }
    }
}
Javascript
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. 

 
How do you check if a number is a power of 2?
To check if a given number is a power of 2, we can continuously divide the number by 2, on the condition that the given number is even. After the last possible division, if the value of the number is equal to 1, it is a power of 2.
How do you write to the power of 2 in Python?
The power operator ( ** ) raises the left value to the power of the second value. For example: 2 ** 3 . The built-in pow() function does the same thing: it raises its first argument to the power of its second argument. Like this: pow(2, 3) .
How do you evaluate a power in Python?
Python pow() Function
The pow() function returns the value of x to the power of y (x^y). If a third parameter is present, it returns x to the power of y, modulus z.
How do you check if a number is a power of 4 in Python?
public static void main(String[] args).
 { int n = 256;.
 if (checkPowerOf4(n)) { System. out. println(n + " is a power of 4");.
 } else {.
 System. out. println(n + " is not a power of 4"); }.

programming python Is float Python

How do you check if a no is power of 2 in python?

Bit Manipulations

math functions

(Expanded) Timing

Find whether a given number is a power of 2 using logarithm:

C++

C

Java

Python3

C#

PHP

Javascript

Find whether a given number is a power of 2 using the division operator:

C++

C

Java

Python3

C#

PHP

Javascript

Below is the recursive implementation of the above approach:

C++

C

Java

Python3

C#

Javascript

Find whether a given number is a power of 2 by checking the count of set bits:

C++

Java

C#

Python3

Javascript

Find whether a given number is a power of 2 using the AND(&) operator:

C++

C

Java

Python3

C#

PHP

Javascript

Find whether a given number is a power of 2 using the AND(&) and NOT(~) operator:

C++

Java

Python3

C#

Javascript

Find whether a given number is a power of 2 using Brian Kernighan’s algorithm:

C++

Java

Python3

C#

Javascript

How do you check if a number is a power of 2?

How do you write to the power of 2 in Python?

How do you evaluate a power in Python?

How do you check if a number is a power of 4 in Python?

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội

`Javascript`

`Find whether a given number is a power of 2 using the division operator:`

`C++`

`Javascript`

`Below is the recursive implementation of the above approach:`

`C++`

`C`

`Java`

`Python3`

`Find whether a given number is a power of 2 by checking the count of set bits:`

`C++`

`Java`

`Javascript`

`Find whether a given number is a power of 2 using the AND(&) and NOT(~) operator:`

`C++`

`Java`