Redis Learn-19-二维数组-02
基本概念
redis提供了setbit、getbit、bitcount、bitop四个命令用于处理二进制数组，称为bit array，又叫位数组。
setbit命令用于位数组指定偏移量上的二进制设置值，偏移量从0开始计算，值可以是0或者是1。
getbit获取指定位置上的值。
bitcount统计位数组里面，值为1的二进制位的数量。
bitop可以有and、or、xor，即与、或、异或的位运算。
位数组的表示
redis 使用字符串对象 sds 来表示位数组，因为其数据结构是二进制安全的。
因此，其末尾也会用 \0 来表示结尾。
一字节长度的位数组，在结构中表示如下：
其中，buf[0] 存放1字节的二进制数组，即长度是8位的二进制数组。
buf[1] 空字符即是 \0。
为了便于查看，采用如下方式：
getbit 实现
命令
getbit 返回位于数组 bitarray 的 offset 偏移量的值，命令即 getbit 。
执行流程
命令执行流程如下：
1）计算byte=offset/8，向下取整。该值记录了保存在offset偏移量的位数保存在哪个字节中，即上述的获取buf数组的下标。
2）计算bit=(offset mod 8)+1，获取二进制的位数是哪一位，即上述 buf[byte] 数组具体的位置。
3）根据上述的结果，获取 buf[byte][bit] 的值。
4）将结果返回给客户端。
例如对于某个二进制数组，getbit 10：
getbit 所有操作都可以在常数时间完成，时间复杂度是O(1)。
setbit 实现
普通 setbit
setbit 设置位于数组 bitarray 的 offset 偏移量的值为 value，命令即 setbit 。
命令执行流程如下：
1）执行 getbit 的 1、2 两步，确定需要修改的二进制的具体位置。
2）获取对应位置的值进行暂存到 oldvalue，并且将新的值设置进去。
3）将 oldvalue 返回给客户端。
setbit 时间复杂度也是 O(1)。
带扩展操作的 setbit
当设置的offset计算出的byte的结果超出现有的数组长度，即 buf[byte] 的下标超出现有的范围，则需要扩展。
例如，现有是 1 个字节，执行 setbit 12 1，则算出 byte=12/8 取整，值是1，但是当前不存在buf[1]，则redis会新开辟空间。
另外，redis基于redis开辟空间的策略（以前文章有提到），会扩展到5字节，剩余的空间是预留空间。
接着，按照前面的方式 setbit，并返回旧的bit值。
由于redis采用逆序保存二进制数组，因此在对buf进行扩展后，可以直接将值设置到对应的bit，而不必改动现有的二进制位。
如果是采用顺序方式保存，则每次扩展后，需要将位数组中已有的位进行移动，然后才能执行写入操作，则过程复杂。
应用场景
关注关系需求中 关注对象 和 被关注人 都是 0-几千万 的数据对象，存储这种对应关系时，采用bitmap 这种位数组，明显要比 uid 的 set 方式要节省存储空间，redis 的内存是很宝贵的，这值得作为考量的地方。
位数组大致可表示为：0101010000100000....0100 这样的二进制串， 在 Redis 的 SDS字符串 一文中可以看到 Redis 中的字符串对象实现，SDS数据结构是二进制安全的，所以 Redis 可以使用字符串来表示位数组 。
所以根据上面说的，位数组是以字符串的形式：buf[0]|buf[1]... 这样一个一个字节存放的。
命令
SETBIT 和 GETBIT
GETBIT 的实现：
# 返回 位数组 bitarray 在 offset 偏移量上的二进制位(byte*8+bit)的值
getbit
# 字节
byte = offset / 8
# 位
bit = (offset mod 8) + 1
# 可以看到 O(1)SETBIT 的实现：
# 将 位数组 bitarray 在offset 偏移量上的二进制位的值设置为 value
setbit
# 计算保存二进制位需要多少 字节
len = [offset / 8] + 1
# 鱿鱼二进制位数组使用的数据结构是 sds ，而 sds 记录长度的是len ，正常进行扩展，同空间预分配 ，扩展位为`00000`
# 字节
byte = offset / 8
# 位
bit = (offset mod 8) + 1
# 记录 (byte*8+bit) 上 oldvalue ，再赋予新值，返回 oldvalueBitcount 的实现
BITCOUNT 统计给定位数组中，值为 1 的数量，也就是统计汉明重量（见 Leetcode 191、338），其实是一个老问题，看看几种算法，和 redis 的做法。
bitcount 返回给定二进制数组中，值为1的二进制位的数量。
例如对于下图，返回的结果是 12。
粗暴遍历 O(n)
遍历算法是最简单但也最低效的方法，即遍历每个二进制位，当是1的时候，计数器加1。
这种算法中，遍历100MB长度的二进制数组，需要执行操作近8亿次。
class Solution(object):
def hammingWeight(self, n):
rst = 0
mask = 1
for i in range(32):
if n & mask :
rst += 1
mask = mask > 1) &0x55555555);
//步骤2
i = (i & 0x33333333) + ((i >> 2) &0x33333333);
//步骤3
i = (i & 0x0F0F0F0F) + ((i >> 4) &0x0F0F0F0F);
//步骤4
i = (i * (0x01010101) >> 24);
}说明
具体说明如下：
1）步骤1
计算出值i的二进制表示，可以按每两个二进制位为一组进行分组，各组的十进制位就表示该组的汉明重量。
解释：
0x55555555 = 0b01010101010101010101010101010101，可以看到奇数位都是1，偶数位都是0。
因此，假设j = i& 0x55555555，即j的偶数位都是0，奇数位是原始i的奇数位的1的数量。
(i >> 1) & 0x55555555，是将i右移一位以后，此时得到的临时变量还是奇数位的1和i右移后的奇数位的1的数量一样。
因此，也就是i右移之前的i的偶数位的1的数量。
因此，这两个数相加以后，得到的是两位一组的情况下，每两位的二进制位中1的数量。
2）步骤2
计算出值i的二进制表示，可以按每四个二进制位为一组进行分组，各组的十进制位就表示该组的汉明重量。
因为 0x33333333= 0b00110011001100110011001100110011，具体过程同第一步。
3）步骤3
计算出值i的二进制表示，可以按每八个二进制位为一组进行分组，各组的十进制位就表示该组的汉明重量。
因为 0x0F0F0F0F= 00001111000011110000111100001111，具体过程同第一步。
4）步骤4
i * (0x01010101) 计算出的是bitarray的汉明重量，并记录在二进制位的最高八位。通过>>24右移运算，将汉明重量移动到最低八位。得到的结果就是最终的结果。
这个要分两步来理解。
0x01010101 = 00000001000000010000000100000001 = (1 setbit bit 0 1 # 设置第0位为1 00000001
> setbit bit 0 1 # 设置第2位为1 00000101
> setbit bit 0 0 # 设置第0位为0 00000100# GETBIT bit 3 # 获取第3位的值
(integer) 1# BITCOUNT key [start end]
> 获取 bitmap 指定范围[start end]，位值为1的总个数# BITOP operation destkey key [key ...] # 对一个或多个bitmap 进行位元操作，并将结果保存到 destkey 上。
operation 可以是 AND 、 OR 、 NOT 、 XOR 这四种操作中的任意一种：
- AND：并
- OR：或
- XOR：异或
- NOT：非# BITPOS key targetBit [start] [end]
计算 bitmap 指定范围[start end]，第一个偏移量对应的值等于targetBit的位置个人收获
算法
算法的重要性