One recurring task when working with data structures is finding out if a given number (say an index into a sorting tree) is a power of 2.

A number is a power of two, if exactly one bit is set, so it all boils down to testing for that.

There are several way to do this. The most naive and inefficient way is to test for all the powers of two representable in a given amount of bits.

int ispow2(int x) 
{
    int bc = 0;
    for(int i = 0; i<sizeof(x)*CHAR_BITS; i++) {
        if( 1<<i & x )
            bc++;
        if(bc > 1)
            return 0;
    }
    return bc == 1;
}

This function is suboptimal, since it's O(n)

A better way, circulating the net for years is this little gem of bit trickery, which executes O(1)

int ispow2(int x)
{
    return !( (~(~0U>>1)|x) & (x-1) );
}

Unfortunately it only works for a specific type (you can of course adjust the most significant bit constant. But say you'd want to use this in a type agnostic macro. What I've seen in circulation is this (using the typeof Compiler extension -- which is not part of the C core language specification):

#define ISPOW2(x) ( ! ( (~(~((typeof (x))0) >> 1) | (x)) & ((x) - 1) ) )

Slightliy better is this:

#define ISPOW2(x) ( ! ( (1<<(sizeof(x)*CHAR_BIT-1) | (x)) & ((x) - 1) ) )

But those attempts look in the wrong direction: That most significant bit is only set to account for the case if x is 0.

In a project I wrote about 1 year ago I (re?-)invented the following method which works with any integral type:

#define ISPOW2(x) ( (x) && !( (x) & ((x) - 1) ) )

So far I've never seen it in circulation in the Internet. Maybe I am the first guy to write it that way, but I don't think so. (if I am: cool!)Nope. Some guys pointed to me to several bit twiddling hacks documents, where this is written that way. But you know what? I don't care, I came up with it myself, instead of just reading it somewhere. Of course credit where is credit due. I'm still interested who did invent that thing first.