3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ If $x=2$, then $x \& (x+1) = 2$, so it does not clear all the bits. The most significant bit stays as $1$. $\endgroup$ – Damien Dec 6 '18 at 9:29
  • 1
    $\begingroup$ @Daniel Beale Yes, sorry, it is ~$x$ instead of $x$. The negation of $x$. I have changed it. $\endgroup$ – plus1 Dec 6 '18 at 10:48
  • $\begingroup$ Have a look at this related SO post. $\endgroup$ – Axel Kemper Dec 6 '18 at 13:14
  • $\begingroup$ 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$. $\endgroup$ – Damien Dec 6 '18 at 15:02
  • 1
    $\begingroup$ 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. $\endgroup$ – Damien Dec 6 '18 at 15:06
3
+50
$\begingroup$

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.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.