[Tutor] Power of Two Function

[Alan Gauld]

On 31/08/12 23:54, Lazar wrote:

> Can someone please explain to me in what way the following function
> checks if a number is a power of two? Basically, the second line of
> code is what I can't really grasp:
>
> def is_power2(num):
> 	return num != 0 and ((num & (num - 1)) == 0)


In binary any positive power of 2 looks like 1 followed by zeros:
10, 100, 1000 etc

If you subtract 1 from  any of those numbers you get
a zero followed by all 1s:

01, 011, 0111 etc

So if you bitwise and N and N-1 you get

   1....0
& 0....1
----------
   0....0

ie all zeros which equals the decimal number zero.


So your function first checks that the argument is not zero
if that is true then it evaluates the second part which as
we've seen does equal zero for a power of two.

Unfortunately it breaks down for fractions like 1/2, 1/4 etc
which are negative powers of 2.

HTH,

-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/