How to find if a number is power 2 ? (Bitwise and Iterative) [Python Script]


As I have promised, I continue answering your questions.

One of the readers of myprogrammingblog.com wrote me an email asking How to find if a number is power 2 ? He also asked me to write a bitwise solution as well as an iterative  solution using Python. There are many examples of these kind of questions in the Internet, but I thought it would be nice to put one up here too,  since person asks.

Ok, here we go !

So first solution  is the bitwise one .

In this solution we will be using legendary bitwise operator AND (&). This solution is based on the unique property of all power 2 numbers having only one bit set to one and all other bits to zero. So number-1 will remove this one bit making expression equal to zero, if the number is power of two. You will notice that there is special case – number != 0 . If you put 0 into expression below, you will see that despite 0 being not power of two, expression will return true. So to eliminate special case, I just made sure that number is not zero.

Here is the function itself :

# Bitwise version
def powTwoBit(number):
  return (number & (number-1) == 0) and (number != 0)

Second solution is easier to understand if you are not a big fan of bitwise operations, since it uses regular looping and is based on the property that any number that is power of two has –  divisible by two without a remainder. So in this solution I loop and divide number by 2 until number is not equal to 1. If one of these divisions shows me that division produced a remainder, I know that number is not power of two. I also take into account special case – number must be positive.

#Iterative version
def powTwoIter(number):
	isPowOfTwo=True;
	while (number != 1 and number > 0):
		if(number%2):
			# can do return here as well
			isPowOfTwo = False
		number=number/2
	return isPowOfTwo and (number > 0)

So here they are – 2 solutions of how to find if a number is power of 2 in Python. I have put this code into myprogrammingblog.com github repo together with Unit Tests. So feel free to use it.

Of course there are many other solutions. For example you can create an array of power 2 values, sorted from least to greatest (the range that corresponds to the problem you are trying to solve) and use a binary search to find if your number corresponds to one of those in the array.

 Choose whatever works for you!

Regards,

Anatoly

Advertisements

About Anatoly Spektor

My name is Anatoly Spektor (originally Anatolijs Spektors) I am Software and Web Developer. I have worked in Seneca Center for Development of Open Technology on Big Blue Button Add-on - Polling Module, Red Hat and some other places :) I am an author of the book 'Eclipse Debugging How To', Muay Thai fighter and amateur photographer ;)
This entry was posted in open-source, Programming Languages, Python, Useful Functions and tagged , , , , . Bookmark the permalink.

One Response to How to find if a number is power 2 ? (Bitwise and Iterative) [Python Script]

  1. mezi5cHB says:

    The industry pointed out that i http://www.pmjg.net/ nkjet printer manufacturers should comply with the requirements of market development, product quality as the core, integrity management, and continuously improve product performance, towards the inkjet printer print speed, more content, automatic cleaning easy, simple

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s