4 ms·
Is there a reason this won't work? It's the most 'readable' way I could come up with. #(python code) def is_power_of_two(n): import math
by zxw 15y ago
Is there a reason this won't work? It's the most 'readable' way I could come up with.
#(python code)
def is_power_of_two(n):
import math
if n <= 0:
return False
power = round(math.log(n, 2))
return 2 ** power == n
- deleted 15y ago[deleted]
- eru 15y agomath.log uses floating point arithmetic. That will lead to trouble on large numbers. The article addresses the issue.
- zxw 15y agoI'm not doing power == int(power) though which is what he warns against. I haven't done a lot of testing however as far I can tell it's working. >>> is_power_of_two(2 ** 31 - 1) False >>> is_power_of_two(2 ** 31) True >>> is_power_of_two(2 ** 31 + 1) False >>> is_power_of_two(2 ** 548 - 1) False >>> is_power_of_two(2 ** 548) True >>> is_power_of_two(2 ** 548 + 1) False
- eru 15y agoYes. It seems to work for much larger numbers than this on my version of Python, but going via doubles leaves a bad taste.
- lambda_cube 15y agoThis will probably give the wrong answer for some integer. I have tried something similar in Java. Since it was three years ago my memory is a little hazy. I was working on a parallelizing compiler written in Java (but not for Java) and I saw that the other programmers had used a method similar to yours, it used log anyway. I knew about #9 and #10 and worried that their method was potentially wrong (and also inefficient). To check if it was wrong I coded up something that compared the log-floating point method against #10 for all non-negative integers and the log-floating point method gave the wrong answer for one value (out of 2 billion). That was Java and your example is in Python, there could be some difference. If you try and compare in Python, please tell us the result.
- zxw 15y agoHere is the code from the first test.[0] It increments a variable and prints a message if their is an inconsistency. I left it running till it reached 1,351,773,471 and didn't come up with any inconsistencies. I then modified the test[1] to look for inconsistencies where they were most likely to be found, ie ±1 of 2n. I reached n being 1024 before python complained about a 'Result too large'. [0] http://paste.pound-python.org/show/10067/ http://paste.pound-python.org/show/10067/ [1] http://paste.pound-python.org/show/10068/ http://paste.pound-python.org/show/10068/ Edit: just reread about the 1 in 2 billion chance, I'll leave the first test running longer to make sure.
- lambda_cube 15y agoNice to see some experimentation. :) I tested all 2^31 non-negative integers, which is 2147483648 values. If I remember correctly, the value that was wrong was large, probably between 2^30 and 2^31. Java is pretty fast and I think this took tens of minutes. Python is about 20 times slower so it may take hours for you.
- zxw 15y agoYeh it's fairly slow going. I'm at 3,706,382,752 and am going to call it a day. Looks like the code works properly.