Quickest way to find the most significant bit that is 1...

[KevinHall]

Anyone know what the quickest way to find which bit is the most significant bit that is 1?

For example, say the function I want has the prototype:

int MsbOn(unsigned long x);

MsbOn(1) returns 0
MsbOn(2) returns 1
MsbOn(3) returns 1
MsbOn(14) returns 3
MsbOn(15) returns 3
MsbOn(16) returns 4
MsbOn(20000) returns 14

The only thing I can think of is this:

#define LN2 (0.69314718055994530941723212145818)

int MsbOn(unsigned long x)
{
return (int)floor(log((double)x)/LN2);
}

But this uses floating point math. I'd like to see if there is a quicker, integer way of doing this.

[CBasicNet]

Use bitwise AND operator

if(MyInt & 0x80000000)
{
//Do what you want here


}

0x80000000 is 1000 0000 0000 0000 0000 0000 0000 0000 in binary

[galathaea]

You can do as section four of this document (http://www.hpl.hp.com/techreports/98/HPL-98-112.pdf) suggests. Its a technique I use in certain tight loop calculations....

[galathaea]

If this can be done in x86 assembly, check out the BSR instruction...

[KevinHall]

Thanks galathaea, that's exactly what I wanted!