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=(\overline{abcdefgh})_2$，拆分为$\overline{ab \ cd \ ef \ gh}$。

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

以最开始的$x=(\overline{abcdefgh})_2$为例，首先做与运算得到$x_1=\overline{0b0d0f0h}$，然后右移一位做与运算得到$x_2=\overline{0a0c0e0g}$，这里设相加的结果为$x’=x_1+x_2=\overline{ABCDEFGH}$。

接下来，我们需要将$\overline{AB \ CD \ EF \ GH}$中每一组位置中的数值相加，即$\overline{AB} + \overline{CD} + \overline{EF} + \overline{GH}$，这里也可以用上面类似的方法计算，只是需要两位两位地移动。即：$\overline{00CD00GH}+\overline{00AB00EF}=\overline{A’B’C’D’ \ E’F’G’H’}$。接下来再进行一次$\overline{0000E’F’G’H’}+\overline{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