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
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor