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;
}

Answer 4

If you insist on directly using bitwise operators, you can try something like this:

private int mostSignificantBit(int myInt){
  int mask = 1 << 31;
  for(int bitIndex = 31; bitIndex >= 0; bitIndex--){
    if((myInt & mask) != 0){
      return bitIndex;
    }
    mask >>>= 1;
  }
  return -1;
}

We initialize the mask to 1 << 31 because that represents a 1 followed by 31 0's. We use that value to test if index 31 (the 32nd spot) is a 1. When we and this value with myInt, we get a 0 unless the corresponding bit is set in myInt. If this is the case, we return that bitIndex. If not, then we shift the mask to the right by 1 and try again. We repeat until we run out of places to shift, in which case it means none of the bits were set (maybe you want to throw an exception here instead of returning -1).

Note that this will return the value 0 for 1 and 6 for 64 (1000000 in binary). You can adjust that if you prefer. Note also that I used the unsigned right operator rather than the signed right shift. This is because the intent here is to deal with raw bits rather than their signed interpretation, but it doesn't matter in this instance since all negative values will terminate in the first iteration of the loop before shifting occurs.

Answer 5

Successive approximation will minimize the iterations to five loops:

unsigned int mostSignificantBit(uint32_t val) {
  unsigned int bit = 0;

  /* 4 = log(sizeof(val) * 8) / log(2) - 1 */
  for(int r = 4; r >= 0 ; --r) {
    unsigned shift = 1 << r; /* 2^r */
    uint32_t sval = val >> shift;
    if (sval) {
        bit += shift;
        val = sval;
    }
  }
  return bit;
}

Answer 6

Not the most efficient, perhaps, but this should work::

public int firstBit(int i) {
    return i < 0 ? 31 : i == 0 ? 0 : Integer.toString(i, 2).length();
}

Answer 7

Just use numberOfTrailingZeros(value) method of Long or Integer class.

Answer 8

For Little Endian format:

((yourByte & yourBitMask) >> msbIndex) && 0x01

Answer 9

Just to add another approach

public static int mostSignificantBit(int b) {
    for (int i = 1 << 30, j = 0; i > 0; i /= 2, j++) {
           if ((b & i) > 0) {
            return 31-j;
        }
    }
    return -1;
}

Answer 10

if( value | 0x40 ) return 7;
else if( value | 0x20 ) return 6;
else if( value | 0x10 ) return 5;
else if( value | 0x8 ) return 4;
else if( value | 0x4 ) return 3;
else if( value | 0x2 ) return 2;
else if( value | 0x1 ) return 1;