• 欢迎访问搞代码网站,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站!
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏搞代码吧

redis当中的二进制位数组

redis 海叔叔 23小时前 4次浏览 已收录 0个评论

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

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


喜欢 (0)
[搞代码]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址