c# - Fast way of finding most and least significant bit set in a 64-bit integer

Question

There are a lot of questions about this on StackOverflow. A lot. However I cannot find an answer that:

• Works in C#
• Works for 64-bit integers (as opposed to 32-bit)

Faster than:

private static int Obvious(ulong v)
{
    int r = 0;
    while ((v >>= 1) != 0) 
    {
        r++;
    }
    return r;
}

Or even

int r = (int)(Math.Log(v,2));

I'm assuming a 64-bit Intel CPU here.

One useful reference is the Bit Hacks page and another is fxtbook.pdf However, while these gives useful direction to approach the problem, they do not give a ready answer.

I'm after a re-usable function that can do something similar to _BitScanForward64 and _BitScanReverse64 only for C#.

Answer 1

.NET Core 3.0 added BitOperations.LeadingZeroCount and BitOperations.TrailingZeroCount so you can use them directly. They'll be mapped to the x86's LZCNT/BSR and TZCNT/BSF instructions, hence extremely efficient

int mostSignificantPosition = 63 - BitOperations.LeadingZeroCount(0x1234L);
int leastSignificantPosition = BitOperations.TrailingZeroCount(0x1234L);

Alternatively the most significant bit's position can be calculated like this

int mostSignificantPosition = BitOperations.Log2(x - 1) + 1