3 ms·
A nasty solution, which assumes and abuses IEEE floating point format and demonstrates a couple of things. int isPowerOfTwo (unsigned int x) { int
by imurray 15y 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 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.