Find position of MSB in binary representation of an integerProblem: 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 |
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:
