簡介
在Redis中的BITCOUNT命令可以實(shí)現(xiàn)統(tǒng)計(jì)一個(gè)key對(duì)應(yīng)的二進(jìn)制數(shù)組1的個(gè)數(shù)始绍，它的實(shí)現(xiàn)方式便是查表法+variable-precision SWAR來提高效率食店。當(dāng)位數(shù)小于28字節(jié)時(shí)使用查表法榛鼎，大于等于28字節(jié)時(shí)使用variable-precision SWAR算法。
查表法
查表法比較簡單，Redis使用8位的表記錄了所有的情況，例如
| 鍵 | 值 |
|---|---|
| 0000 0000 | 0 |
| 0000 0001 | 1 |
| 片迅。。皆辽。 | 柑蛇。 |
| 1111 1110 | 7 |
| 1111 1111 | 8 |
對(duì)于小于28字節(jié)的數(shù)組芥挣，每8位查表一次，累加就是1的個(gè)數(shù)了
variable-precision SWAR
而對(duì)于超過28個(gè)字節(jié)的數(shù)組使用variable-precision SWAR算法,下面來介紹下該算法耻台，首先看如下代碼空免，它是計(jì)算一個(gè)32位數(shù)組的含有1的個(gè)數(shù)
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;
}
下面對(duì)每一步進(jìn)行解析
- 第一步
0x55555555 轉(zhuǎn)換為二進(jìn)制為：
01010101 01010101 01010101 01010101
注意到它的特點(diǎn)，偶數(shù)位為0粘我，奇數(shù)位為1，那么與這個(gè)數(shù)與操作會(huì)得到什么呢痹换？我們先把問題縮減下征字，考慮它的循環(huán)體為01，考慮兩位的情況娇豫，所有的數(shù)有四種分別為00匙姜、01、10冯痢、11氮昧，分別于01與結(jié)果如下所示：
| 所有情況 | 01 |
|---|---|
| 00 | 00 |
| 01 | 01 |
| 10 | 00 |
| 11 | 01 |
它得到的是奇數(shù)位1的個(gè)數(shù)，如果把這四種情況都右移一位浦楣，那么得到的就是原數(shù)偶數(shù)位1的個(gè)數(shù)袖肥。所以把這個(gè)結(jié)論推到0x55555555
i & 0x55555555 在每兩位上得到的是每兩位奇數(shù)位的1的個(gè)數(shù)，而((i >> 1) & 0x55555555)在每兩位上得到的是每兩位偶數(shù)位的個(gè)數(shù)振劳。二者相加得到的就是每兩位上1的個(gè)數(shù)椎组。
第二步
0x33333333轉(zhuǎn)換為二進(jìn)制為：
00110011 00110011 00110011 00110011
在上面的對(duì)于與01的結(jié)果得到的是偶數(shù)位1的個(gè)數(shù)，個(gè)數(shù)的取值范圍為00历恐、01寸癌、10，那么每四位與0011得到就是低兩位的1的個(gè)數(shù)弱贼，每四位右移兩位后與0011得到的就是高兩位的1的個(gè)數(shù)蒸苇，二者相加得到的就是每4位的1的個(gè)數(shù)第三步
0x0f0f0f0f 轉(zhuǎn)換為二進(jìn)制為：
00001111 00001111 00001111 00001111
在第二步中得到的是每四位分組的1的個(gè)數(shù)，同理與00001111得到就是低四位的1的個(gè)數(shù)吮旅，每四位分組右移四位后與00001111得到的高四位的1的個(gè)數(shù)溪烤，二者相加得到的是每8位的1的個(gè)數(shù)第四步
0x01010101轉(zhuǎn)換為二進(jìn)制為：
00000001 00000001 00000001 00000001
第三步得到的每8位一組統(tǒng)計(jì)的1的個(gè)數(shù)，一共有4組庇勃，該值乘以00000001 00000001 00000001 00000001氛什，舉個(gè)例子
假如32位數(shù)為：
00000011 00000111 10000111 01000011
00000001 00000001 00000001 00000001
00000011 00000111 10000111 01000011
00000111 10000111 01000011
10000111 01000011
01000011
注意下高8位已經(jīng)變成了四個(gè)分組之和了，所以最終得到的就是32位數(shù)中1的個(gè)數(shù)了
redis中的實(shí)現(xiàn)
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個(gè)字節(jié)匪凉，則使用variable-precision SWAR算法處理
while(count>=28) {
uint32_t aux1, aux2, aux3, aux4, aux5, aux6, aux7;
//取出28個(gè)字節(jié)枪眉，每次取4個(gè)，取7次
aux1 = *p4++;
aux2 = *p4++;
aux3 = *p4++;
aux4 = *p4++;
aux5 = *p4++;
aux6 = *p4++;
aux7 = *p4++;
count -= 28;
//下面兩步計(jì)算四位分組1的個(gè)數(shù)
aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
//下面兩步計(jì)算四位分組1的個(gè)數(shù)
aux2 = aux2 - ((aux2 >> 1) & 0x55555555);
aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333);
////下面兩步計(jì)算四位分組1的個(gè)數(shù)
aux3 = aux3 - ((aux3 >> 1) & 0x55555555);
aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333);
////下面兩步計(jì)算四位分組1的個(gè)數(shù)
aux4 = aux4 - ((aux4 >> 1) & 0x55555555);
aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333);
////下面兩步計(jì)算四位分組1的個(gè)數(shù)
aux5 = aux5 - ((aux5 >> 1) & 0x55555555);
aux5 = (aux5 & 0x33333333) + ((aux5 >> 2) & 0x33333333);
//下面兩步計(jì)算四位分組1的個(gè)數(shù)
aux6 = aux6 - ((aux6 >> 1) & 0x55555555);
aux6 = (aux6 & 0x33333333) + ((aux6 >> 2) & 0x33333333);
////下面兩步計(jì)算四位分組1的個(gè)數(shù)
aux7 = aux7 - ((aux7 >> 1) & 0x55555555);
aux7 = (aux7 & 0x33333333) + ((aux7 >> 2) & 0x33333333);
//計(jì)算8位分組1的個(gè)數(shù)再层，并使用乘法以及移位計(jì)算出總的1的個(gè)數(shù)
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個(gè)字節(jié)的使用查表法計(jì)算出
p = (unsigned char*)p4;
while(count--) bits += bitsinbyte[*p++];
return bits;
}
