[Tutor] Power of Two Function
bgailer at gmail.com
Sat Sep 1 01:30:42 CEST 2012
On 8/31/2012 6:54 PM, Lazar wrote:
> 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
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
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.
Chapel Hill NC
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Tutor