An elegant way to find a power of 2

Question

My question is quite similar to Fastest way of computing the power that a "power of 2" number used?:

Giving x=2^y as an input I want to output y. The difference is that I'm coding in C, not C++ and I know for sure that there is only one bit set in my input so I'm wondering if there is a more efficient ways to solve this.

Here is my try:

unsigned int get_power_of_two(unsigned int x)
{
    unsigned int y=0;
    for(unsigned int input=x; input>0; input=input>>1)
    {
        if(input & 1U)
        {
            break;
        }
        y++;
    }
    return y;
}

What is this efficiency compared to the proposed lookup table in @Dave's answer ? (again, I'm coding in C so I don't have the iterators functions like lower_bound)

Answer 1

In your case since you know only one bit is set, so it's enough to count trailing zeros. This can be done without a hardware instruction very quickly. Check out this answer, that's where the code below comes from (I'm not one to tamper with perfection... sometimes).

unsigned v;  // this is the number with one bit set
unsigned r;  // this becomes the exponent in v == pow(2, r)
static const unsigned MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((unsigned)((v & -v) * 0x077CB531U)) >> 27];

In your case since v only has one bit set, so you don't need to find the lowest bit set; therefore you can skip v & -v. And your version of the code becomes this:

unsigned v;  // this is the number with one bit set
unsigned r;  // this becomes the exponent in v == pow(2, r)
static const unsigned MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[(v * 0x077CB531U) >> 27];

See the link for more information, it in turn links to it's source information.

Answer 2

The efficiency of your algorithm is O(log x), whereas Dave's (which performs binary search on powers of two) is O(log log x). So his is asymptotically faster.

The fastest approach, of course, is to use the BSF instruction.

Answer 3

Apart from ways previously said by others, such as BSF or CLZ instructions which strictly depend on the underlying ISA, there are some other ways such as:

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

in fact here you could find a lot of 'bit twiddling hacks' there.

Answer 4

As a side-note, you should consider renaming function get_power_of_two to get_log_two.

If you are calling this function very often, then you can initialize a relatively small look-up table.

Using this table, you can check every input number, byte by byte, as follows:

#include <limits.h>

static unsigned int table[1<<CHAR_BIT];

void init_table() // should be called once
{
    for (unsigned int n=0; n<CHAR_BIT; n++)
        table[1<<n] = n;
}

unsigned int get_log_two(unsigned int x)
{
    for (unsigned int n=0; x>0; n+=CHAR_BIT, x>>=CHAR_BIT)
    {
        unsigned int y = x & ((1<<CHAR_BIT)-1);
        if (y > 0)
            return n+table[y];
    }
    return ~0; // will never be reached during runtime
}

This is not necessarily the most efficient method in terms of "pure academic complexity", as function get_log_two does not perform a binary-search.

Nevertheless, considering the relatively small value of sizeof(unsigned int) on any platform (usually 4), it will pretty much yield the same performance for average as well as worst-case scenarios.

Answer 5

Here is a funny idea...

If you know there is only 1 bit set, then why not use a switch?

unsigned int get_log_two(unsigned int x)
{
        switch(x)
        {
            case 1<<0: return 0;
            case 1<<1: return 1;
            case 1<<2: return 2;
            case 1<<3: return 3;
            case 1<<4: return 4;
            case 1<<5: return 5;
            case 1<<6: return 6;
            case 1<<7: return 7;
            case 1<<8: return 8;
            case 1<<9: return 9;
            case 1<<10: return 10;
            case 1<<11: return 11;
            case 1<<12: return 12;
            case 1<<13: return 13;
            case 1<<14: return 14;
            case 1<<15: return 15;
        }
        return 0;
}

Extend this to 31, and you'll have a good function. This should be fast; but will only work if there is only one bit set.