Log2 is an integer which is a power of 2

Question

Is there an efficient way to find log2 numbers, assuming it is a force of 2. I know obvious ways how to have a table or

for (log2=0;x!=1;x>>=1,log2++); 

But I am wondering if there is a more efficient / elegant way.

Answer 1

You can simply count the number of start or end zero bits, because any exact power of the two is represented as one 1 bit, with all other bits 0. Many CPUs have special instructions for this, and compilers are like that since gcc has built-in functions for these operations, which are compiled into a single command on the respective architectures.

If you have efficient clz ("count leading zeroes"), the log2 implementation might look like this:

 int32_t ilog2(uint32_t x) { return sizeof(uint32_t) * CHAR_BIT - clz(x) - 1; } 

(Note: returns -1 for ilog2(0) .)

When using a gcc or gcc-compatible compiler, you can simply define clz as follows:

 #define clz(x) __builtin_clz(x) 

Microsoft has something similar: BitScanReverse .

Note that it is more convenient to count trailing zeros (using the ctz instruction), but the clz instruction clz more widely available on various processor architectures .

An additional advantage of using clz rather than ctz is that you get floor(log2(x)) for values ​​without power 2, which makes your ilog2 function more useful than if you used ctz , which only works for exact degrees-2 .

See also: Search for the first bit of a set in a binary number .

Answer 2

I did not compare this, but it should work fast enough, since it does not require many iterations:

 int which_power_of_2(uint64_t x) { uint64_t z = 0x0000000100000000ULL; int p = 31, d = 16; while (d) { if (x & (z-1)) { p -= d; z >>= d; } else { p += d; z <<= d; } d >>= 1; } return x ? ((x & z) ? p+1 : p) : -1; }