2011-12-02

Bit manipulation trickery

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.


PGP Key:479F 96E1 2B49 8B0D 69F1 94EE F11B E194 2E6C 2B5E (last 32 bit of fingerprint are ID).

Impressum

This is a noncommercial private webpresence / weblog (blog), of
Dies ist eine nicht-kommerzielle Webpräsenz / Weblog (Blog), von

Wolfgang Draxinger

Please obtain the technical and administrative contact information from the WHOIS data of this domain. Technische und administrative Kontaktdaten sind bitte den WHOIS-Daten dieser Domain zu entnehmen.