Ten Ways to Check if an Integer Is a Power Of Two in C

Re:Ten Ways to Check if an Integer Is a Power Of Two in C by zxw on Tuesday July 26, 2011 @11:31AM (#2807775)

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

[ Parent | on HN ]

Re:Ten Ways to Check if an Integer Is a Power Of Two in C by lambda_cube on Tuesday July 26, 2011 @01:53PM (#2808563)

This 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.

[ Parent | on HN ]

Re:Ten Ways to Check if an Integer Is a Power Of Two in C by zxw on Tuesday July 26, 2011 @03:58PM (#2809217)

Here 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/

[1] 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.

[ Parent | on HN ]

Re:Ten Ways to Check if an Integer Is a Power Of Two in C by lambda_cube on Tuesday July 26, 2011 @05:07PM (#2809495)

Nice 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.

[ Parent | on HN ]

Re:Ten Ways to Check if an Integer Is a Power Of Two in C by zxw on Tuesday July 26, 2011 @06:31PM (#2809749)

Yeh 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.

[ Parent | on HN ]

Re:Ten Ways to Check if an Integer Is a Power Of Two in C by eru on Tuesday July 26, 2011 @11:41AM (#2807836)

math.log uses floating point arithmetic. That will lead to trouble on large numbers. The article addresses the issue.

[ Parent | on HN ]

Re:Ten Ways to Check if an Integer Is a Power Of Two in C by zxw on Tuesday July 26, 2011 @12:12PM (#2808001)

I'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

[ Parent | on HN ]

Re:Ten Ways to Check if an Integer Is a Power Of Two in C by eru on Tuesday July 26, 2011 @02:03PM (#2808618)

Yes. It seems to work for much larger numbers than this on my version of Python, but going via doubles leaves a bad taste.

[ Parent | on HN ]