Skip to content

Latest commit

 

History

History
120 lines (82 loc) · 5.21 KB

22、二进制位数组.md

File metadata and controls

120 lines (82 loc) · 5.21 KB

Table of Contents generated with DocToc

Redis提供了SETBIT、GETBIT、BITCOUNT、BITOP四个命令用于处理二进制位数组。

  • SETBIT，为位数组指定偏移量上的二进制位设置值0或1。
  • GETBIT，获取位数组指定偏移量上的二进制位的值。
  • BITCOUNT，统计位数组中1的个数。
  • BITOP，既可以对多个位数组进行按位与、按位或、按位异或运算，也可以对给定位数组取反。

22.1 位数组的表示

Redis使用字符串来表示位数组，并使用SDS结构的操作函数来处理位数组。

  • redisObject.type的值为REDIS_STRING，表示字符串对象。
  • sdshdr.len值为1，表示这个SDS保存了一个一字节长的位数组。
  • buf数组的buf[0]字节保存了一个一字节长的位数组。
  • buf数组的buf[1]字节保存了SDS程序自动追加到值的末尾的'\0'。

22.2 GETBIT命令的实现

GETBIT

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

  1. 计算 byte = (offset / 8)，byte记录了offset偏移量指定的二进制保存在位数组的哪个字节。
  2. 计算 bit = (offset mode 8) + 1，bit记录offset指定的二进制位是byte字节的第几个二进制位。
  3. 根据 byte 和 bit 值，在位数组 bitarray中定位offset指定的二进制位，并返回这个位的值。

22.3 SETBIT命令的实现

SETBIT

用于将位数组bitarray在offset偏移量上的二进制位设置为value：

  1. 计算len = (offset / 8) + 1，len记录了offset指定的二进制位至少需要多少个字节。
  2. 检查bitarray键保存的位数组长度是否小于len。如果是，扩展，并将新空间的二进制位置为0。
  3. 计算 byte = (offset / 8)，byte记录了offset偏移量指定的二进制保存在位数组的哪个字节。
  4. 计算 bit = (offset mode 8) + 1，bit记录offset指定的二进制位是byte字节的第几个二进制位。
  5. 根据 byte 和 bit 值，在位数组 bitarray中定位offset指定的二进制位，首先将现在的值保存在oldvalue变量，然后将value设置为新值。
  6. 向客户端返回oldvalue的值。

22.4 BITCOUNT命令的实现

BITCOUNT用于统计给定位数组中，值为1的二进制位的个数。它的实现用到了查表和variable-precision SWAR两种算法：

  • 查表算法使用键长为8的表，记录了从0000 0000到1111 1111在内的汉明重量。
  • variable-precision SWAR算法方面，BITCOUNT在每次循环时载入128个二进制，调用四次32位variable-precision SWAR算法来计算这个128个二进制位的汉明重量。

根据二进制位的长度是否大于128，来决定使用哪种算法。

# 一个表，记录了所有8位长位数组的汉明重量
# 程序将8位长的位数组转换为无符号整数，并在表中进行索引
# 例如，对于输入0000 0011，程序将二进制转换为无符号整数 3
# 然后取出 weight_in_byte[3]的值 2，2 就是 0000 0011 的汉明重量
weight_in_byte = [0, 1, 1, 2, 1, 2, 2, ..., 7, 7, 8]

def BITCOUNT(bits):
    # 计算位数组中包含了多少个二进制位
    count = count_bit(bits)
    
    # 初始汉明重量为0
    weight = 0
    
    # 如果未处理的二进制位大于等于 128 位
    # 那么使用 variable-precision SWAR 算法
    while count >= 128:
        
        # 4个swar调用，每个调用计算32位二进制位的汉明重量
        # 注意：bits[i:j]中的索引j是不包含在取值范围之内的
        weight += swar (bits[0:32])
        weight += swar (bits[32:64])
        weight += swar (bits[64:96])
        weight += swar (bits[96:128])
        
        # 移动指针，略过已处理的位
        bits = bits[128:]
        
        # 减少未处理位的长度
        count -= 128
       
    # 如果执行到这里，说明未处理的位数量不足128，那么使用查表法
    while count:
        index = bits_to_unsigned_int(bits[0:8])
        weight += weight_in_byte[index]
        
        # 移动指正，略过未处理的位
        bits = bits[8:]
        
        # 减少未处理位的长度
        count -= 8
        
    return weight

22.5 BITOP命令的实现

BITOP命令直接使用C语言的逻辑运算。

导航

目录

上一章：21、排序

下一章：23、慢查询日志