在给定限制的情况下寻找更有效的流行计数

Question

popcount 函数 return 计算输入中 1 的数量。 0010 1101 的 popcount 为 4。

目前，我正在使用这个算法得到 popcount:

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

这很好用，我要求更多的唯一原因是因为这个操作运行非常频繁，我正在寻找额外的性能提升。

我正在寻找一种方法来简化算法，因为我的 1 总是右对齐的。也就是说，输入将类似于 00000 11111 (returns 5) 或 00000 11111 11111 (returns 10).

有没有一种方法可以根据这个约束来进行更有效的人口统计？如果输入是 01011 11101 10011，它只会 return 2 因为它只关心最右边的那些。似乎任何一种循环都比现有解决方案慢。

Answer 1

这是执行 "find highest set"（二进制对数）的 C# 实现。它可能比你当前的 PopCount 快也可能不快，它肯定比使用真正的 clz and/or popcnt CPU 指令慢：

static int FindMSB( uint input )
{
    if (input == 0) return 0;
    return (int)(BitConverter.DoubleToInt64Bits(input) >> 52) - 1022;
}

测试：http://rextester.com/AOXD85351

还有一个没有条件分支的细微变化：

/* precondition: ones are right-justified, e.g. 00000111 or 00111111 */
static int FindMSB( uint input )
{
    return (int)(input & (int)(BitConverter.DoubleToInt64Bits(input) >> 52) - 1022);
}

在给定限制的情况下寻找更有效的流行计数

Looking for a more efficient pop count given a restriction

c#

algorithm

binary

bit-manipulation

hammingweight