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

61–70 of 82 posts

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

#61

Post by aidenn0 »

feb wrote: post #24
esrauch wrote: post #17

Earlier quoted context omitted.

The benchmarks would probably be somewhat misleading in a lot of cases here. I'm fairly certain that most compilers will replace a /2 with >>1 for example, so that isn't really going to end up being reflected when you compile it.

That depends on the CPU used. Modern CPU have more arithmetic units than logical units and can perform more divisions than bit shifts. There was a good video presentation of that, but I can't find the link now. EDIT: http://blogs.msdn.com/b/shawnhar/archive/2007/03/19/a-story-... gives other reasons why multiplications can be faster than bit shifts.

That's multiplies, not divides. Modern CPUs are still faster at shifts than divides, even the pentium4, which lacked a single-cycle shift unit.

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

#62

Post by aidenn0 »

The benchmarks are crap. The loop/function call overhead time dominates. They should list the benchmark for when the implementation is "return x;" That gives a baseline number. On my machine I have to run a few thousand runs before I can distinguish between "return x;" and "return ((x != 0) && !(x & (x - 1)));"

They both take about 10s for 232 iterations.

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

#63

Post by gjm11 »

bad_user wrote: post #25

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

Unless x==0 is often true, it's probably better to put the conjuncts in the other order:

  return (!(x & (x-1)) && (x != 0));
because that way you don't have to test x against 0 so often.

(On my machine it appears to be about 10% faster.)

[EDIT to clarify: 10% faster with the particular sample of x values that I tested, which happened to be all the integers from 0 up to 2^30-1 once each. Of course if you only ever call it with x=0 then the original version will be faster. Also, if this is really in your inner loop then you're probably doing something wrong :-).]

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

#65

Post by lambda_cube »

sltkr wrote: post #60
lambda_cube wrote: post #54

Earlier quoted context omitted.

How were you accessing the lookup table? In a linear or random way? If you did it in a linear way, locality and prefetching will help performance for your lookup table. The great thing about #9 and #10 is that they are just as fast when the sequence of numbers is random. I know you weren't serious about the 2GiB lookup table, but if a lookup table in general should be used as a baseline, the benchmark should probably…

> You can simulate random access by using a stride great enough to avoid the cache. I think a good pattern is to add a large number co-prime to 2^32 on every iteration. That guarantees you actually hit all cache entries, while picking a "round" number like 1024 underutilizes the cache severely, which is unfair if you were trying to simulate random performance. edit : Actually, in this case it doesn't really matter si…

Thank you for that little trick. Even if it doesn't matter for this case I will remember it for later. I know I've read stuff like that before, but I haven't learned enough of that part of discrete math to really understand why (but it seems kind of intuitive).

As a coincidence I got "A Concrete Introduction to Higher Algebra" by Lindsay Childs in the mail today. The concrete part of the book is that he uses properties about integers to introduce and teach concepts about algebra (and then he goes on to polynomials and other stuff). So now I got no excuse to not know that stuff any longer :-).

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

#66

Post by zxw »

lambda_cube wrote: post #50
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 ineffici…

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.

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

#67

Post by ppereira »

dasmoth wrote: post #15

Recent Intel/AMD CPUs have a POPCNT instruction, which seems like the logical way to do this. Would be interested to see how that performs compared to these implementations.

Intel has included BSF and BSR (bit scan forward / reverse) since 386, which would presumably also give you the magnitude of the power of 2.

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

#68

Post by axylone »

ChristianMarks wrote: post #38

The decrement test for a power of two can be modified to count bits and runs in log n time. int bits(unsigned n) { int i = 0; while (n > 0) { n &= n-1; i++ } return i; }

Much better ways to count bits set: http://graphics.stanford.edu/~seander/bithacks.html#CountBit...

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

#69

Post by lambda_cube »

imurray wrote: post #58
lambda_cube wrote: post #54

Earlier quoted context omitted.

How were you accessing the lookup table? In a linear or random way? If you did it in a linear way, locality and prefetching will help performance for your lookup table. The great thing about #9 and #10 is that they are just as fast when the sequence of numbers is random. I know you weren't serious about the 2GiB lookup table, but if a lookup table in general should be used as a baseline, the benchmark should probably…

I completely agree with all of the above. I was doing a linear scan, and I know that that is artificial. Your stride suggestion does slow things down dramatically; thanks for the simple-to-implement idea. (Shrinking the lookup table by 1/8, I don't know how to do that fast .) The annoying thing about lookup tables is that they are hard to benchmark properly. But superficially they often look like a good idea. (Here f…

> I was doing a linear scan, and I know that that is artificial.

May be artificial :). Don't forget that your application is the best benchmark. If it uses linear access you can take advantage of that. Let's just say that linear access is a special case and random access is a worst case result. The behavior of the random access is the one to remember, IMO.

> Shrinking the lookup table by 1/8, I don't know how to do that fast.

Here is how I do bit vectors. I'm not suggesting that anyone should use a lookup table for this problem since there are very fast solutions that uses O(1) memory, but let's use this as an example since we're all familiar with it.

Since you mention a 2GiB table I guess you use a byte vector. The article uses an unsigned int as the type for the argument which would need 4GiB for all values, I guess you used int instead. We want to use every bit of memory in an array to store boolean flags. It's probably faster to use the native word size of the machine than to use byte size elements, so let's use unsigned int. I assume that we use a 32-bit machine, just like in the article. If you have a 64-bit machine it will be obvious what to change.

We need 2^31 bits (1 When looking up things in a bit vector we need to find the right element in the array and the right bit in the array element that holds the boolean flag. To find the right element we divide the input by the number of bits in each element. To find the right bit we do mod (%) by the number of bits in each element and then shift a bit flag by that amount and AND (&) with the array element.

  unsigned table[1  0) {
          return table[x / 32] & (1
Since the constant 32 is a power of two, a good C compiler will change the divide and modulo operations to shift and AND. If you use some other language and/or your compiler doesn't optimize that you may want to do that optimization by hand. x / 32 == x >> 5, if x >= 0. x % 32 == x & 31, if x >= 0. NB: It's not that simple for negative numbers!

The lookup table must be populated before use of course, that is left as an exercise for the reader ;-).

(imurray, if you think I explained things you already know, I did it for other readers.)

> The annoying thing about lookup tables is that they are hard to benchmark properly.

If you want some general rule: If you can get the table small, lookup tables are fast, sometimes the fastest solution. But maybe you're application (not an artificial benchmark) doesn't use the function very often and the table won't be in the cache. Then the computation have to slower than fetching memory with a cache miss for the lookup table to be worth it. Also, memory bandwith has been a bottleneck for a long time and it will get even worse. This diminishes the value of lookup tables and trading memory for computation time. As always when it comes to performance and optimizations: benchmark your application with your data. General results may or may not apply in your context.

Edit: If you want the answer to always come out as 0 for false and 1 for true, you can do this instead:

  return (table[x / 32] >> (x % 32)) & 1;

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

#70

Post by lambda_cube »

zxw wrote: post #66
lambda_cube wrote: post #50

Earlier quoted context omitted.

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 ineffici…

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 2 n. I reached n being 1024 before python complained about a 'Result too large'. [0] http://paste.pound-…

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.

Post reply on HN