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

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.

Use bitwise AND operator

Code:

---

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


}

---

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

You can do as section four of this document suggests. Its a technique I use in certain tight loop calculations....

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

Thanks galathaea, that's exactly what I wanted!