c# - 在 UInt32 中计算设置位的最快方法是什么

Question

在不使用查找表的情况下计算 UInt32 中设置位的数量(即计算 1 的数量)的最快方法是什么？有没有办法在 O(1) 中计数？

Answer 1

bit-twiddling hacks页面有许多选项。

当然，您可以争辩说遍历所有 32 个可能的位是 O(N)，因为每次的成本都相同 :)

为简单起见，我会考虑逐字节查找表的方法，或者 Brian Kernighan 的巧妙想法，它迭代的次数与设置的位一样多，我将其写为:

public static int CountBits(uint value)
{
    int count = 0;
    while (value != 0)
    {
        count++;
        value &= value - 1;
    }
    return count;
}

如果您不喜欢填充 256 个条目的查找表的想法，每个 nybble 的查找仍然会非常快。请注意，8 次数组查找可能比 32 次简单的位操作慢。

当然，在采用特别深奥的方法之前，测试您应用的真实性能是值得的……这真的是您的瓶颈吗？