# Least and most significant bit calculation using bitwise operations

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?

• If $x=2$, then $x \& (x+1) = 2$, so it does not clear all the bits. The most significant bit stays as $1$. – Damien Dec 6 '18 at 9:29
• @Daniel Beale Yes, sorry, it is ~$x$ instead of $x$. The negation of $x$. I have changed it. – plus1 Dec 6 '18 at 10:48
• Have a look at this related SO post. – Axel Kemper Dec 6 '18 at 13:14
• You might have thought that would work, but addition can carry from one bit to the next. The bitwise and operates on each bit independently. This means that $\&$ does not distribute over $+$. Again, if $x=2$ then $x\&(\sim x + 1) = 2$. – Damien Dec 6 '18 at 15:02
• Usually to extract a bit at a particular location we use a bit mask' with a one in the location that needs to be extracted. – Damien Dec 6 '18 at 15:06

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.

• With the obvious generalization for 64-bit I guess.. – plus1 Dec 14 '18 at 20:26
• You’re right we only add the line “x|=(x>>32)” – narek Bojikian Dec 15 '18 at 10:50

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.

• Hey, that's a lie, isn't it? It returns the rightmost bit ie the LSB, not the MSB ??!! – plus1 Dec 19 '18 at 6:44