Popcount问题及算法

在使用状态压缩或树状数组（Binary Indexed Tree）的时候，经常涉及位运算的操作。其中一类问题被称为Popcount问题：对于一个无符号整数x，求二进制表示下的x（即(x)2）中1的个数。

如：(2)10=(10)2，则x=2时答案为1；(255)10=(11111111)2，则x=255时答案为8。

很暴力的暴力 O(log⁡x)

直接将x以二进制形式转换为字符串，按照字符串的方法处理即可。

// Code by KSkun, 2019/10
int popcount(unsigned int x) {
    char str[32];
    memset(str, 0, sizeof(str));
    itoa(x, str, 2); // 以二进制转换x至字符串str
    int counter = 0;
    for (int i = 0; i < 32 && str[i] != 0; i++) {
        if (str[i] == '1') counter++;
    }
    return counter;
}

不那么傻的暴力 O(log⁡x)

直接用位运算处理上面那个暴力的流程不好吗？

// Code by KSkun, 2019/10
int popcount(unsigned int x) {
    int counter = 0;
    while (x > 0) {
        counter += (x & 1);
        x >>= 1;
    }
    return counter;
}

不那么暴力的暴力 最差O(log⁡x)

我们想起了在树状数组中常用的lowbit函数，可以利用那个每次找到一个1然后把它删掉，循环进行这个操作直至所有的1都被统计了一遍。

// Code by KSkun, 2019/10
int popcount(unsigned int x) {
    int counter = 0;
    while (x > 0) {
        counter++;
        x -= (x & -x);
    }
    return counter;
}

更好的算法：Shift and Add O(log⁡log⁡x)

这里可以采用类似分治的考虑方法。

我们将数字x按二进制拆分为2位为一组的形式，例如，令x=(abcdefgh―)2，拆分为abcdefgh―。

对于每一组的两个位，例如最高位一组的a和b，它们的取值非0即1，只需要把这两位上的值简单相加即可得到这两位的统计结果。由于1+1=2=(10)2，最多也只需占用2位来存储结果，因此不妨用这两位之前的空间来存储结果即可。对于“将相邻两位加起来，并存储在原来的这两位的位置上”这一操作，我们可以先对原数x与(01010101)2做按位与运算，再用原数右移一位的结果与(01010101)2做按位与运算，再将两个结果加起来即得到这一步的结果。

以最开始的x=(abcdefgh―)2为例，首先做与运算得到x1=0b0d0f0h―，然后右移一位做与运算得到x2=0a0c0e0g―，这里设相加的结果为x′=x1+x2=ABCDEFGH―。

接下来，我们需要将ABCDEFGH―中每一组位置中的数值相加，即AB―+CD―+EF―+GH―，这里也可以用上面类似的方法计算，只是需要两位两位地移动。即：00CD00GH―+00AB00EF―=A′B′C′D′E′F′G′H′―。接下来再进行一次0000E′F′G′H′―+0000A′B′C′D′―就可以得到结果了。

这种方法每次对相邻的两组做二分的分治，逐层合并结果（将相邻两组相加），最后得到结果。这是一种很巧妙的分治方法。

由于unsigned int本身的长度有限，可以直接以长度为总长度，就有了下面这种很tricky的实现。

// Code from http://leexh.com/blog/2014/10/25/popcount-problem/
// Author: lixinhe
// Adjusted to unsigned int
const unsigned int m1 = 0x55555555; //binary: 0101...
const unsigned int m2 = 0x33333333; //binary: 00110011..
const unsigned int m4 = 0x0f0f0f0f; //binary:  4 zeros,  4 ones ...
const unsigned int m8 = 0x00ff00ff; //binary:  8 zeros,  8 ones ...
const unsigned int m16 = 0x0000ffff; //binary: 16 zeros, 16 ones ...

int popcount(unsigned int x) {
    x = (x & m1) + ((x >> 1) & m1);
    x = (x & m2) + ((x >> 2) & m2);
    x = (x & m4) + ((x >> 4) & m4);
    x = (x & m8) + ((x >> 8) & m8);
    x = (x & m16) + ((x >> 16) & m16);
    x = (x & m32) + ((x >> 32) & m32);
    return x;
}

• Popcount Problem – lixinhe blog