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 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 ]