Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

exploringbinary.com

Post reply on HN
Print view View original

41–50 of 82 posts

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

#42

Post by tesseract »

omaranto wrote: post #26

It seems bizarre to call the first group of methods "decimal based" when the methods don't ever look at the decimal digits of the number being tested. I would call them "arithmetic" or something like that.

Or "representation independent", although the ones that rely on the number being less than INT_MAX obviously rely on some knowledge of the representation.

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

#43

Post by rcfox »

wnoise wrote: post #40
Jabbles wrote: post #16

Earlier quoted context omitted.

And 3 == 2^(log_2(3)). Clearly we want to know if x is an integer power of 2.

2^(bitsize) == 0. Edit: Yes, 1 << bitsize is undefined. But unsigned integers actually do have well-defined semantics on overflow, and multiplying by 2 enough times really does produce zero.

Actually, it's undefined behaviour. http://blog.regehr.org/archives/213

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

#44

Post by ot »

wnoise wrote: post #40
Jabbles wrote: post #16

Earlier quoted context omitted.

And 3 == 2^(log_2(3)). Clearly we want to know if x is an integer power of 2.

2^(bitsize) == 0. Edit: Yes, 1 << bitsize is undefined. But unsigned integers actually do have well-defined semantics on overflow, and multiplying by 2 enough times really does produce zero.

2^(bitsize) == 2^(bitsize)

If you meant 1 << (bitsize), that's undefined behaviour in C

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

#45

Post by imurray »

For interest rather than practical use:

Creating a 2GiB lookup table is ~10% faster on my machine than method #10. That is, faster on the benchmark in the blog post. A 2GiB lookup table is horrible, has a little setup cost dominated by calloc-ing the array, and would trash caches with real code.

A also made a solution using a union to split x into two shorts and a 64kiB lookup table that was ~15% slower. For more expensive functions, lookup tables are an annoying baseline to beat. (Although still often good to avoid because of dealing with setup, cache problems, etc.)

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

#49

Post by ColinWright »

MostAwesomeDude wrote: post #41
bad_user wrote: post #25

return ((x != 0) && !(x & (x - 1))); This is beautiful.

And fast; Mesa uses this. static INLINE boolean util_is_power_of_two( unsigned v ) { return (v & (v-1)) == 0; }

Returns True when v==0, and yet 0 is not a power of 2.

Further, this technique - correctly applied - is essentially #9 in the list.

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

#50

Post by lambda_cube »

zxw wrote: post #27

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

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.

Post reply on HN