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

71–80 of 82 posts

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

#71

Post by imurray »

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

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

#72

Post by gjm11 »

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

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

#73

Post by zxw »

lambda_cube wrote: post #70
zxw wrote: post #66

Earlier quoted context omitted.

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.

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.

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

#74

Post by neckbeard »

dasmoth wrote: post #31
vilya wrote: post #23

Earlier quoted context omitted.

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.

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.

GCC 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

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

#75

Post by oldcigarette »

imurray wrote: post #71

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

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.

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

#76

Post by vog »

gjm11 wrote: post #63
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…

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.

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

#77

Post by vog »

ColinWright wrote: post #49
MostAwesomeDude wrote: post #41

Earlier quoted context omitted.

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.

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

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

#78

Post by imurray »

oldcigarette wrote: post #75
imurray wrote: post #71

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

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.

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.

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

#79

Post by gjm11 »

vog wrote: post #76
gjm11 wrote: post #63

Earlier quoted context omitted.

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…

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.

It's OK if x is of an unsigned integer type. If x is of a signed type, though, you're right: strictly, the value of x-1 is then undefined when x==0.

(In practice, of course, it's perfectly safe unless you're on a distinctly exotic system, and if you are then you probably know you are.)

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

#80

Post by MostAwesomeDude »

ColinWright wrote: post #49
MostAwesomeDude wrote: post #41

Earlier quoted context omitted.

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.

Mesa 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

Post reply on HN