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

Re:Ten Ways to Check if an Integer Is a Power Of Two in C by imurray on Tuesday July 26, 2011 @05:21PM (#2809546)

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.

[ Parent | on HN ]

Re:Ten Ways to Check if an Integer Is a Power Of Two in C by oldcigarette on Wednesday July 27, 2011 @09:16AM (#2811960)

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.

[ Parent | on HN ]

Re:Ten Ways to Check if an Integer Is a Power Of Two in C by imurray on Wednesday July 27, 2011 @05:52PM (#2814359)

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.

[ Parent | on HN ]