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

在ulong（C#）中，从最低有效位（LSB）到最高有效位（MSB）获得第一组（1）位位置的最快（或至少非常快）方法是什么？对于ulong i = 18;（10010），这将是2（或者如果我们从0开始计算位置，则为1）。

MS C++编译器具有用于此任务的_BitScanForward64内部函数，但C#编译器没有类似函数

随着.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);

public static UInt64 CountTrailingZeros(UInt64 input)
{
    if (input == 0) return 64;
    UInt64 n = 0;
    if ((input & 0xFFFFFFFF) == 0) { n = 32; input = input >> 32; }
    if ((input & 0xFFFF) == 0) { n = n + 16; input = input >> 16; }
    if ((input & 0xFF) == 0) { n = n + 8; input = input >> 8; }
    if ((input & 0xF) == 0) { n = n + 4; input = input >> 4; }
    if ((input & 3) == 0) { n = n + 2; input = input >> 2; }
    if ((input & 1) == 0) { ++n; }
    return n;
}

我更改了迈克尔·D·奥的答案以匹配你的问题。

我测量了所有答案的表现。

获胜者不在这里，经典的德布鲁因序列方法。

    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编译器之后将Bit Scan Forward（bsf）Bit指令注入程序集，而不是BitScanForward主体，但这需要付出更多的努力。

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;
}

我敢打赌这会更快。从这里开始。

static Int32 GetLSBPosition(UInt64 v) {
    UInt64 x = 1;
    for (var y = 0; y < 64; y++) {
        if ((x & v) == x) {
            return y;
        }
        x = x << 1;
    }
    return 0;
}

虽然与Alexander的答案相似，但这种形式的执行速度始终更快，在我的机器上每秒约有4600万次操作。

此外，我已经把它写为基于零，但我个人认为它应该是基于1的，例如：

Assert.Equal(0, GetLSBPosition(0));
Assert.Equal(1, GetLSBPosition(1));
Assert.Equal(1, GetLSBPosition(3));

作为逐位操作，最低设置位为：

ulong bit = x & ~(x-1);

并且最低开启位设置为关闭的原始值为：

x & (x-1)

所以要获得所有的比特：

public static void Main()
{
    ulong x = 13;
    while(x > 0)
    {
        ulong bit = x & ~(x-1);
        x = x & (x-1);
        Console.WriteLine("bit-value {0} is set", bit);
    }
}

输出

bit-value 1 is set
bit-value 4 is set
bit-value 8 is set

具有非常快速的位操作的解决方案。只有不安全的代码才能更快。

ulong n = 18; // 10010
ulong b = 1;
int p = 0;
for (int i = 0; i < 64; i++)
{
    if ((n & b) == b)
    {
        p = i;
        break;
    }
    b = b << 1;
}
Console.WriteLine(p);

相关内容

最新更新

热门标签：