Finding if a number is a power of 2 using recursion

Question

I'm trying to find whether a number is a power of 2 using recursion. However, I couldn't seem to figure out the correct solution. Here's what I've tried so far:

def is_power(n):
    n = n/2
    if n == 2:
        return True
    elif n > 2:
        is_power(n)
    else:
        return False


if is_power(32):
    print 'yes'
else:
    print 'no'

Since '32' is a power of 2, I expected my code to return 'yes' as the output. However, the code outputs 'no' instead. What seems to be wrong with my code?

Answer 1

Since I already have an accepted answer here, I'll use this one to explain a bit why your approach is bad:

It uses recursion in python. Python needs to open up a stack frame for every call, so for very large numbers, this will be a bad way of solving this. It will even fail for very large integers.

I don't even think recursion in a non-purely-functional language like python is the intuitive thing to do here. There's a million easier ways to do this; for example, a while loop:

n = int(n)
while n>1:
    if n/2 != n/2.0: #compare integer division to float division
       return False
    n = n/2
return True

Checking against power of two can be done in clever ways by realizing what the storage structure for integers on computers is: it's binary. So you could just count the binary 1s in your int's binary representation:

return bin(n).count('1') == 1

would also work. Of course, that would mean that python internally converts the integer to a string, which wastes memory on large numbers. So you might as well

power_of_2 = 1
while power_of_2 <= n:
    if power_of_2 == n:
        return True
    power_of_2 *= 2
return False

simply compares your number to all smaller-or-equal powers of two. (which of course would probably take longer and use more memory, since your python interpreter will have to interpret python instead of just converting your integer to a string in C, but this is about algorithmic principles, right?) That way, you don't need to reserve memory just to count occurencies of 1 in your binary representation.

Of course, there's a one-liner that solves your issues, and I take it from the things I've learned writing in C/C++:

bool(n and not (n&(n-1)))

To explain n and not (n&(n-1)): n is True iff n != 0, which is would otherwise falsely qualify as power of 2.

For not (n&(n-1)): n&(n-1) checks whether something is not a power of 2, so we have to invert that. & is the bitwise "and" operator. To understand n & (n-1), imagine n is a power of 2, let's say 8. So n-1 == 7, and thus

8|0b1000
7|0b0111
--------
&|0b0000

as you can see, for all powers of two, n&(n-1) is 0, which evaluates to False. For all non-powers of two, you'll don't invert all the bits when subtracting 1, so n&(n-1) != 0, which evaluates to True.

Answer 2

elif n > 2:
    is_power(n)

is missing the return:

def is_power(n):
    n = n/2
    if n == 2:
        return True
    elif n > 2:
        return is_power(n)
    else:
        return False

thus, the "first" level of is_power returns nothing (or None, depending on how you check), which leads to output of no.

@kaveman correctly pointed out is_power(2) yields the wrong result. You can fix that by halving 2 in the elif clause:

def is_power(n):
    if not n == int(n):
        return False
    n = int(n)
    if n == 1:
        return True
    elif n > 2:
        return is_power(n/2.0)
    else:
        return False

EDIT: @will pointed out that I was mixing up python2 with python3 division. Using /2.0 fixes that. Also, in comments to the question he pointed out that 1 is a power of 2. Checking against ==1 instead of ==2 fixes that issue. Also, I added an int cast, which is not necessary for the power of 2 check (since well, IEEE754 floats are base 2 after all, so powers of 2 are exactly representable), but for non-2 bases, this will make the code portable.

Answer 3

The answer provided above is wrong.

Yes it will work for powers of two, but it will also give many false positives - as you are using integer division - because you are using python 2.7.

It would work if you were using from __future__ import division, which changes the behaviour of / - but this changes its behaviour throughout the program, which may not be what you want.

for example:

print 33/2 # 16
print 32/2 # 16

however, with from __future__ import division the outputs change to the correct (or at least more intuitive) results - to get the original integer math behaviour you need to use // instead (as in python3).

So the correct answer will be more like this:

def is_power(n):
    n = n/2.0
    if n == 2:
        return True
    elif n > 2:
        return is_power(n)
    else:
        return False

Note the n= n/2.0 at the beginning.

You need to test your code works on several test cases, not just ones for which you want particular results.

Alternatively though, i would go with something like this:

def is_power(n):
  if n == 2:
    return True
  elif n%2 != 0:
    return False
  else:
    return is_power(n/2.0)

Answer 4

While this does not directly answer your question, the fastest way to implement this would be

def is_power(n):
    return ((n & (n - 1)) == 0) and n != 0

While this has been covered in a previous post by Marcus, a 'bit' more explanation may help some. The binary representation of every number and the (number-1) share at least a single 1 bit, except if the number is a power of two. Further, all negative numbers share the leading bit, so are excluded by this method.

The only exception is the number 0, which doesn't share bits with the previous number -1, and may not be viewed as a power of 2. Therefore this needs an explicit check.

The binary table for the numbers will make this clear.

> Dcml  Binary 5bit
> -15   10001
> -14   10010
> -13   10011
> -12   10100
> -11   10101
> -10   10110
> -9    10111
> -8    11000
> -7    11001
> -6    11010
> -5    11011
> -4    11100
> -3    11101
> -2    11110
> -1    11111 
>  0    00000 
>  1    00001
>  2    00010
>  3    00011
>  4    00100
>  5    00101
>  6    00110
>  7    00111
>  8    01000
>  9    01001
>  10   01010
>  11   01011
>  12   01100
>  13   01101
>  14   01110
>  15   01111
>  16   10000

No negative numbers in this signed number notation would satisfy the condition as they all share the most significant bit as 1. number 0 would satisfy the condition as 0&(any_other_number) == 0. If you need to implement this for very large numbers you may be better off using bitarrays or numpy with changed dtype. Also, this discussion may be helpful for speed of bitwise operations for on large arrays/numbers.

Answer 5

    """
    Power check if a number is a power of 2
    Negative numbers are not allowed
    """
    import math


    def is_power_of_two(num):
        """
        :type num: integer
        """
        try:
            x=0
            x = math.log10(num)/math.log10(2)
            return 2 ** x == num
        except ValueError:
            exit()

Answer 6

You can just use the power of the math library

import math

def isPowerOfTwo(n):
    if n <= 0:
        return False
    res = int(math.log(n) / math.log(2))
    return 2 ** res == n

Answer 7

This was my solution for a function which checks which number is a base of another:

def is_power_of(number, base):
  # when number is smaller than base.
  if base <= 1:
    return False
  elif number < base:
    return False
  elif  number > base:
    # keep dividing number by base.
    return is_power_of(number/base, base)
  else:
    return True

Answer 8

This will be bit informative,

counter = 0
def powoftwo(n):
    global counter
    counter+=1
    if n%2 != 0:
      return "Given Number %s is not Power of 2!"%g
    else:      
      if n==2:
        return "yes give number %s = 2**%s is power of 2!"%(g, counter)
      return powoftwo(n/2)

g = 1024
print powoftwo(g)

yes give number 1024 = 2**10 is power of 2!

Answer 9

Late to the party, though yet, another way:

import math 

def is_power_of_2(x):
    n = math.log(abs(x), 2)
    return n == int(n)