redis当中的二进制位数组

redis当中使用字符串对象来表示位数组，因为字符串对象使用的sds数据结构是二进制安全的，所以程序可以直接使用sds结构来保存位数组，并使用sds结构的操作函数来处理位数组
至于计算具体位就用offset/8和(offset  mod   8)来计算具体的位了~
这边主要讲讲bitcount命令的实现
这里主要是用到了一个叫做计算汉明重量的东西（Hamming Weight），它本身就表示一个位数组中非0二进制位的数量，目前已知效率最好的通用算法为variable-precision SWAR算法，该算法通过一系列位移和位运算操作，可以在常数时间内计算多个字节的汉明重量，并且不需要额外的内存

点击(此处)折叠或打开

1. uint32_t swar(uint32_t i){
   
2.     i = (i&0x55555555) + ((i>>1)&0x55555555);
   
3.     i = (i&0x33333333) + ((i>>2)&0x33333333);
   
4.     i = (i&0x0f0f0f0f) + ((i>>4)&0x0f0f0f0f);
   
5.     i = (i * (0x01010101) >> 24);
   
6.     return i
   
7. }

总体思路就是：
1. 步骤1 计算出值i的二进制表示可以按每两个二进制位为一组进行分组，各组的十进制表示就是该组的汉明重量
2. 步骤2 计算出的值i的二进制表示可以按每4个二进制位为一组进行分组，各组的十进制表示就是该组的汉明重量
3. 步骤3 计算出的值i的二进制表示可以按每8个二进制位一组进行分组，各组的十进制表示就是该组的汉明重量
4. 步骤4计算出bitarray的汉明重量并记录在二进制位的最高8位，最终返回实际值
在redis当中，执行bitcount命令时，程序会根据未处理的二进制位的数量来决定使用哪种算法，如果剩余二进制位大于128， 则使用swar来计算，如果小于128，则采用查表法计算
其余的命令就比较简单了，就不在这里赘述了~