What is the fastest algorithm to return the power of a number which is a power of 2?

Given n = 2^k, how can I find k assuming n is 32-bit integer using C/C++ bitw开发者_如何学运维ise?

GCC has __builtin_clz that translates to BSR on x86/x64, CLZ on ARM, etc. and emulates the instruction if the hardware does not implement it.
Visual C++ 2005 and up has _BitScanReverse.

Using those functions, you can get your k

Wikipedia writes how to do it using bitwise operators:

/**
 * Returns the floor form of binary logarithm for a 32 bit integer.
 * −1 is returned if ''n'' is 0.
 */
int floorLog2(unsigned int n) {
  if (n == 0)
    return -1;

  int pos = 0;
  if (n >= 1<<16) { n >>= 16; pos += 16; }
  if (n >= 1<< 8) { n >>=  8; pos +=  8; }
  if (n >= 1<< 4) { n >>=  4; pos +=  4; }
  if (n >= 1<< 2) { n >>=  2; pos +=  2; }
  if (n >= 1<< 1) {           pos +=  1; }
  return pos;
}

Code taken from: Wikipedia on: Binary Logarithm this page has since been altered the original version with the code sample can still be found her: Wikipedia on: Binary Logarithm (24 May 2011)

Well, you could use the fact that the binary exponent is explicitly stored in floating point numbers:

unsigned log2(unsigned x)
{
    float f = x;
    memcpy(&x, &f, sizeof x);
    return (x >> 23) - 127;
}

I don't know how fast this is, and it surely is not the most portable solution, but I find it quite interesting.

And just for fun, here is a completely different, relatively straightforward solution:

unsigned log2(unsigned x)
{
    unsigned exp = 0;
    for (; ;)
    {
        switch (x)
        {
            case 128: ++exp;
            case 64: ++exp;
            case 32: ++exp;
            case 16: ++exp;
            case 8: ++exp;
            case 4: ++exp;
            case 2: ++exp;
            case 1: return exp;
            case 0: throw "illegal input detected";
        }
        x >>= 8;
        exp += 8;
    }
}

And here is a completely unrolled solution:

#define CASE(exp) case (1 << (exp)) : return (exp);

unsigned log2(unsigned x)
{
    switch (x)
    {
        CASE(31) CASE(30) CASE(29) CASE(28)
        CASE(27) CASE(26) CASE(25) CASE(24)
        CASE(23) CASE(22) CASE(21) CASE(20)
        CASE(19) CASE(18) CASE(17) CASE(16)
        CASE(15) CASE(14) CASE(13) CASE(12)
        CASE(11) CASE(10) CASE( 9) CASE( 8)
        CASE( 7) CASE( 6) CASE( 5) CASE( 4)
        CASE( 3) CASE( 2) CASE( 1) CASE( 0)
        default: throw "illegal input";
    }
}

keep on right-shifting the value n till u get get 1.count the number of right shifts required.

For a portable solution (without resorting to implementation-specific stuff), you can use binary chop which is probably one of the most efficient ways not involving non-portable stuff. For example, say your integer is 8 bits:

// Given n = 2^k, k >= 0, returns k.

unsigned int getK (unsigned int n) {
    if (n <= 8) {
        if (n <= 2) {
            if (n == 1) return 0;
            return 1;
        }
        if (n == 4) return 2;
        return 3;
    }
    if (n <= 32) {
        if (n == 16) return 4;
        return 5;
    }
    if (n == 64) return 6;
    return 7;
}

That gets a little unwieldy as the integer size increases but you only have to write it once :-)

Given: 0 <= n <= 2**32 that means 0 <= k <= 32 and k can be represented by a byte. 2**32 bytes of RAM is not exhorbitant in general, so the fastest method of calculation might well be a simple table lookup.

If you use GCC, I guess that this is the fastest way:

int ilog2(int value) {
 return 31 - __builtin_clz(value);
}

Where __builtin_clz is an optimized GCC builtin function.