[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