1

该popcount函数返回输入中 1 的数量。0010 1101有popcount4 个。

目前，我正在使用这个算法来获得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）。

有没有办法根据这个约束做出更有效的popcount？如果输入是01011 11101 10011，它只会返回 2 因为它只关心最右边的那些。似乎任何类型的循环都比现有解决方案慢。

4

1 回答 1

1

这是一个执行“查找最高集”（二进制对数）的 C# 实现。它可能会也可能不会比您当前的 PopCount 快，它肯定比使用真实clz和/或popcntCPU 指令慢：

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);
}
于 2015-03-28T21:19:43.787 回答