Tuesday, May 1, 2012

Power of 2

As part of an event, I had to come up with a number of problems to be solved in Python.  One was to write a procedure to determine if a number is a power of two.  I supplied answers for the judges and for this problem I provided:

def is_power_of_2(x):
while x > 1 and (x % 2 == 0):
x = x//2
return x == 1

and

import math
def is_power_of_2(x):
return not (math.log(x, 2) % 1)

But one of the participants came up with a solution that I hadn't thought of and for some reason appeals to me the most out of the three.  This is my version:

def is_power_of_2(x):
s = bin(x)[2:]
return s[0] == "1" and s[1:] == "0"*len(s[1:])

bin is built into the language, but I've never used it and had actually forgotten that it existed.

Let me know if you have other ways of solving this that do not involve pre-computing large sets of data in advance.

1. def power_of_two(n):
return True if n&(n-1)==0 else False

1. Very nice and the most logical. My new favorite.

2. isn't that the same as

def power_of_two(n):
return n&(n-1)==0

Also, this returns True for 0 :p

2. # https://engineering.purdue.edu/kak/dist/BitVector-3.1.html
from BitVector import BitVector
is_power_of_2 = lambda x: BitVector( intVal = x ).isPowerOf2_sparse()

1. I had not heard of this library before. I've been using BitArray. I've downloaded it for use with version 2x and 3x and I'll see how the two compare.