更好的 popcnt

日期:
标签: cpp trick

众所周知 是一个十分常用的算法。

它是用于统计二进制数字中 的个数的算法。

暴力算法

容易得到常规做法是 的。

如下:

unsigned int lowbit(unsigned int x)
{
    return x & (-x);
}

// O(n)
int popcnt1(unsigned int x)
{
    int result = 0;
    while (x)
    {
        x -= lowbit(x);
        result++;
    }
    return result;
}

这太慢了,考虑优化。

分析

我们先只考虑 字节的简单情况。

考虑建一个线段树,维护区间 中的 的个数,当然我们并不会对其进行区间的修改,也只会查询区间 (一字节 位)中的 个数。

比如说数

所以只需要对于这个数执行建树操作,再直接返回根节点的值。

首先,我们注意到对于 C++ 的数据类型都是 ,因此一定可以建成一个满二叉树。

其次,注意到当 时,,所以 一定可以在长度为 的一个二进制数中表示出,因此每一层的建树操作都可以在一个整形变量中完成。

再然后,由于我们只返回根节点的数,类似滚动数组,我们不必保存其他的数,可以至始至终都在一个变量里完成操作。

了解这些性质后,我们便可以完成建树操作了。

对于最底下一层,我们不需要操作,因为当该位为 时,有 ,为 则有 (废话)。

接着每向上一层,便错位相加,如下:

我们把当前状态分为 两组,所以我们只需要把所有 组的数右移再加上 组的数,便得到了下一层的数。

举例:现在我们有 节),Misplaced &11101001 \\& 10101010 >> 1 = 01010100,再加上 Misplaced &11101001 \\& 01010101 = 01000001 便得到了

最终便可以写出代码了:

// O(lg(n))
int popcnt2(unsigned int x)
{
    x = ((x & 0xaaaaaaaa) >> 1) + (x & 0x55555555); // 0xaa = 10101010, 0x55 = 01010101
    x = ((x & 0xcccccccc) >> 2) + (x & 0x33333333); // 0xcc = 11001100, 0x33 = 00110011
    x = ((x & 0xf0f0f0f0) >> 4) + (x & 0x0f0f0f0f); // 0xf0 = 11110000, 0x0f = 00001111
    x = ((x & 0xff00ff00) >> 8) + (x & 0x00ff00ff);
    x = ((x & 0xffff0000) >> 16) + (x & 0x0000ffff);
    return x;
}

用时

benchmark:
popcnt1() * 1000000000, time = 56.269000s
popcnt2() * 1000000000, time = 6.124000s

题外话

其实开了 -O2 后两个方法耗时都差不多。