There are a lot of questions about this on StackOverflow. A lot. However I cannot find an answer that:
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#.
.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
One of the ways of doing this, that is described on the Bit Hacks page linked in the question is leveraging De Bruijn sequence. Unfortunately this page does not give a 64-bit version of said sequence. This useful page explains how De Bruijn sequences can be constructed, and this one gives an example of the sequence generator written in C++. If we adapt the given code we can generated multiple sequences, one of which is given in the C# code below:
public static class BitScanner
{
private const ulong Magic = 0x37E84A99DAE458F;
private static readonly int[] MagicTable =
{
0, 1, 17, 2, 18, 50, 3, 57,
47, 19, 22, 51, 29, 4, 33, 58,
15, 48, 20, 27, 25, 23, 52, 41,
54, 30, 38, 5, 43, 34, 59, 8,
63, 16, 49, 56, 46, 21, 28, 32,
14, 26, 24, 40, 53, 37, 42, 7,
62, 55, 45, 31, 13, 39, 36, 6,
61, 44, 12, 35, 60, 11, 10, 9,
};
public static int BitScanForward(ulong b)
{
return MagicTable[((ulong) ((long) b & -(long) b)*Magic) >> 58];
}
public static int BitScanReverse(ulong b)
{
b |= b >> 1;
b |= b >> 2;
b |= b >> 4;
b |= b >> 8;
b |= b >> 16;
b |= b >> 32;
b = b & ~(b >> 1);
return MagicTable[b*Magic >> 58];
}
}
I also posted my C# port of the sequence generator to github
Another related article not mentioned in the question with decent cover of De Bruijn sequences, can be found here.
As per my comment, this is a function in C# to count leading zero bits modified for a 64 bit integer.
public static UInt64 CountLeadingZeros(UInt64 input)
{
if (input == 0) return 64;
UInt64 n = 1;
if ((input >> 32) == 0) { n = n + 32; input = input << 32; }
if ((input >> 48) == 0) { n = n + 16; input = input << 16; }
if ((input >> 56) == 0) { n = n + 8; input = input << 8; }
if ((input >> 60) == 0) { n = n + 4; input = input << 4; }
if ((input >> 62) == 0) { n = n + 2; input = input << 2; }
n = n - (input >> 63);
return n;
}
UPDATE:
If you're using a newer version of C#, check to see if this is built-in per the answer below.
https://stackoverflow.com/a/61141435/1587755