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

http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/

by caustic • 15 years ago

114 65 15 years ago

exploringbinary.com

mansr2• 15 years ago

One they missed: (x & -x) == x

Jabbles3• 15 years ago

Unfortunately this doesn't work for x=0.

rcfox5• 15 years ago

2^-infinity == 0

mansr2• 15 years ago

So make it x && blah. Do I really have to state the obvious?

chime• 15 years ago

That was #9:

    int isPowerOfTwo (unsigned int x)
    {
      return ((x != 0) && !(x & (x - 1)));
    }

quacker• 15 years ago

This is method 10 in the article, since -x is equivalent to ~x+1.

cube13• 15 years ago

This works for negative values of x, though.

It should be: ((x>0) && ((x & -x) == x))

rcfox5• 15 years ago

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

dasmoth2• 15 years ago

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.

vilya• 15 years ago

FWIW, 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.

dasmoth2• 15 years ago

Unfortunately __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.

TorKlingberg• 15 years ago

Also, 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• 15 years ago

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.

btilly• 15 years ago

Most of the solutions explicitly assume 32 bit integers. These days most of us have 64 bit integers available.

lambda_cube6• 15 years ago

Yes, 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• 15 years ago

     return ((x != 0) && !(x & (x - 1)));

This is beautiful.

slug• 15 years ago

for more equally beautiful expressions, check out "Hacker's Delight".

MostAwesomeDude2• 15 years ago

And fast; Mesa uses this.

  static INLINE boolean
  util_is_power_of_two( unsigned v )
  {
     return (v & (v-1)) == 0;
  }

ColinWright• 15 years ago

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.

lojack• 15 years ago

Check out Bit Twiddling Hacks if you'd like to see more: http://graphics.stanford.edu/~seander/bithacks.html

gjm114• 15 years ago

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 :-).]

vog3• 15 years ago

However, this way your code enters an undefined state in C, strictly speaken. (as far as I unstand the standard)

So theoretically, an extremely aggressive optimizer would be allowed to generate machine code that doesn't handle the case x==0 properly.

If (x != 0) is placed first, the optimizer wouldn't be allowed to do that, due to short-circuit evaluation.

omaranto• 15 years ago

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.

rcfox5• 15 years ago

It's decimal as in base 10, as opposed to binary.

eru4• 15 years ago

But 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• 15 years ago

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

zxw4• 15 years ago

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

eru4• 15 years ago

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

zxw4• 15 years ago

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

lambda_cube6• 15 years ago

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.

zxw4• 15 years ago

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.

Lambent_Cactus• 15 years ago

I hadn't considered #2, the Check All option. I love its refusal to be drawn into over-engineering.

sharth• 15 years ago

Use popcount?

return _mm_popcnt_u64(x) < 2;

ChristianMarks• 15 years ago

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;
  }

axylone• 15 years ago

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

imurray4• 15 years ago

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

lambda_cube6• 15 years ago

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

imurray4• 15 years ago

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 faster than the fastest reported result, when tested naively.)

sltkr2• 15 years ago

> 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 since your values aren't expected to be in-cache anyway.

sltkr2• 15 years ago

Great job; that was definitely a point of comparison that was missing from the original article. I'm surprised this actually is faster, but if it is only by 10%, then I still think the memory-less algorithm is preferable.

On modern-day systems main memory access is much slower than the processor, and on multi-core systems (which are the norm these days, though not all cores are always in use, of course) the memory bus can easily become a bottleneck. Benchmarks tend to hide that fact because they are often run on a single core on an otherwise idle system, so they usually have all memory bandwidth and cache memory to themselves, which isn't really representative of real-world systems.

For that reason, I believe that algorithms that do not depend on fast memory access to work efficiently are preferable to those that make use of large memory caches, at least if the performance difference isn't too great.

Someone• 15 years ago

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

kqueue• 15 years ago

if x is unsigned, then:

(x & (x - 1)) == 0

aidenn0• 15 years ago

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.

imurray4• 15 years ago

A 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• 15 years ago

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

imurray4• 15 years ago

Thanks, 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.

gjm114• 15 years ago

Here'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.)

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

Related Stories