21. 二进制位数组

1.Redis提供了SETBIT、GETBIT、BITCOUNT、BITOP四个命令用于处理二进制位数组(又称“位数组”)。

1)SETBIT:为位数组指定偏移量上的二进制位设置值,位数组的偏移量从0开始计数,而二进制位的值则可以为0或者1

2)GETBIT:获取位数组指定偏移量上的二进制位的

3)BITCOUNT:统计位数组里面,值为1的二进制位的数量

4)BITOP:既可以对多个位数组进行按位与(and)、按位或(or)、按位异或(xor)运算,也可以对给定的位数组进行取反运算。(异或:一正一负结果为真,都正都负结果为假)

 

2.位数组的表示

Redis使用字符串对象来表示位数组,因为字符串对象使用的SDS数据结构是二进制安全的,所以程序可以直接使用SDS结构来保存位数组,并使用SDS结构的操作函数来处理位数组。

注:buf数组保存位数组的顺序和我们平时书写位数组的顺序是完全相反的。如:保存的是1111 0000,其实对应的是我们认知里的0000 1111

 

3.GETBIT命令的实现

GETBIT命令用于返回位数组bitarray在offset偏移量上的二进制位的值

GETBIT <bitarray> <offset>

GETBIT执行过程:

1)计算byte=[offset / 8],byte值记录了offset偏移量指定的二进制位保存在位数组的哪个字节

2)计算bit=(offset mod 8)+1,bit值记录了offset偏移量指定的二进制位是byte字节的第几个二进制位

3)根据byte和bit值,在位数组中定位offset偏移量指定的二进制位,并返回这个值

 

4.SETBIT命令的实现

SETBIT用于将位数组在offset偏移量上的二进制位的值设置为value,并向客户端返回二进制位之前的旧值

SETBIT <bitarray> <offset> <value>

SETBIT的执行过程:

1)计算len=[offset / 8] +1,len值记录了保存offset偏移量指定的二进制位至少需要多少字节

2)检查bitarray键保存的位数组的长度是否小于len,如果是的话,将SDS的长度扩展为len字节,并将所有新拓展空间的二进制位的值设置为0

3)计算byte = [offset / 8],byte值记录了offset偏移量指定的二进制位保存在位数组的哪个字节

4)计算bit = (offset mod 8) + 1,bit值记录了offset偏移量指定的二进制位是byte字节的第几个二进制位

5)根据byte值和bit值,在bitarray键保存的位数组中定位offset偏移量指定的二进制位,首先将制定二进制位现在值保存在oldvalue变量,然后将新值value设置为这个二进制位的值

6)向客户端返回oldvalue变量的值

 

5.BITCOUNT命令的实现

BITCOUNT命令用于统计给定位数组中,值为1的二进制位的数量。

实现方法有如下几种:

1)遍历算法

遍历位数组中的每个二进制位,并在遇到值为1时,将计数器的值增一。

注:这个方法每次遍历只能查看其中一个位是否为1,因为1MB = 8000000bit,所以需要遍历8000000次

 

2)查表算法

对于一个有限集合来说,集合元素的排列方式是有限的。而对于一个有限长度的位数组来说,它能表示的二进制位排序也是有限的。

因此可以创建一个表,表的键为某种排列的位数组,而表的值则是相应位数组中,值为1的二进制位的数量

注:查表发受内存和缓存两方面因素的限制:

==1)查表法是典型的空间换时间策略,按照查表法来操作,位数越多,所需要的空间就是几何倍增长,内存大小是个问题

==2)查表法还受到CPU缓存的限制:对于固定大小的CPU缓存来说,创建的表格越大,CPU缓存所能保存的内容相比整个表格的比例就越少,缓存不命中的概率就会越大,缓存切入切出操作越频繁,最终影响效率。

 

3)variable-precision SWAP算法

BITCOUNT命令要解决的问题是——统计一个位数组中非0二进制位的数量,在数学上被称为“计算汉明重量”。

实现:

uint32_t swar(uint32_t i){
    //步骤1
    i = (i & Ox55555555) + ((i>>1) & Ox55555555);

     //步骤2
    i = (i & Ox33333333) + ((i>>2) & Ox33333333);

     //步骤3
    i = (i & Ox0F0F0F0F) + ((i>>1) & Ox0F0F0F0F);

     //步骤4
    i = (i & Ox01010101) >> 24;

    return i;
}

 

执行步骤:

==1)计算出的值i的二进制表示可以按每两个二进制位为一组进行分组,各组的十进制表示就是该组的汉明重量

==2)计算出的值i的二进制表示可以按每四个二进制位为一组进行分组,各组的十进制表示就是该组的汉明重量

==3)计算出的值i的二进制表示可以按每八个二进制位为一组进行分组,各组的十进制表示就是该组的汉明重量

==4)通过i * 0x01010101语句计算出位数组的汉明重量,并记录在二进制位的最高八位,而>>24语句则是通过右移,将位数组的汉明重量移到最低八位,得到的就是位数组的汉明重量

 

swar函数每次执行可以计算32个二进制位的汉明重量,它速度比较快,而且还不占用额外的内存。

另外,swar函数是一个常熟复杂度的操作,所以我们可以按照自己的需求,在一个循环中多次执行swar,从而按倍数提升计算汉明重量的效率。

当然,一个循环里执行多个swar调用是有极限的,一旦循环中处理的位数组的大小超过了缓存的大小,这种优化效果就会降低

 

4)Redis的实现

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

==1)查表法使用键长为8位的表,表中记录了从 0000 0000到1111 1111在内的所有二进制位的汉明重量

==2)至于variable-precisionSWAR算法,BITCOUNT命令在每次循环中载入128个二进制位,然后调用四次32位variable-precisionSWAR算法来计算这128个二进制位的汉明重量

在执行BITCOUNT命令时,如果未处理二进制位数量小于128位,使用查表法计算二进制位的汉明重量,否则使用variable-precisionSWAR算法来计算

 

6.BITOP命令

BITOP命令的AND、OR、XOR、NOT四个操作都是基于与、或、异或、非实现的。

BITOP AND result x y 

因为与、或、异或可以 接收多个位数组作为输入,程序需要遍历输入的每个字节进行计算,所以时间复杂度为O(n^2)

非只能接受一个位数组输入,所以时间复杂度为O(n)

    原文作者:鹏哥哥啊Aaaa
    原文地址: https://blog.csdn.net/qq_40594696/article/details/106618871
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞