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.

Solution 1

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.

Solution 2

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).

Solution 3

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

Solution 4

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

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

View more solutions

Comments

[Admin]

What did you try in detail? What was the result?

[Ted Hopp]

What happened to returning 8 through 31?

[Ted Hopp]

Actually the use of the unsigned right shift operator is important. If myInt is not negative, then you'll need to shift mask and it starts off as a negative value.

[Michael McGowan]

You're correct that mask will always have a leading 1 that doesn't belong if the signed right shift is used (since mask starts out as negative). However, this doesn't affect results of my implementation because when myInt is not negative, that superfluous 1-bit is always being anded with a 0 (i.e. the sign bit of myInt, which we just said was positive).

[Ted Hopp]

Good point! I hadn't worked through the consequences of having leading 1s in mask, which (as you point out) are precisely nothing.

[Stefan Reich]

No... just no. Yes it works, but ouch is it wasteful.