Least and most significant bit calculation using bitwise operations

Question

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?

Answer 1

I just came across this hack from an old book about chess programming:

$$ y=XOR(x,x-1)=00...001111...11, $$

where the leftmost $1$ in $y$ is the leftmost $1$ of $x$, ie the MSB of $x$. Then we can add $1$ and shift right by $1$. I am not an expert but I think it's faster than what we 've seen here.

Answer 2

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.