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 :

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.

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

Anatoly Spektor

IT Consultant with 6 years experience in Software Development and IT Leadership. Participated in such projects as Eclipse IDE, Big Blue Button, Toronto 2015 Panam Games.

Join the Discussion

Your email address will not be published. Required fields are marked *

arrow