Redis提供了SETBIT,GETBIT,BITCOUNT,BITOP四个命令用于处理二进制位数组.
其中, SETBIT命令用于为位数组指定偏移量上的二进制设置值, 位数组的偏移量从0开始计数, 而二进制位的值则可以是0或者1。
GETBIT命令则用于获取位数组指定偏移量上的二进制位的值.
BIGCOUNT命令用于统计维数组里面, 值为1的二进制位的数量.
BITOP命令既可以对多个位数组进行按位与(and),按位或(or),按位异或(xor),取反操作(not)运算
位数组的表示
Redis使用字符串对象来表示位数组, 因为字符串对象使用的SDS数据结构是二进制安全的, 所以程序可以直接使用SDS结构来保存位数组, 并使用SDS结构的操作函数来处理位数组.
在使用redisObject保存位数组时, buf数组保存位数组的顺序和我们平时书写位数组的顺序是完全相反的. 例如: buf[0] 字节中, 各个位的值分别是: 1,0,1,1,0,0,1,0, 这表示buf[0]字节保存的位数组为0100 1101. 使用逆序来保存为数组可以简化SETBIT命令的实现。
GETBIT 命令的实现
GETBIT命令用于返回位数组bitarray在offset偏移量上的二进制位的值:
GETBIT <bitarray> <offset>
GETBIT命令的执行过程如下:
-
计算
byte=[offset / 8]0,byte值记录了offset偏移量指定的二进制位保存在位数组的哪个字节. -
计算
bit=(offset mod 8) + 1bit值记录了offset偏移量指定的二进制位是byte字节的第几个二进制位 -
根据
byte值和bit值, 在位数组bitarray中定位offset偏移量指定的二进制位, 并返回这个位的值.
GETBIT执行步骤
GETBIT <bitarray> 3
将执行以下操作:
-
[3/8]的值为0 -
(3 mod 8) + 1的值为4 -
定位到
buf[0]字节上面, 然后取出该字节上的第四个二进制位的值 -
向客户端返回二进制位上的
1
NOTE: 因为
GETBIT命令执行的所有操作都是可以在常数时间内完成, 所以该命令的算法复杂度为O(1)
SETBIT 命令的实现
SETBIT用于将数组bitarray在offset偏移量上的二进制位的值设置为value, 并向客户端返回二进制位被设置之前的旧值:
SETBIT <bitarray> <offset> <value>
以下是SETBIT命令的执行过程:
-
计算
len=[offset / 8] + 1,len值记录了保存offset偏移量指定的二进制位至少需要多少字节. -
检查
bitarray键保存的位数组(也即是SDS)的长度是否小于len, 如果是的话, 将SDS的长度扩展为len字节, 并将所有新扩展空间的二进制位的值设置为0(此处还是会遵循SDS的扩展原则) -
计算
byte=[offset / 8],byte值记录了offset偏移量指定的二进制位保存在维数组的哪个字节 -
计算
bit=(offset mod 8) + 1,bit值记录了offset偏移量指定的二进制位是byte字节的第几个二进制位. -
根据
byte值和bit值, 在bitarray键保存的维数组中定位offset偏移量指定的二进制位, 首先将指定二进制位在值保存在oldvalue变量, 然后将新值value设置为这个二进制位的值 -
向客户端返回
oldvalue变量的值.
因为SETBIT命令执行的所有操作都可以在常数时间内完成, 所以该命令的时间复杂度为O(1)
为什么SETBIT采用逆序存储???
BIGCOUNT 命令的实现
BITCOUNT命令用于统计给定位数组中, 值为1的二进制位的数量。
二进制位统计算法(1): 遍历算法
实现BITCOUNT命令最简单直接的办法, 就是遍历数组中的每个元素中的每个二进制位, 并在遇到值为1的二进制位时, 将计数器的值增加1
尽管遍历算法对单个二进制位的检查可以在很短的时间内完成, 但是重复执行上亿次这种检查肯定不是一个搞笑程序应有的表现, 为了让BITCOUNT命令的实现尽可能地高效, 程序必须尽可能地增加每次检查所能处理的二进制位的数量，从而减少检查操作执行的次数.
二进制统计算法(2): 查表算法
优化检查操作的一个办法是使用查找表:
-
对于一个有限集合来说, 集合元素的排列方式是有限的
-
而对于一个有限长度的位数组来说, 它能表示的二进制位排列也是有限的
根据这个原理,我们可以创建一个表, 表的键为某种排列的位数组, 而表的值则是相应位数组中, 值为1的二进制位的数量。
创建了这种表之后, 我们可以根据输入的位数组进行查表, 在无须对位数组的每个位进行检查的情况下, 直接知道这个位数组包含了多少个值为1的二进制位。
存在的问题
-
因为查表法是典型的空间换时间策略, 算法在计算方面节约的时间是通过花费额外的内存换取而来的, 节约的时间越多, 花费的内存越大
-
除了内存大小的问题之外, 查表法的效果还会受到CPU缓存的限制： 对于固定大小的CPU缓存来说, 创建的表格越大, CPU缓存所能保存的内容比整个表格的比例就越少, 查表时出现缓存不命中的情况就会越高, 混村的换入和换出操作就会越频繁, 最终影响查表法的实际效率。
为了搞笑地实现BITCOUNT命令, 我们需要一种不会带来内存压力, 并且可以在一次检查中统计多个二进制位的算法。
二进制位统计算法(3): variable-precision SWAR算法
BITCOUNT命令要结局的问题——统计一个位数组中非0二进制位的数量， 在数学上被称为计算汉明重量.
因为汉明重量经常被用于信息论, 编码理论和密码学, 所以研究人员针对计算汉明重量开发了多种不同的算法, 一些处理器甚至直接带有计算汉明重量的指令, 而对于不具备这种特殊命令的普通处理器来说, 目前已知效率最好的通用算法为variable-precision SWAR算法, 该算法通过一系列位移和位运算操作, 可以在常数时间内计算多个字节的汉明重量, 并且不需要使用任何额外的内存。
uint32_t swar(uint32_t i) {
// 步骤1
i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
// 步骤2
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
// 步骤3
i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);
// 步骤4
i = (i * (0x01010101) >> 24);
return i;
}
SWAR的执行步骤
-
步骤1: 计算出的值i的二进制标识可以按每两个二进制位位一组进行分组, 各组的十进制表示就是该组的汉明重量
-
步骤2: 计算出的值i的二进制标识可以按每四个二进制位为一组进行分组, 各组的十进制表示就是该组的汉明重量
-
步骤3: 计算出的值i的二进制标识可以按每8个二进制位为一组进行分组, 各组的十进制的表示就是该组的汉明重量
-
步骤4的
i * 0x01010101语句计算出bitarray的汉明重量并记录在二进制位的最高八位, 而>>24语句则通过右移运算, 将bitarray的汉明重量移动到最低八位, 得出的结果就是bitarray的汉明重量。
二进制位统计算法(4): Redis的实现
BITCOUNT命令的实现用到了查表和variable-precision SWAR两种算法:
-
查表算法使用键长位
8位的表, 表中记录了从0000 0000到1111 1111在内的所有二进制位的汉明重量 -
至于
variable-precision SWAR算法方面,BITCOUNT命令在每次循环中载入128个二进制位, 然后调用四次32位variable-precision SWAR算法来计算128个二进制位的汉明重量
在执行BITCOUNT命令时, 程序会根据未处理的二进制位的数量来决定使用哪种算法:
-
如果为处理的二进制位的数量大于等于
128位, 那么程序使用variable-precision SWAR算法来计算二进制位的汉明重量 -
如果未处理的二进制位的数量小于
128位, 那么程序使用查表算法来计算二进制位的汉明重量
NOTE: 这个BITCOUNT实现的算法复杂度为
O(n)，其中n为输入二进制位的数量
BITOP命令的实现
因为C语言直接支持对字节执行逻辑与(&),逻辑或(|),逻辑异或(^),逻辑非(~)操作, 所以BITOP命令的AND,OR,XOR,NOT四个操作都是直接给予这些逻辑操作实现的:
-
在执行
BITOP AND命令时, 程序会用&操作计算出所有输入二进制位的逻辑与结果, 然后保存在指定的键上面 -
在执行
BITOP OR命令时, 程序用|操作计算出所有输入二进制位的逻辑或结果, 然后保存在指定的键上面 -
在执行
BITOP XOR命令时, 程序用^操作计算出所有输入二进制位的逻辑异或结果, 然后保存在指定的键上面 -
在执行
BITOP NOT命令时, 程序用~操作计算出输入二进制位的逻辑非结果, 然后保存在指定的键上面。
BITOP AND result x y
以上命令的执行步骤
-
创建一个空白的位数组
value, 用于保存AND操作的结果 -
对两个位数组的第一个字节执行
buf[0] & buf[0]操作, 并将结果保存到value[0]字节 -
对两个数组的第二个字节执行
buf[1] & buf[1]操作, 并将结果保存到value[1]字节 -
对连个数组的第三个字节执行
buf[2] & buf[2]操作, 并将结果保存到value[2]字节 -
经过前面的三次逻辑与操作, 程序得到结果, 并将结果保存在
result上面
NOTE:
BITOP OR,BITOP XOR,BITOP NOT命令的执行过程和这里列出的BITOP AND的执行过程类似
因为BITOP AND,BITOP OR,BITOP XOR三个命令可以接受多个位数组作为输入, 程序需要遍历输入的每个位数组的每个字节来进行计算, 所以这些命令的复杂度位O(N^2); 与此相反, 因为BITOP NOT命令只接受一个位数组输入, 所以它的复杂度位O(n)
