获取每个设置位的连续索引的最快方法？

Question

假设我有一个整数，它的二进制表示是：

1001 1011 0111 0001 0010 1100 1000 1111

我正在寻找一种方法来获取每个设置位的连续索引。我正在将数组元素从一个数组移动到另一个数组。元素个数就是个数

在此示例中，第一个数组的前 4 个元素将移动到第二个数组的前 4 个索引（从右侧开始：LSB）。

然而，在那之后，第一个数组的第五个元素将改为移动到第二个数组的第 8 个索引，因为有 3 个零的间隙（所以第 8 个索引 = 索引 7）。

希望你现在能看到模式。我考虑过可能转换为字符串并进行循环，但这似乎很慢。我也可以在循环中使用这样的位操作：

x & (x-1) 清除下一个设置位

和

(int)Math.Log((x & ~(x - 1)), 2); 查找下一个设置位。

还有一个解决方案，只需保留一个运行索引，并在每次迭代中保持 1 并移动 1。

但我不确定是否有更好的方法，或者我是否遗漏了一些更简单的方法。

Answer 1

我认为带有运行索引的简单循环应该可以正常工作。调用 Math.Log 肯定不会更快，De Bruijn 也不会攻击黑客操作。如果可以 assembly/intrinsics 在 c# 中找到 leading/trailing 0 可能会做一些更好的事情。

现在，我建议使用简单的循环，当 mask 变为 0 时有一个终止标准，如：

static void CopyByMask<T>(UInt32 mask, T[] srcArray, T[] destArray)
{
    // Note: assumes arrays are appropriately sized.
    var srcPos = 0;
    for (var destPos = 0; mask != 0; destPos++)
    {
        if ((mask & 1) == 1)
            destArray[destPos] = srcArray[srcPos++];
        mask >>= 1;
    }
}

获取每个设置位的连续索引的最快方法？

Fastest way to get consecutive index of each set bit?

c#

arrays

binary

bit-manipulation