log2(n) with bit manipulation

I'm trying to figure out how to find log2(n) of a number in binary. For example, I want to somehow get 3 out of 01000 (8 in binary). How can this be performed using bit operations with no if statements or loops? Is it even possible?

This is the problem I'm trying to solve:

howManyBits - return the minimum number of bits required to represent x in 2's complement                                                 
Examples:   howManyBits(12) = 5                                               
            howManyBits(298) = 10                                             
            howManyBits(-5) = 4                                               
            howManyBits(0)  = 1                                               
            howManyBits(-1) = 1                                               
            howManyBits(0x80000000) = 32                                      
Legal ops: ! ~ & ^ | + << >>   

So far I have this:

int sign = x >> 31;

/* flip if negative */

int a = x ^ sign;

/* generate mask indicating leftmost 1 in a */

a = a | (a >> 1);
a = a | (a >> 2);
a = a | (a >> 4);
a = a | (a >> 8);
a = a | (a >> 16);
a = a ^ (a >> 1);

/* the amount of bits needed will be log2(a)+2 */ 

I'm just getting stuck figuring how to get the position of a's most significant bit without using a loop!

Thanks!

链接地址: http://www.djcxy.com/p/36400.html

上一篇: 明智的操作员和位操作

下一篇: log2（n）进行位操作