简介
在Redis中的BITCOUNT命令可以实现统计一个key对应的二进制数组1的个数，它的实现方式便是查表法+variable-precision SWAR来提高效率。当位数小于28字节时使用查表法，大于等于28字节时使用variable-precision SWAR算法。
查表法
查表法比较简单，Redis使用8位的表记录了所有的情况，例如
| 键 | 值 |
|---|---|
| 0000 0000 | 0 |
| 0000 0001 | 1 |
| 。。。 | 。 |
| 1111 1110 | 7 |
| 1111 1111 | 8 |
对于小于28字节的数组，每8位查表一次，累加就是1的个数了
variable-precision SWAR
而对于超过28个字节的数组使用variable-precision SWAR算法,下面来介绍下该算法，首先看如下代码，它是计算一个32位数组的含有1的个数
uint32_t swar(uint32_t i) {
//第一步
i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
//第二步
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
//第三步
i = (i & 0x0f0f0f0f) + ((i >> 4) & 0x0f0f0f0f);
//第四步
i = (i * (0x01010101) >> 24);
return i;
}
下面对每一步进行解析
- 第一步
0x55555555 转换为二进制为：
01010101 01010101 01010101 01010101
注意到它的特点，偶数位为0，奇数位为1，那么与这个数与操作会得到什么呢？我们先把问题缩减下，考虑它的循环体为01，考虑两位的情况，所有的数有四种分别为00、01、10、11，分别于01与结果如下所示：
| 所有情况 | 01 |
|---|---|
| 00 | 00 |
| 01 | 01 |
| 10 | 00 |
| 11 | 01 |
它得到的是奇数位1的个数，如果把这四种情况都右移一位，那么得到的就是原数偶数位1的个数。所以把这个结论推到0x55555555
i & 0x55555555 在每两位上得到的是每两位奇数位的1的个数，而((i >> 1) & 0x55555555)在每两位上得到的是每两位偶数位的个数。二者相加得到的就是每两位上1的个数。
第二步
0x33333333转换为二进制为：
00110011 00110011 00110011 00110011
在上面的对于与01的结果得到的是偶数位1的个数，个数的取值范围为00、01、10，那么每四位与0011得到就是低两位的1的个数，每四位右移两位后与0011得到的就是高两位的1的个数，二者相加得到的就是每4位的1的个数第三步
0x0f0f0f0f 转换为二进制为：
00001111 00001111 00001111 00001111
在第二步中得到的是每四位分组的1的个数，同理与00001111得到就是低四位的1的个数，每四位分组右移四位后与00001111得到的高四位的1的个数，二者相加得到的是每8位的1的个数第四步
0x01010101转换为二进制为：
00000001 00000001 00000001 00000001
第三步得到的每8位一组统计的1的个数，一共有4组，该值乘以00000001 00000001 00000001 00000001，举个例子
假如32位数为：
00000011 00000111 10000111 01000011
00000001 00000001 00000001 00000001
00000011 00000111 10000111 01000011
00000111 10000111 01000011
10000111 01000011
01000011
注意下高8位已经变成了四个分组之和了，所以最终得到的就是32位数中1的个数了
redis中的实现
size_t redisPopcount(void *s, long count) {
size_t bits = 0;
unsigned char *p = s;
uint32_t *p4;
//8位的表用于查表
static const unsigned char bitsinbyte[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};
/* Count initial bytes not aligned to 32 bit. */
while((unsigned long)p & 3 && count) {
bits += bitsinbyte[*p++];
count--;
}
/* Count bits 28 bytes at a time */
p4 = (uint32_t*)p;
//如果超过28个字节，则使用variable-precision SWAR算法处理
while(count>=28) {
uint32_t aux1, aux2, aux3, aux4, aux5, aux6, aux7;
//取出28个字节，每次取4个，取7次
aux1 = *p4++;
aux2 = *p4++;
aux3 = *p4++;
aux4 = *p4++;
aux5 = *p4++;
aux6 = *p4++;
aux7 = *p4++;
count -= 28;
//下面两步计算四位分组1的个数
aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
//下面两步计算四位分组1的个数
aux2 = aux2 - ((aux2 >> 1) & 0x55555555);
aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333);
////下面两步计算四位分组1的个数
aux3 = aux3 - ((aux3 >> 1) & 0x55555555);
aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333);
////下面两步计算四位分组1的个数
aux4 = aux4 - ((aux4 >> 1) & 0x55555555);
aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333);
////下面两步计算四位分组1的个数
aux5 = aux5 - ((aux5 >> 1) & 0x55555555);
aux5 = (aux5 & 0x33333333) + ((aux5 >> 2) & 0x33333333);
//下面两步计算四位分组1的个数
aux6 = aux6 - ((aux6 >> 1) & 0x55555555);
aux6 = (aux6 & 0x33333333) + ((aux6 >> 2) & 0x33333333);
////下面两步计算四位分组1的个数
aux7 = aux7 - ((aux7 >> 1) & 0x55555555);
aux7 = (aux7 & 0x33333333) + ((aux7 >> 2) & 0x33333333);
//计算8位分组1的个数，并使用乘法以及移位计算出总的1的个数
bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) +
((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) +
((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) +
((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) +
((aux5 + (aux5 >> 4)) & 0x0F0F0F0F) +
((aux6 + (aux6 >> 4)) & 0x0F0F0F0F) +
((aux7 + (aux7 >> 4)) & 0x0F0F0F0F))* 0x01010101) >> 24;
}
/* Count the remaining bytes. */
//小于28个字节的使用查表法计算出
p = (unsigned char*)p4;
while(count--) bits += bitsinbyte[*p++];
return bits;
}
