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?

Solution 1

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.

Solution 2

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.

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

Solution 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.

Solution 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()

View more solutions

Comments

[kaveman]

While you are correct about the missing return, there is still an error with this implementation. What happens when you run is_power(2)

[kaveman]

why not just fix your implementation, so as not to confuse the OP and future readers?

[Manas Chaturvedi]

Yea, I was missing the 'return'. Thanks for pointing that out !

[will]

Your answer is wrong - see mine below. Try your function on some numbers it should return false for - i.e. 5,9,10,11,17,18,19,20,21,22,23,33,34,35,36,37,38,39,40,...

[Marcus Müller]

@will., you're right. I thought I saw a python3.4 tag, but I was wrong. So, yes, I'll have an edit, which will fix this.

[Marcus Müller]

excellent answer, and definitely a better approach than OPs, so well worthy of upvoting :) Only thing is that when using the % operator, we might as well just take the bitwise comparison operators, and use a one-step approach: return not (n & (n-1)). The nice thing about python is that it has a working implementation for "infinitely large integers", so this even works for very large values (e.g. 2**100 -1).

[will]

@MarcusMüller I don't agree with rolling it all into that n&(n-1) construct - unless you put a detailed comment along with it detailing what is going on.

[mrgloom]

This if n/2 != n/2.0: will fail in python 3, it can be modified as if n // 2 != n / 2