Bit Count算法学习笔记

2021-01-06

Word count: 2.2k | Reading time≈ 9 min

Pop_Count 位计数算法学习笔记

所谓Pop_Count算法，即Bit Population Count算法，解决的都是同一个简洁明了的问题——统计一个多位二进制数中‘1’的个数。如此简单的问题，不需要动脑子就可以想到循环判断的$O(n)$算法，而作为可能被频繁调用的功能，$O(n)$显然远算不上这个问题的最优解。在本篇中，我们将涉及多个”神乎其技“的Bit Count(位计数)算法，感受位操作与位运算的强大与奇妙。方便起见，本文将在C++语言下描述算法。

朴素算法

抛开效率上的需求，相信大部分人第一分钟都能想到一个最朴素的算法：逐位统计。利用位运算符，我们只需要写一个循环就可以实现Pop_Count了。对于一个32位的无符号整型，利用一个for循环解决问题。

int rekt_popcnt(unsigned int n)
{
	int count = 0;
	for(int i = 0;i<32;i++)
	{
		count += n&(0x01);
		n = n>>1;
	}
	return count; 
}

当然，这个算法的局限性非常大。该算法的时间复杂度是固定的，对远小于$2^32$的数据其复杂度依旧如此。

为了改进这个地方，我们保持逐位统计的思想，只需要对循环结构稍加优化即可：

int iterated_popcnt(unsigned int n)
{
    int count = 0;
    for(;n;n>>=1)
        count += n&(0x01);
    return count;
}

当n右移到一定次数后，n将会变为0，循环结束，这样就能根据输入数据的最大位数决定循环的次数了。

但是这样依然存在一个缺点，当只有n的较高位为1时，该算法还是会逐位地统计。例如对$2^31$这个数，该算法还是会迭代31次，但最后统计结果count却只有1。

Sparse算法与Dense算法

Sparse即稀疏，Dense即密集，顾名思义，这两种算法都是针对特殊的输入情况进行了优化。目前我们只对输入数据n引入了按位与运算和右移运算。而接下来的算法中将会体现减法在Pop_Count中的妙用。

int sparse_popcnt(unsigned int n)
{
    int count = 0;
    while(n)
    {
        ++count;
        n &= (n-1);
    }
    return count;
}

以数据42为例，我们从数学上来看一下这个算法的过程：
$$
42=00101010(bin)
$$

$$
41=00101001(bin)
$$

$$
42\space\mathit{AND}\space41=00101000(bin)=40
$$

经过一次n&=(n-1)的过程，我们直接将最低位的一个1给消除了。循环进行该过程每次消掉一个1，就完成了Pop_Count。也就是说，该算法的复杂度为$O(m)$，其中m为输入数据中1的个数。这比前文的朴素算法又在效率上提高了一个档次。但这也代表着效率取决于其中1的个数，1越少，时间开销越短，故称为Sparse稀疏算法。

如果我们知道了输入数据中1的个数很多，那自然可以反其道而行之，先取反再用Sparse统计，最后从最大位数中减去统计结果即可，这就是Dense算法。

int dense_popcnt(unsigned int n)
{
    /* CHAR_BIT is the number of bits in char. */
    /* In most cases it equals to 8,but some   */
    /* architectruers use more than 8 bits	   */
    /* reference:https://stackoverflow.com/questions/3200954/what-is-char-bit*/
    int count=CHAR_BIT*sizeof(unsigned int);
    n^=(unsigned int)-1;
    while(n)
    {
        --count;
        n&=(n-1);
    }
    return count;
}

我们通过让n与一个全1二进制数异或来达到取反的效果，之后就是同样的统计方法，只是这次我们进行倒数。

然而稀疏和密集始终是一对特殊情况，更多的数据是分布在这两者之间的，这两个算法在大多数情况下并没有优劣之分。

查表法

对于Pop_Count来说，对每个数据的答案永远是固定的。使用打表与查表的方式，虽然是以牺牲空间为代价换取效率，但在不同场合下找到正确的分治方法总能起到很好的效果，对于硬件（FPGA等）设计等可以并行运算的情况也可用。

在一般情况下，8位(一个字节)的查表法比较常用，对超过8位的数据，只要用0补齐到8*n位，再分别查表结果相加即可。

如果用比较死板的方式打表可以直接：

const int BITS_COUNT_TABLE[256] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

但打表的代码实现方式可以十分优雅，具体可参照文末参考中的博客KAIO2-2013^[1](可以说是本文资料的最大来源了)。

并行算法

并行加速可以说是Pop_Count快速算法目前的终极答案，对于硬件设计这也是非常优秀的设计方式，之后的算法中基本都是基于这个原理实现的。

考虑两位数据：

X1	X0	Count
0	0	00
0	1	01
1	0	01
1	1	10

我们的任务就是要找出从( [X1,X0] )到Count的映射。

如果你学过数字电路的话，这个真值表应该十分熟悉吧。如果不考虑X1和X0之间在同组数据当中的关系，这个映射关系实际就是全加器——X1(1bit)+X0(1bit)=Count(2bits)。但实际上，我们并不能直接就把它们拆开相加，而需要在运算上把它们先拆开再相加，设X为由它们组合而成的2位数据：

Count = (X&01)+((X>>1)&01)

如果分步来讲的话：

取出X的低位
将X的高位右移至低位
取出X的低位
将两次取出的值相加

在这个运算的推导过程中，我们需要用到掩码(Mask)这个概念来屏蔽和保留的低位数据。在上述2位数据的情况下，掩码为01。

把位数增加至4位来考虑，按上面的运算就不能一次得到结果了，这时我们要两两分组，掩码就变为了0101：

第一次迭代：

*X(4bits) = {Count_H(2bits),Count_L(2bits)} = *

(X&0101)+((X>>1)&0101)

此时高2位的Count结果和低2位的Count结果分别的存储在了高2位和低2位，我们还需要将它们加在一起。这时我们分取2位数据用的掩码就变成了0011。

第二次迭代：

Count(4bits) = (X&0011)+((X>>2)&0011)

在两次迭代后，得到Pop_Count结果。

归纳可以得到，每次迭代的运算表达式为：
$$
X = X&((2^N-1)/2^{2^n}) + (X>>2^n)&((2^N-1)/2^{2^n})
$$
其中$ N $为总位数，$ n $为当前迭代次数，$ (2^N-1)/2^{2^n} $就是掩码的表达式。

到这里不难看出这是典型的分治算法，称为并行算法的原因正式因为它同时完成了多个位数的统计，其迭代次数很轻松就能得证为$ \log_2^N $。

既然是并行算法，我们不妨用HDL来描述一下：

module parr_popcnt(Data,cnt);

	parameter n = 32;

	input [n-1:0] Data;
	
	output reg [4:0]cnt;
	
	reg [1:0]cnt2[16];
	reg [2:0]cnt4[8];
	reg [3:0]cnt8[4];
	reg [4:0]cnt16[2];
	
	integer i;
	
	always@(Data)
	begin
		cnt = 0;
		
		for(i=0;i<16;i=i+1)
			cnt2[i] = Data[2*i] + Data[2*i+1];
			
		for(i=0;i<8;i=i+1)
			cnt4[i] = cnt2[2*i] + cnt2[2*i+1];
			
		for(i=0;i<4;i=i+1)
			cnt8[i] = cnt4[2*i] + cnt4[2*i+1];
		
		for(i=0;i<2;i=i+1)
			cnt16[i] = cnt8[2*i] + cnt8[2*i+1];
		
		cnt = cnt16[0]+cnt16[1];
		
	end
	
endmodule

并行算法++

to be continue 2021.1.6 ====》

参考

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.