bitwise most significant set bit

Question

I want to find the most significant bit that is set to 1. I have tried every possible way from & to ORing all of the bits from 1 to 31 and it doesn't work.

Like if 1000000 I would like to have 7.

Answer 1

http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Integer.html#numberOfLeadingZeros%28int%29 You want something like 32 - Integer.numberOfLeadingZeros(value).

Answer 2

The slickest implementation I've come across - three iterations and a table lookup.

unsigned int msb32(unsigned int x)
{
    static const unsigned int bval[] =
    { 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4 };

    unsigned int base = 0;
    if (x & 0xFFFF0000) { base += 32/2; x >>= 32/2; }
    if (x & 0x0000FF00) { base += 32/4; x >>= 32/4; }
    if (x & 0x000000F0) { base += 32/8; x >>= 32/8; }
    return base + bval[x];
}

Answer 3

Though there is an answer accepted, I have another ways to share which I think is easier.

If you want to use bitwise operations, here is the way. Basically, I am right-shifting the integer until it become zero. No mask is required.

private static int mostSignificantBit(int myInt){
    int i = 0;
    while (myInt != 0) {
        ++i;
        myInt >>>= 1;
    }
    return i;
}

Another way is calculate it mathematically:

private static int mostSignificantBit(int myInt){
    if (myInt == 0) return 0;    // special handling for 0
    if (myInt < 0) return 32;    // special handling for -ve

    return (int)(Math.log(myInt)/Math.log(2)) +1;
}