redis当中使用字符串对象来表示位数组,因为字符串对象使用的sds数据结构是二进制安全的,所以程序可以直接使用sds结构来保存位数组,并使用sds结构的操作函数来处理位数组
至于计算具体位就用offset/8和(offset mod 8)来计算具体的位了~
这边主要讲讲bitcount命令的实现
这里主要是用到了一个叫做计算汉明重量的东西(Hamming Weight),它本身就表示一个位数组中非0二进制位的数量,目前已知效率最好的通用算法为variable-precision SWAR算法,该算法通过一系列位移和位运算操作,可以在常数时间内计算多个字节的汉明重量,并且不需要额外的内存
-
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
-
}
总体思路就是:
1. 步骤1 计算出值i的二进制表示可以按每两个二进制位为一组进行分组,各组的十进制表示就是该组的汉明重量
2. 步骤2 计算出的值i的二进制表示可以按每4个二进制位为一组进行分组,各组的十进制表示就是该组的汉明重量
3. 步骤3 计算出的值i的二进制表示可以按每8个二进制位一组进行分组,各组的十进制表示就是该组的汉明重量
4. 步骤4计算出bitarray的汉明重量并记录在二进制位的最高8位,最终返回实际值
在redis当中,执行bitcount命令时,程序会根据未处理的二进制位的数量来决定使用哪种算法,如果剩余二进制位大于128, 则使用swar来计算,如果小于128,则采用查表法计算
其余的命令就比较简单了,就不在这里赘述了~
阅读(4719) | 评论(0) | 转发(0) |