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 :
1 2 3 |
# 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.
1 2 3 4 5 6 7 8 9 |
#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