Chinaunix首页 | 论坛 | 博客
  • 博客访问: 630665
  • 博文数量: 99
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1299
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(99)

文章存档

2019年(51)

2018年(47)

2017年(1)

我的朋友

分类: NOSQL

2019-11-10 20:25:06

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,则采用查表法计算
其余的命令就比较简单了,就不在这里赘述了~
阅读(3079) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册