What is the fastest algorithm that returns the power of a number that has a power of 2?

Question

Given n = 2 ^ k, how can I find k, assuming n is a 32-bit integer using bitwise C / C ++?

Answer 1

Well, you could use the fact that the binary metric 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 it is, and it is certainly not the most portable solution, but I find it quite interesting.

And just for fun, here is a completely different, relatively direct 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 fully deployed 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"; } } 

Answer 2

GCC has __builtin_clz , which translates to BSR on x86 / x64, CLZ to ARM, etc. and emulates a command if the hardware does not implement it. <Visual C ++ 2005 and above have _BitScanReverse .

Using these functions, you can get your k

Answer 3

Wikipedia writes how to do this 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: the binary logarithm from this page the original version with the sample code has been changed, you can still find it: Wikipedia: Binary logarithm (May 24, 2011)

Answer 4

continue the right shift of the n value until get 1.count the number of necessary shifts to the right.

Answer 5

For a portable solution (without resorting to implementation-specific materials), you can use binary chops, which is probably one of the most effective methods that are not related to intolerance. For example, let's 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; } 

It gets a little cumbersome as the size of the whole increases, but you only need to write it :-)

Answer 6

Given: 0 <= n <= 2**32 , which means 0 <= k <= 32 , and k can be represented by byte. 2 ** 32 bytes of RAM are not excessive in general, so the fastest way to calculate this can be by simply looking at the table.

Answer 7

If you are using GCC, I think this is the fastest way:

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

Where __builtin_clz is the optimized built-in GCC function.