2
$\begingroup$

So I have an integer $x$ between $1$ and $2^{64}$ and I am looking for the fastest way to get the rightmost 1 (the least significant bit or LSB) and the leftmost 1 (the most significant bit, MSB). How to do this in Mathematica? Can it be done without branching?

Any ideas are welcome.

$\endgroup$
5
  • $\begingroup$ Maybe I misunderstand the question, but wouldn't the leftmost digit be 0 if the number is less than 2^32 and 1 if it is greater, and the rightmost would be 1 if it's odd and 0 if its even... $\endgroup$
    – bill s
    Commented Apr 12, 2023 at 19:32
  • $\begingroup$ The leftmost and rightmost 1 is what we are after $\endgroup$
    – Georgy
    Commented Apr 12, 2023 at 19:36
  • 1
    $\begingroup$ A lot of CPUs support this function natively, so for ultimate speed I'd recommend going bare-metal by writing a C function and linking it in. $\endgroup$
    – Roman
    Commented Apr 12, 2023 at 20:02
  • $\begingroup$ BitLength for leftmost. As already noted, IntegerExponent[...,2] for the rightmost. $\endgroup$ Commented Apr 12, 2023 at 23:01
  • $\begingroup$ 64-Part[Flatten[IntegerDigits[8649436750036656,2,64]],{1,-1}] gives {52, 4} in little-endian bit numbering. $\endgroup$
    – anon
    Commented Apr 13, 2023 at 3:26

3 Answers 3

3
$\begingroup$

You can use IntegerLength and IntegerExponent:

SeedRandom[77];

x = RandomInteger[{1, 2^64}]
8649436750036656
IntegerDigits[x, 2]

{1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0}

{IntegerLength[x, 2], 1 + IntegerExponent[x, 2]}
{53, 5}

IntegerExponent >> Details

enter image description here

$\endgroup$
0
$\begingroup$
64-Part[Flatten[IntegerDigits[8649436750036656,2,64]],{1,-1}] gives {52, 4} in little-endian bit numbering.
$\endgroup$
0
$\begingroup$
64-Part[Flatten[IntegerDigits[8649436750036656,2,64]],{1,-1}]

gives {52, 4} in little-endian bit numbering.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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