[Tutor] Power of Two Function

bob gailer bgailer at gmail.com
Sat Sep 1 01:30:42 CEST 2012


On 8/31/2012 6:54 PM, Lazar wrote:
> Hello,
>
> I'm fairly new to Python and still learning.
>
> 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)
A power of 2 in binary is (in general) one followed by zero-or-more 
zeroes. Thus
2 = 10
4 = 100
8 = 1000

The python manual informs us


      5.4.1. Bit-string Operations on Integer Types

Plain and long integer types support additional operations that make 
sense only for bit-strings. Negative numbers are treated as their 2's 
complement value (for long integers, this assumes a sufficiently large 
number of bits that no overflow occurs during the operation).


x & y 	bitwise /and/ of /x/ and /y/


in other words & takes two bit strings, does a boolean and on pairs of 
bits. Thus
1100 & 1010 = 1000 (you get 1 only where the two bits are 1.

for any /integer /n that is a power of 2, n-1 will be a string of all 
ones length one less than n. Thus given n = 4 (100), n-1 is 11. Attach a 
leading 0, perform the & and the result will be 0. Thus

num & (num - 1)) == 0 will be one only for powers of 2.

The function returns 1 or  0 which may be interpreted as True or False by the caller.

Why the function does not ensure that its argument is of type int is a problem.

HTH.

-- 
Bob Gailer
919-636-4239
Chapel Hill NC

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20120831/a502a6c2/attachment-0001.html>


More information about the Tutor mailing list