[Math] Least and most significant bit calculation using bitwise operations

binarydiscrete mathematics

I am working on a project and I need to calculate the least significant bit (LSB) and most significant bit (MSB) of integers.

Suppose $x$ is an $n$-bit unsigned integer ($n=16, 32$ or $64$). We know that $y=x \ \& \ ($~$x+1)$ clears all the bits of $x$ except for the LSB. This is lightning fast, just three operations. Is there something similar for the MSB? What is the fastest way to compute it?

Best Answer

Here is a way that works in $\log(|n|)$ where |n| is the number of bits needed to represent $n$. Let's say we have a 32-bit integers.

MST(int x)
{
    x|=(x>>1);
    x|=(x>>2);
    x|=(x>>4);
    x|=(x>>8);
    x|=(x>>16);
    x++;
    x>>=1;
    return x;
}

The reason why this works is that the first 5 lines set all bits right to the mst to 1. By adding one to the number we flip them all (including mst) to zero and put a one the left of them all. we shift this one to the right (and hence it's now in the position of mst) and return the number.

Related Question