Make delicious recipes!

Find position of MSB in binary representation of an integer



Problem: Find position of MSB (Most Significant Bit) in binary representation of an integer.
For example, binary representation of 4 is 100 and the MSB in it is present at position 2
Similarly, binary representation of 99 is 1 100 011 and the MSB in it is present at position 6.


Solution: A naive solution for this problem would be to shift the given integer by 1 and increment a count till the number is 0.
However, that would need 'k' iterations of the for loop where k is the position of the last 1.
For example, for 99, the loop would require to be executed 7 times.

This can be optimized by using binary search to find MSB position.
We first find MSB in 31-16 bits. If found, then we find in 31-24 bits, else in 24-17 bits.
So, the loop iterations are reduced to a maximum of log2(32) = 5.

Code:

void findPositionOfMSB (int n) 
{
    int high=31, low=0;

    while (high - low > 1)
    {
        int mid = (high+low)/2;
        int maskHigh = (1 << high) - (1 << mid);
        if ((maskHigh & n) > 0)
        {
            low = mid;
        }
        else
        {
            high = mid;
        }
    }
    System.out.println(n + ": MSB at " + low + ". Between " + (int)Math.pow(2, low) + " and " + (int)Math.pow(2, low+1));
}

Sample Run for some random integers:
0        :  MSB at 0.
4003     :  MSB at 11.  Between 2048 and 4096
12887    :  MSB at 13.  Between 8192 and 16384
28268    :  MSB at 14.  Between 16384 and 32768
59799    :  MSB at 15.  Between 32768 and 65536
120753   :  MSB at 16.  Between 65536 and 131072
247851   :  MSB at 17.  Between 131072 and 262144
500777   :  MSB at 18.  Between 262144 and 524288
1005372  :  MSB at 19.  Between 524288 and 1048576
2018676  :  MSB at 20.  Between 1048576 and 2097152
4044500  :  MSB at 21.  Between 2097152 and 4194304
8091824  :  MSB at 22.  Between 4194304 and 8388608
16185494 :  MSB at 23.  Between 8388608 and 16777216
32374804 :  MSB at 24.  Between 16777216 and 33554432
64755652 :  MSB at 25.  Between 33554432 and 67108864








Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal