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

Question

popcount函数返回输入中 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(返回 5(或00000 11111 11111(返回 10(。

有没有办法基于此约束使弹出计数更有效？如果输入是01011 11101 10011的，它将只返回2，因为它只关心最右边的输入。似乎任何类型的循环都比现有解决方案慢。

Answer 1

下面是一个执行"查找最高集"(二进制对数(的 C# 实现。 它可能比您当前的 PopCount 快，也可能不快，它肯定比使用真正的 clz 和/或 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);
}