Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
484 views
in Technique[技术] by (71.8m points)

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

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#.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

.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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...