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

Question

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

Answer 1

在 .NET Core 3.0 中，x86popcnt内在函数已公开，允许您对 uint 或 uint64 执行单指令人口计数计算。

int setBits = System.Runtime.Intrinsics.X86.Popcnt.PopCount(value);

还有一个 64 位版本System.Runtime.Intrinsics.X86.Popcnt.X64.PopCount()，可以ulong在 64 位 CPU 上运行时使用。

Answer 2

是重复的: 如何实现-bitcount-only-only-bitwise-operators 或 best-algorithm-to-count-of-set-bits-in-a-32-bit-integer

这个问题有很多解决方案.我使用的是:

    int NumberOfSetBits(int i)
    {
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }

Answer 3

BitOperations.PopCountCore 3.0 及更高版本中提供了独立于平台的功能。

如果可用，则使用硬件内在函数，否则默认为软件后备。目前支持X86/64和ARM处理器。

来源

完全归功于@Mark，他在另一个答案的评论中提到了这一点。

Answer 4

这个讨厌的黑客页面有很多选项.

当然,您可以争辩说,迭代所有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个简单位操作慢.

当然,在采用特别深奥的方法之前,值得测试你的应用程序的真实性能......这真的是你的瓶颈吗？