power of 2

[Skaperen]

given an int argument, is it a power of two?

how efficiently can you code this function?

[Ofnuts]

http://www.exploringbinary.com/ten-ways-...-two-in-c/

[wavic]

>>> def is_power(num):
...     if type(num) == int:
...         if num & (num - 1) == 0:
...             return True
...         else:
...             return False

>>> is_power(8)
True

>>> is_power(3)
False

>>> is_power(16)
True

>>> is_power(2**529354)
True

[zivoni]

Just rewrite of wavric's solution:

def is_power(num):
    return isinstance(num, int) and num > 0 and num & (num - 1) == 0

[Ofnuts]

Likely nitpicking, but if you really want to compute this efficiently, it is because you are facing large numbers, so checking for int is rather limiting... Check for int or long, or better do not check and catch the exception...

[Skaperen]

the way i did it was pretty much like how wavic did it except i did not bother with the two if tests and just did it as return num&num-1==0 (variable names were changed to protect the innocent).

choosing the best algorithm is the first step of good programming (coding).

[wavic]

As I know, the integer in Python can be as long as we need.

>>> type(2**(10**6))

<class 'int'>

@Ofnuts gave a useful link. I see that the algorithm I proposed is not the fastest one.

[zivoni]

Maybe Ofnuts means something about internal representation of int? There used to be "short" ints (32 or 64bit ones) and long ints in python2, but it was unified in python3 (and long() was removed).

Python 2.7

Output:
>>> x, y = 1, 1L
>>> type(x), type(y)
(<type 'int'>, <type 'long'>)

I am not sure if performance comparison in Ofnuts' link applies to python - fastest algorithm uses binary complement and that depends on fixed bit length.  return num & num - 1 == 0 seems to perform well and its easy to understand.

[Ofnuts]

As I know, the integer in Python can be as long as we need.

>>> type(2**(10**6))

<class 'int'>

Not in Python V2

Output:
Python 2.7.6 (default, Oct 26 2016, 20:30:19) 
[GCC 4.8.4] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> type(2**(10**6))
<type 'long'>