18 ms·
Ten Ways to Check if an Integer Is a Power Of Two in C
- deleted 15y ago[deleted]
- tedunangst 15y agoAll of the loops could be written recursively, but that'd be rather atypical for solving this problem in C.
- eru 15y agoThough with gcc and tail recursion it wouldn't make a difference to the generated code.
- Someone 15y agoI haven't tried, but I would expect doing the linear search in the reverse direction will be faster than binary search. It, on average, inspects just two values; binary search does about five.
- deleted 15y ago[deleted]
- phoyd 15y agoIt is method #9.
- deleted 15y ago[deleted]
- Jabbles 15y agoBecause the methods clearly get more complicated. Starting simply and naively and then improving is a perfectly standard way of teaching. Articles like these, which provide detailed explanation of the methods involved and results of benchmarks help greatly.
- deleted 15y ago[deleted]
- deleted 15y ago[deleted]
- esrauch 15y agoThe 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.
- feb 15y agoThat 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-about-premature-optimization.aspx http://blogs.msdn.com/b/shawnhar/archive/2007/03/19/a-story-... gives other reasons why multiplications can be faster than bit shifts.
- aidenn0 15y agoThat's multiplies, not divides. Modern CPUs are still faster at shifts than divides, even the pentium4, which lacked a single-cycle shift unit.
- Jabbles 15y agoNot only did you not bother to read the site, your version gives the wrong answer for x=0.
- deleted 15y ago[deleted]
- mansr 15y agoOne they missed: (x & -x) == x
- Jabbles 15y agoUnfortunately this doesn't work for x=0.
- rcfox 15y ago2^-infinity == 0
- mansr 15y agoSo make it x && blah. Do I really have to state the obvious?
- rcfox 15y agoI think it would be better to list the worst- and average-case asymptotic analyses of each method, rather than just the run-times. For instance, the "Decimal-Based Approaches to Checking for Powers of Two" will take longer depending on the size of your number.
- dasmoth 15y agoRecent 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.
- vilya 15y agoFWIW, in gcc/g++ there are compiler intrinsics which (should) map to that instruction on CPUs where it's available: __builtin_popcnt, __builtin_popcountl and __builtin_popcountll for unsigned ints, unsigned longs and unsigned long longs respectively. Visual C++ provides equivalent functions for Windows (but I can't remember what they're called). It does seem odd that the article misses this approach out.
- dasmoth 15y agoUnfortunately __builtin_popcnt isn't emitting a popcnt instruction with the GCC I've got here, even using -msse4.2. I believe that very recent GCC does get this right.
- neckbeard 15y agoGCC 4.4 isn't very recent, but it generates a popcnt with -msse4.2. GCC 4.5, using popcnt on my Core-i7 860 takes the trivial loop mentioned using "Complement and Compare" from ~10.5s to ~7.5s
- TorKlingberg 15y agoAlso, is there any pure C code that an optimizing compiler could make into a POPCNT instruction? I would be quite impressed if a compiler could recognize some of the snippets in the article, and compile them into a POPCNT and a compare with 1.
- ppereira 15y agoIntel has included BSF and BSR (bit scan forward / reverse) since 386, which would presumably also give you the magnitude of the power of 2.
- btilly 15y agoMost of the solutions explicitly assume 32 bit integers. These days most of us have 64 bit integers available.
- lambda_cube 15y agoYes, but the two best solutions don't. The other solutions are mostly for educational purposes, I guess. One of #9 or #10 is the one that should be in some utility library.
- bad_user 15y agoreturn ((x != 0) && !(x & (x - 1))); This is beautiful.
- slug 15y agofor more equally beautiful expressions, check out "Hacker's Delight".
- MostAwesomeDude 15y agoAnd fast; Mesa uses this. static INLINE boolean util_is_power_of_two( unsigned v ) { return (v & (v-1)) == 0; }
- ColinWright 15y agoReturns True when v==0, and yet 0 is not a power of 2. Further, this technique - correctly applied - is essentially #9 in the list.
- vog 15y agoAccording to the C spec, this is expression is undefined for v == 0. So it might return true, or return false, or start NetHack, or wipe your disk. In other words: Strictly speaken, that function is not allowed to be called for v == 0.
- MostAwesomeDude 15y agoMesa is a GL renderer. POT only matters in 3D for things like texture sizes. Textures aren't allowed to have zero-sized dimensions. The check for v == 0 occurs far higher up the stack than where this function's used. We're not writing bad code, we promise. :3
- lojack 15y agoCheck out Bit Twiddling Hacks if you'd like to see more: http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html
- 15y ago
- omaranto 15y agoIt 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.
- rcfox 15y agoIt's decimal as in base 10, as opposed to binary.
- eru 15y agoBut they aren't in base 10. The constant mentioned might as well have been put into the code in hex or octal and nothing would have changed. (I don't know whether C support binary constants.)
- tesseract 15y agoOr "representation independent", although the ones that rely on the number being less than INT_MAX obviously rely on some knowledge of the representation.
- zxw 15y agoIs 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.
- Lambent_Cactus 15y agoI hadn't considered #2, the Check All option. I love its refusal to be drawn into over-engineering.
- sharth 15y agoUse popcount? return _mm_popcnt_u64(x) < 2;
- ChristianMarks 15y agoThe 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; }
- axylone 15y agoMuch better ways to count bits set: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive http://graphics.stanford.edu/~seander/bithacks.html#CountBit...
- imurray 15y agoFor 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.)
- lambda_cube 15y agoHow 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 use random access. Do you agree? (Special applications could use a linear access pattern, of course.) (Also, you can shrink the size to 1/8 by just using 1 bit instead of one byte, but that would need some more code of course.) Edit: You can simulate random access by using a stride great enough to avoid the cache. I guess that would be slightly worse than random, but close enough.
- imurray 15y agoI 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 faster than the fastest reported result, when tested naively.)
- lambda_cube 15y ago> 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 << 31 in C), unsigned int is 32 bits and 32 is 2^5 so we need 2^31/2^5 = 2^26 elements. 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 << 26]; unsigned is_power_of_two(int x) { if (x > 0) { return table[x / 32] & (1 << (x % 32)); } else { return 0; } } 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;
- kqueue 15y agoif x is unsigned, then: (x & (x - 1)) == 0
- aidenn0 15y agoThe 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.
- deleted 15y ago[deleted]
- imurray 15y agoA nasty solution, which assumes and abuses IEEE floating point format and demonstrates a couple of things. int isPowerOfTwo (unsigned int x) { int exponent; union { unsigned int u; float f; } tmp; tmp.f = x; exponent = (tmp.u >> 23) - 127; return x == (1 << exponent); } One can also cast to a double without losing precision, mask out the exponent and then compare to 1.0. That solution is even nastier, and needs #define's to deal with endianness. Obviously the above solution is not a good idea! Amongst the several problems, casting to floats is really slow. Sometimes I store my integers in doubles throughout my code because it saves conversions, and can be more convenient. (Matlab users routinely store integers as doubles.) What I found interesting/disconcerting was that the above function doesn't compile reliably. When using 'gcc -Wall' I get isPowerOfTwo(0)==0, whereas with 'gcc -Wall -O2' I get isPowerOfTwo(0)==1. clang has the same change in behaviour with optimization levels.
- oldcigarette 15y agogcc should do the right thing if you add a special case for zero. exponent will be negative in that case. For larger integers you might end up with some false positives with floats though for say 2^30+1.
- imurray 15y agoThanks, I had confused myself. You're right: shifting with a negative value (or far too big) gives undefined behaviour in C. (The type punning stuff is formally undefined too, a memcpy would be more portable, but gcc promises to make the widely-used union trick work.) Regarding the second point, the posted code works fine with 1073741825U (the literal for 2^30+1). The algorithm doesn't need the float to keep full precision, because only the exponent is consulted.
- gjm11 15y agoHere's another. It's strictly inferior to the x&(x-1) one, but the idea that makes it work is so pretty it seems worth mentioning. y = x | (x>>1); y |= y>>2; y |= y>>4; y |= y>>8; y |= y>>16; y |= y>>32; // for 64-bit numbers; return y == (x<<1)-1; So what's going on here? Well, it's easy enough to locate the lowest set bit in x -- it's x & -x, the same basic idea as the x&(x-1) trick -- but what the code above does is to locate the highest by "filling" rightwards from that bit. After the first line, the 1-bits in y are the 1-bits in x, and the bits one to the right of them. After the second, it's the 1-bits in x shifted right by 0..3 places. After the next, 0..7 places. And so on. Eventually, that comes to "all the 1-bits in x, and everything any distance to their right". So, e.g., 000101000100 -> 000111100110 --> 000111111111 which then doesn't change. The nice thing is that the number of steps this takes goes like log(word width). It's in the same spirit as the 0x33333333 popcount trick. (On some processors -- all x86 ones since 386, for instance -- there's an instruction that does something similar directly, but on at least some x86 processors it's rather slow.)