redis设计与实现之二进制位数组篇

redis提供了setbit、getbit、bitcount、bitop四个命令用于处理二进制位数组

setbit命令用于为位数组指定偏移量上的二进制设置值,只能赋值0或者1
getbit命令用于获取位数组指定偏移量上的二进制位的值
bitcount命令用于统计位数组里面,值为1的二进制位的数量
bitop命令既可以对多个数组进行按位与(and)按位或(or)按位异或(xor)

位数组的表示

注释:buf数组采用逆序来保存位数组

位数组命令的实现

getbit命令实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
GETBIT <bitarray> <offset>
计算 byte = [offset / 8] , byte 值记录了 offset 偏移量指定的二进制位保存在位数组的哪个字节
计算 bit = (offset mod 8) + 1 , bit 值记录了 offset 偏移量指定的二进制位是 byte 字节的第几个二进制位
根据 byte 值和 bit 值, 在位数组 bitarray 中定位 offset 偏移量指定的二进制位, 并返回这个位的值(返回的是原来的值,切记)
case如下
GETBIT <bitarray> 3
[3 / 8] 的值为 0
(3 mod 8) + 1 的值为 4
定位到 buf[0] 字节上面, 然后取出该字节上的第 4 个二进制位(从左向右数)的值
向客户端返回二进制位的值 (如果是1返回1,如果是0返回0)
注释:时间复杂度位O(1)

setbit命令实现

1
2
3
4
5
6
7
8
9
10
SETBIT <bitarray> <offset> <value>
计算len=[offset / 8]+1,len值记录了保存offset偏移量指定的二进制位至少需要多少字节
检查bitarray键保存的位数组(sds)的长度是否小于len,如果是则将sds的长度扩展为len字节,并将所有新扩展空间的二进制位的值设为0
计算byte=[offset / 8],byte值记录了offset偏移量指定的二进制位保存在位数组的哪个字节
计算bit=(offset mod 8)+1,bit值记录了offset偏移量指定的二进制位是byte字节的第几个二进制位
根据byte值和bit值,在bitarray键保存的位数组中定位offset偏移量指定的二进制位,首先将制定二进制位现在值保存在oldvalue变量,然后将新值value设置为这个二进制位的值
向客户端返回oldvalue变量的值
注释:时间复杂度位O(1)

bitcount命令实现

bitcount命令的实现用到了查表和variable-precisionSWAR两种算法

1
2
3
4
5
6
7
8
查表算法使用键长位8位的表,表中记录了从0000 0000到1111 1111 在内的所有二进制位的汉明重量
至于variable-precisionSWAR算法方面,bitcount命令在每次循环中载入128个二进制位,然后调用四次32位variable-precisionSWAR算法来计算这128个二进制位的汉明重量
在执行bitcount命令时,程序会根据未处理的二进制位的数量来决定使用哪种算法
如果未出的二进制位的数量大于等于128位,那么程序使用variable-precisionSWAR算法计算汉明重量
如果未出的二进制位的数量小于128位,那么程序使用查表法计算汉明重量
注释:时间复杂度位O(n)

bitop命令实现

1
2
没什么好说的,和C语言一样的逻辑操作
因为bitop and、bitop or、bitop xor三个命令可以接受多个位数作为输入,程序需要遍历输入的每个位数组的每个字节来进行计算,所有这些命令的复杂度位O(n^2),与此相反,bitop not命令只接受一个位数组的输入,复杂度位O(n)