在ulong(C#)中获得最后一个有效位位置的最快方法？

Question

什么是从最低有效位(LSB)到ulong(C#)中的最高有效位(MSB)的第一个设置(1)位位置的最快(或至少非常快)的方法？对于ulong i = 18; (10010),将为2(如果我们从0开始计算位置,则为1).

MS C++编译器具有 _BitScanForward64用于此任务的内在函数,但C#编译器没有模拟.

Answer 1

随着 .NET Core 3.0 引入硬件内在函数，最快的解决方案应该是

ulong value = 18;
ulong result = System.Runtime.Intrinsics.X86.Bmi1.X64.TrailingZeroCount(value);

另外，新的 System.Numerics.Bitoperations 方法也使用硬件内部函数：

int result2 = System.Numerics.BitOperations.TrailingZeroCount(value);

Answer 2

我测量了所有答案的性能。

获胜者并不在这里出现经典的 De Bruijn 序列方法。

    private const ulong DeBruijnSequence = 0x37E84A99DAE458F;

    private static readonly int[] MultiplyDeBruijnBitPosition =
    {
        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,
    };

    /// <summary>
    /// Search the mask data from least significant bit (LSB) to the most significant bit (MSB) for a set bit (1)
    /// using De Bruijn sequence approach. Warning: Will return zero for b = 0.
    /// </summary>
    /// <param name="b">Target number.</param>
    /// <returns>Zero-based position of LSB (from right to left).</returns>
    private static int BitScanForward(ulong b)
    {
        Debug.Assert(b > 0, "Target number should not be zero");
        return MultiplyDeBruijnBitPosition[((ulong)((long)b & -(long)b) * DeBruijnSequence) >> 58];
    }

最快的方法是在 JIT 编译器之后将位扫描前向 (bsf) 位指令注入到程序集中，而不是注入 BitScanForward 主体，但这需要更多的努力。